Содержание к диссертации
Введение
Глава 1. Проблемы оптимизации технологии обработки потоков социально-экономической информации в сфере электронной торговли 15
1.1. Основные направления реализации Международной программы создания сети ИМЦ для продвижения товаров - и услуг на рынки стран СНГ 16
1.2. Разработка математических моделей выбора оптимальной технологии обработки информационных массивов 34
1.2.1 .Общие определения и обозначения 34
1.2.2. Содержательные постановки задач 36
1.2.3. Формальные постановки задач 39
1.2.4. Основные свойства задачи и стратегии поиска ее решения 40
1.3. Многокритериальная оптимизация 45
Выводы 46
Глава 2. Оптимальная декомпозиция зацикленного алгоритма поиска экономической информации 49
2.1. Декомпозиция алгоритма с помощью выделения контуров возведением матрицы смежности вершин модифицированного графа в степень 49
2.2. Декомпозиция зацикленных алгоритмов перебором замкнутых путей на графах 54
2.3. Использование алгоритма поиска кратчайших путей на графе 59
2.4. Минимизация объема используемой памяти 65
2.5. Многокритериальная оптимизация и лексико-графическое упорядочение критериев 67
2.6. Весовые коэффициенты целевых функций 69
Выводы 72
Глава 3. Размещение данных в памяти компьютера 73
3.1. Формальные постановки задач 73
3.2. Свойства оптимальных стратегий размещения данных 75
3.3. Алгоритмы размещения данных в памяти ЭВМ 85
3.4. Модификация модели и алгоритма 89
Выводы 94
Глава 4. Параллельная реализация обрабатываемой информации 95
4.1. Постановка задач 98
4.2. Поиск оптимальной декомпозиции зацикленного алгоритма 100
Выводы 108
Заключение 109
Литература
- Разработка математических моделей выбора оптимальной технологии обработки информационных массивов
- Декомпозиция зацикленных алгоритмов перебором замкнутых путей на графах
- Свойства оптимальных стратегий размещения данных
- Поиск оптимальной декомпозиции зацикленного алгоритма
Введение к работе
Актуальность проблемы. В настоящее время одним из мощных импульсов в развитии рыночных отношений в России может стать организация системы информационно-маркетинговых центров (ИМЦ), которые будут предназначены для продвижения товаров и услуг на национальные рынки государств - участников Содружества Независимых Государств (Программа работ утверждена Решением Совета глав правительств СНГ 29 ноября 2001 года). Основными задачами электронной коммерции, решаемыми в системе ИМЦ, являются организация маркетинговых исследований, проведение электронной торговли и рекламной деятельности по привлечению инвестиций в различные регионы и страны СНГ. Подключение к Интернету системы ИМЦ позволит участникам электронной коммерции обеспечить свое присутствие на глобальном уровне.
Первым шагом к электронной торговле для многих организаций является проведение маркетинговых исследований в интересах (или по заказам) инвесторов, производителей и иных хозяйственных субъектов ИМЦ, которые должны использовать маркетинговые данные в своих решениях. Эти задачи включают в себя определение спроса и предложений потребителей и поставщиков по видам продукций и услуг (анализ емкости рынка, прогнозирование объемов продаж, цен по определенным видам продукции и услуг); определение потенциальных потребителей и поставщиков, их финансово-экономические возможности; выявление потребительских свойств товаров и услуг, сегмент рынка и компоновка инвестиционных проектов с учетом ресурсных ограничений, логических связей (технического, технологического и организационного содержания) между вариантами привлечения исполнителей, вариантами технических решений, вариантами используемого оборудования, а так же целей.
В электронной торговле наблюдается быстрый процесс глобализации рынков, проявляющийся в том, что предприятия используют поставщиков компонентов в одной части мира, организуют сборочные операции в другой, а продают готовую продукцию в третьей. Такая деятельность должна включать в себя оптимальную процедуру, которая базируется на применении эффективных методов поиска партнеров. На практике колоссальный объем циркулирующей информации существенно усложняет проблему для покупателей и продавцов найти друг друга. Поставщики и торговые компании широко используют электронные базы данных о своей продукции. Хотя эффективное ведение баз данных отвечает интересам поставщиков, с точки зрения покупателей возникают сложности, связанные с необходимостью осуществления поиска по многочисленным базам данных.
Еще одним направлением, способствующим развитию электронной коммерции в Интернете, является организация проведения рекламной деятельности по инвестированию различных регионов и стран СНГ. Решение этой проблемы заключается в создании крупных сетевых информационных интеграторов новостей в области экономики, которые призваны собирать и давать объективную информацию по различным регионам России с целью привлечения туда инвестиций.
Каждая интересующая пользователя тематика, например, "банковская сфера" или "торговая сфера", в сутки может охватывать тысячи документов. В этом случае необходимо осуществлять мониторинг информационных ресурсов, который тесно связан с достаточно популярным методом анализа, таким как контент-анализ. Именно этот метод является перспективным направлением развития систем сетевой интеграции и рассматривается сегодня многими экспертами как контент-мониторинг, появление которого вызвано, прежде всего, задачей систематического отслеживания тенденций и процессов в постоянно обновляемой сетевой информационной среде.
Решение рассмотренных выше проблем организации маркетинговых
исследований, поиска партнеров в электронной торговле и анализа больших объёмов социально-экономической информации для проведения рекламной деятельности по инвестированию различных регионов России и стран СНГ приводит к необходимости разрабатывать быстродействующие методы обработки социальной и экономической информации.
Основу таких программных средств составляют программные реализации простых зацикленных алгоритмов, которые используют повторяющиеся процедуры: по заданному поисковому образу осуществляется поиск соответствующих данных, которые запоминаются и вновь повторяются. Помимо этих процедур в состав поисковых систем могут входить и другие проблемно-ориентированные прикладные программы, осуществляющие тот или иной целенаправленный анализ.
Крупный вклад в развитие теории и практики создания оптимизационных моделей и методов обработки социально-экономической информации внесли многие отечественные ученые. В их числе: СВ. Емельянов, К.А. Багриновский, В.Н. Бурков, О.В. Голосов, В.О. Гроппен, И.Н. Дрогобыцкий, В.А. Ириков, В.В. Кульба, Б.Е. Одинцов, А.Н. Романов, СВ. Черемных и другие.
Усилиями этих ученых сложилась база для дальнейшего обобщения результатов и теоретических разработок на одном из самых актуальных направлений - разработке математических моделей и методов обработки больших массивов социально-экономической информации в автоматизированных информационных системах и сетях компьютеров.
Одной из основных парадигм современного программирования, таких как проблемно-ориентированное программирование и объектно-ориентированное программирование, является оптимальное программирование. Оптимальное программирование это система моделей и методов, позволяющая применительно к заданной триаде задача-алгоритм-компьютер создавать программное обеспечение, эффективно реализующее специфику
этой триады.
Так, стремление к созданию универсального программного продукта противоречит концепции создания высококачественных программ, эффективно использующих ресурсы конкретных компьютеров, а сокращение трудозатрат программиста, связанное с применением виртуальной памяти, часто приводит к неэффективному использованию последней, повышающему время счета.
Традиционная технология обработки информации предполагает разработку структуры основных и вспомогательных массивов, их размещение в оперативной и внешней памяти компьютера, декомпозицию поискового алгоритма с тем, чтобы реализовать его в виде головной программы, присутствующей в оперативной памяти и взаимодействующей с ней в оверлейном режиме прикладными подпрограммами, размещенными на внешних носителях. Как правило, целью оптимизации выступает минимизация верхней либо нижней границы времени счета, затрат оперативной памяти, что определяется индивидуальностью программиста, а также его умением и навыками. Однако результаты разработок этих направлений достаточно скромные. Это связано с тем, что практические задачи имеют достаточно большую размерность и получение решений в реальном масштабе времени методами математического программирования сильно затруднено.
Попытка осуществить оптимальный выбор эффективного алгоритма организации вычислительного процесса для решения задачи обработки социально-экономической информации на имеющемся компьютере, лежит в основе предлагаемой в диссертации новой технологии проектирования программ, развитой применительно к программным реализациям простых зацикленных алгоритмов. Такие алгоритмы обработки социально-
экономической информации могут быть использованы для значительного числа задач электронной коммерции.
Используя существующие подходы, в диссертационной работе разрабатываются более эффективные средства автоматизации обрабатываемой социально-экономической информации. При этом целью автоматизации является оптимизация размещения программы, осуществляющей поиск необходимой информации, и самих информационных массивов в памяти компьютера или вычислительной системы с возможностями параллельной её обработки. К таким вычислительным системам относятся различные типы компьютеров (одно и многопроцессорные) и сетей компьютеров.
Исходя из вышесказанного, повышение эффективности алгоритмов обработки социально-экономической информации являются актуальной проблемой, требует дальнейших исследований, её решение позволит существенно улучшить качество принимаемых решений в электронной торговле.
Разрабатываемые в диссертационной работе модели и методы позволят существенно упростить технологию обработки информации, исключив некоторые процедуры, зависящие от человеческого фактора: размещение данных, декомпозицию алгоритма, создание вспомогательных массивов (при этом оптимальность и корректность самого алгоритма пользователя сомнению не подвергается). Они также дадут возможность получить некую разновидность виртуальной памяти, которая использует лишь программное обеспечение компьютера, оснащенного внешними носителями и обладающего трансляторами с языков высокого уровня.
Цель диссертации - разработка математических моделей и инструментальных методов оптимизации процессов обработки больших
объемов социально-экономической информации в системах электронной торговли.
Для достижения указанной цели в диссертации поставлены и решены следующие задачи.
Проведен анализ современного состояния решения задач электронной коммерции, которые включают в себя маркетинговые исследования, поиск партнеров в электронной торговле, а также проведение рекламной деятельности по инвестированию различных регионов и стран СНГ в информационных системах и компьютерных сетях.
Исследованы традиционные технологии обработки информации и определены возможные пути их модернизации с целью повышения быстродействия.
3. Разработаны формальные постановки задач по повышению
быстродействия технологии обработки информации за счет декомпозиции
основной программы и эффективного размещения основных и
вспомогательных массивов.
Усовершенствованы традиционные и разработаны новые эффективные методы организации процесса обработки социально-экономической информации, учитывающие специфику поставленных задач.
Проведены экспериментальные исследования разработанных алгоритмов на примере решения задачи формирования информационного сборника по инвестиционной привлекательности регионов России по материалам СМИ из сети Интернет.
Объект исследования - компьютерные системы и сети компьютеров, в которых циркулирует социально-экономическая информация, предназначенная для решения задач электронной торговли.
Предмет исследования - процессы обработки социально-экономической информации с помощью компьютеров и компьютерных сетей.
Методология исследования. Теоретическую и методологическую базу исследования составляет системный подход к моделированию сложных информационных систем.
В ходе проведения исследований использовались труды отечественных и зарубежных ученых в области математического и комбинаторного программирования. При решении конкретных задач были использованы научные работы в области теории вероятностей, математической статистики, теории графов, а также материалы научной периодики, конференций и семинаров.
Решение поставленных в диссертации задач потребовало применения методов комбинаторного программирования, функционального, статистического, системного и комбинаторного анализа, а также использование аппарата теории вероятностей и теории графов.
Диссертационная работа по своему содержанию соответствует пункту 2.5 паспорта специальности 08.00.13 - Математические и инструментальные методы экономики («Разработка концептуальных положений использования новых информационных и коммуникационных технологий с целью повышения эффективности управления в экономических системах»).
Научная новизна исследования заключается в решении научной задачи - повышение эффективности технологии обработки больших объемов социально-экономической информации для решения основных задач электронной коммерции.
Научную новизну содержат следующие положения.
Определен класс программ с повторяющимися вычислениями, которые базируются на простых зацикленных алгоритмах, используемых для обработки социально-экономической информации.
Разработаны формализованные постановки задач по размещению основных и вспомогательных информационных массивов в компьютере, определены граничные условия, при которых возможно было получить
решение исходной задачи в аналитическом виде. Это стало возможным за счет декомпозиции обобщенной задачи.
3. Доказана теорема, определяющая нижнюю границу числа обращений
к внешней памяти в общем случае, на основе которой разработаны более
эффективные алгоритмы обработки социально-экономической информации.
4. Разработаны эффективные алгоритмы обработки социально-
экономической информации, в которых оптимизация размещения данных
осуществляется одновременно с декомпозицией основной программы.
5. Разработаны стратегии управления многопроцессорной системой по
обработке социально-экономической информации, которые позволяют
существенно повысить быстродействие поиска решений задач электронной
коммерции.
6. Разработан комплекс программных средств, реализующих
технологию автоматизированного расчета по размещению основных и
вспомогательных информационных массивов в компьютере.
Экспериментальное исследование, разработанных алгоритмов показало их
преимущество по сравнению с традиционными методами.
Практическая ценность работы заключается в том, что основные положения, выводы и рекомендации диссертации ориентированы на широкое применение математических моделей и инструментальных методов для разработки систем автоматизированного управления обработкой больших объёмов социально-экономической информации с целью повышения эффективности принятия решений в задачах электронной торговли.
Разработка математического и инструментального обеспечения системы управления обработкой информационных массивов позволило существенно увеличить её быстродействие за счет оптимальной организации обрабатывающих программ и информационных массивов.
Проведенные исследования и полученные результаты составляют теоретическую основу построения систем автоматизированного управления
обработкой социально-экономической информации. Разработанные модели и методы направлены на решение практической задачи - повышение эффективности обработки больших объемов социально-экономической информации, циркулирующей в системах и компьютерных сетях. Результаты исследований доведены до конкретных методик, алгоритмов и программных комплексов.
Основные результаты исследования, имеющие практическое значение: технология автоматизации процесса обработки социально-экономической информации, реализация которой позволила повысить качество и сократить время принятия решений в задачах электронной коммерции;
алгоритмы обработки социально-экономической информации, учитывающие специфику задач электронной торговли.
Апробация и внедрение результатов исследования. Проведенные в диссертации исследования непосредственно связаны с планами научно-исследовательских работ Всероссийского научно-исследовательского института проблем вычислительной техники и информатизации (ВНИИПВТИ). Основные выводы и предложения диссертации прошли экспериментальную проверку и были использованы в научно-исследовательских работах:
«Прогноз развития российского сегмента Интернета до 2010 года» (Шифр «Прогноз-2002»)
«Создание системы ИМЦ для продвижения товаров и услуг на национальные рынки государств - участников Содружества Независимых Государств на период до 2005 года».
Алгоритмы и программы будут использованы при разработке программного обеспечения ИМЦ для динамического оперативного размещения данных в памяти IBM-совместимых персональных компьютеров на основе накапливаемой статистики обращений.
Разработан комплекс моделей и программный макет автоматизации обработки больших объёмов социально-экономической информации для решения задачи формирования рекламного информационно-аналитического сборника регионов России, которые были использованы в НИИР Центра прикладных экономических исследований и разработок Государственного университета - Высшая школа экономики (ГУ-ВШЭ) (соответствующие акты о внедрении прилагаются к диссертации).
Результаты исследований внедрены в виде:
пакета прикладных программ, который будет использован ВНИИПВТИ при разработке программного обеспечения ИМЦ для динамического оперативного размещения данных в памяти IBM-совместимых персональных компьютеров на основе накапливаемой статистики обращений.
Экспериментальная проверка была проведена при формировании интегрированного информационно-аналитического сборника для потенциальных инвесторов по рекламе наиболее привлекательных областей и регионов России.
Теоретические и практические результаты диссертационного исследования были также использованы при разработке компьютерной обучающей программы по курсу «Информационные технологии управления» для дистанционного образования студентов экономических специальностей Всероссийского финансово-экономического института ВЗФЭИ.
Основные положения диссертации докладывались и получили одобрение
на следующих конференциях и семинарах:
1-й Международной НТК «Проблемы развития топливно-энергетического комплекса: экономика, политика, история» (Москва, Российский государственный гуманитарный университет, 2000);
- П-й Международной НТК «Проблемы развития топливно-
энергетического комплекса: экономика, политика, история» (Москва,
Российский государственный гуманитарный университет, 2001);
VI-й Международной НТК «Комплексная защита информации» (Москва, Всероссийский научно-исследовательский институт проблем вычислительной техники и информатизации, 2002),
VII Международной НТК «Комплексная защита информации» (Москва-Минск, Объединенный институт проблем информатики НАН Беларуси, 2003),
а также на семинарах РГТУ, ВНИИПВТИ, ИЛУ РАН и Финансовой академии при Правительстве Российской Федерации.
Публикации. По материалам диссертации опубликовано 3 печатных работы общий объём - 1,7 п.л. (авторский объем 1,5 п. л.).
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, и приложения содержащего акты о внедрении результатов работы. Общий объем диссертационной работы 118 страница, содержащих машинописный текст и 20 схем.
Разработка математических моделей выбора оптимальной технологии обработки информационных массивов
Далее в диссертации использованы следующие обозначения, определения и допущения, в основном совпадающие с принятым в [14-16]:
G(X,U) - ориентированный граф, множество вершин которого X, а множество дуг U; Xj X - 1-я вершина множества X; (iJ)eU - дуга множества U, идущая из вершины Xj в вершину XJ; r(ij) - вектор, который ставится в соответствие дуге (iJ)eU: r(ij)={ri(ij),r2(ij)}. A(G) - множество простых контуров графа G(X,U) L(p,q) - путь из вершины хр в вершину х , ]d[ - целая часть от величины d; акє A(G) - k-й контур на множестве A(G); X(ak) - множество вершин, принадлежащих контуру ак; U(ak) - множество дуг, принадлежащих k-му контуру; ХтсХ - подмножество терминальных вершин графа G(X,U), полустепень исхода которых равна нулю;
Н - число массивов пользователя; W(i) - размер і-го массива пользователя, если он не меняется в процессе решения задачи; V - объем свободной оперативной памяти, используемой в компьютере; V] - часть объема свободной оперативной памяти, вьщеленная для хранения программных единиц (Vi V); V2. - часть объема свободной оперативной памяти, выделенная для хранения данных и массивов (Vi+V2 V);
Uj. - объем вспомогательного массива, предназначенного для сканирования 1-го массива пользователя при условии, что: а) последний не меняется в ходе реализации алгоритма; б) 1-й массив пользователя размещается на внешних носителях; Р;. - вероятность обращения к і-му массиву пользователя; Nj - прогнозируемое число обращений к і-му массиву пользователя (очевидно, что рі= — ). j=l
Каждой вершине х;єХ ставится в соответствие і-ое состояние вектора переменных решаемой задачи.
N(d,i j) - число обращений к d-му массиву пользователя при переходе от і-го состояния вектора переменных к j-му;
U(d,ij) - размер вспомогательного массива, размещаемого в оперативной памяти компьютера и предназначенного для сканирования d-ro массива пользователя при переходе от і-го состояния вектора переменных решаемой задачи к j-му. Очевидна справедливость неравенств: Vij:u(d,i,j) V2 d-1
Зацикленный алгоритм называется простым, если ему отвечает на графе G(X,U) простой контур. Контур называется простым, если он свободен от самопересечений, т.е. не содержит повторяющихся вершин либо дуг. Z - число задействованных процессоров используемой однородной вычислительной сети (очевидно, что для единичного компьютера Z=l); ri(ij) - время перевода вектора переменных решаемой задачи из і-го состояния в j-oe; r2(ij)- объем оперативной памяти, требуемой программным единицам для перевода вектора переменных решаемой задачи из і-го состояния в j-oe при условии, что время такого перехода равно rl(ij); P - общее число процессоров вычислительной системы (P Z); а - стоимость коллективно используемых аппаратных средств многопроцессорного вычислительного комплекса; b - стоимость аппаратных средств, отвечающих использованию одного процессора; ЬЛ- отношение числа программных единиц, реализующих зацикленный алгоритм к общему числу реализуемых ими операторов. с - нижняя граница времени однократного решения распараллеливаемой задачи пользователя при условии, что Z — оо; d - величина, для которой справедливо: если Z = 1, то время одной итерации определяется суммой c+d. Остальные обозначения, определения и допущения вводятся далее по ходу изложения.
Декомпозиция зацикленных алгоритмов перебором замкнутых путей на графах
Перебор контуров на графе с бикомпонентами процедурой, предложенной Неметри и рядом других авторов, сводится к перебору замкнутых путей, проходящих через различные вершины графа. Описание поиска решения задачи (1.1), включающий этот алгоритм, приводится ниже.
Алгоритм 2.2. Шаг l.R = +oo. Шаг 2. Все вершины исходного графа считаем непросмотренными. Шаг 3. На множестве непросмотренных вершин Хн выбираем вершину х«єХ. Если таковых нет, т.е. Хн = 0 - перейти к шагу 15. Шаг 4. Подмножество дуг, инцидентных вершине, выбранной на предыдущем шаге, считаем непомеченным. Шаг 5. На подмножестве выбранных и непомеченных дуг выбирается произвольная дуга (ij). Если таковых нет, т.е. все дуги помечены и і Р, то перейти к шагу 10, если же і = Р, то к шагу 11. Шаг 6. Если вершина Xj в которую заходит дуга (i, j), совпадает с хр, то перейти к шагу 12, в противном случае - к следующему шагу. Шаг 7. Если XJGX\XH, то дугу (i, j) считаем помеченной, перейти к шагу 5. Шаг 8. Если вершина Xj совпадает с одной из промежуточных вершин пути, построенного из хр в Xj, то дугу (i, j) помечаем и переходим к шагу 5. Шаг 9. Вершину Xj считать выбранной и перейти к шагу 4. Шаг 10. Дуга (f, g), заходящая в вершину, все множество дуг исходящих из которой помечено, также помечается. Выбранным считается множество дуг, исходящих из Xf. Перейти к шагу 5. Шаг 11. Вершину хр считать просмотренной. Перейти к шагу 3. Шаг 12. Неравенством (2.2) проверяется допустимость декомпозии алгоритма, определяемой найденным контуром, число дуг которого равно D. Шаг 13. Если R D, то переменной R присваивается новое значение, равное D, а соответствующий контур запоминается вместо хранившегося в памяти ранее. Шаг 14. Дута, заходящая в хр, помечается. Перейти к шагу 5. Шаг 15. Конец алгоритма. Величина R равна оптимальному значению целевой функции задачи (1.1), а дуги хранящегося в памяти контура определяют оптимальную декомпозию алгоритма.
Ниже работа алгоритма 2.2 иллюстрируется решением задачи, приведенной в примере 2.2. Пример 2.3. Пользуясь условием примера 2.2 решить задачу (1.1) алгоритмом 2.2.
1) Все вершины графа G(X, U) (рис. 2.2) считаем непросмотренными. На множестве вершин X выбирается вершина хе X.
2) Повторение шагов 5-10 соответствуют построению дерева G(X, U), изображенному на рис.2.3.
В результате этой итерации получаем R = 3, что соответствует контуру а={х,(1,2),х,(2,3),х,(3, 1),х}.
3) на множестве непросмотренных вершин X\xi выбирается вершина х2, являющаяся корневой вершиной дерева Ог(Хг, U2), построенного повторением шагов 5 -10 и изображенного на рис.2.4.
Решение остается неизменным.
4) На множестве непросмотренных вершин X\(xi U х2) выбирается вершина хз, являющаяся корневой вершиной дерева G3(X3, U3), построенного повторением шагов 5 -10 и изображенного на рис.2.5.
Значение рекорда R остается неизменным.
5) На множестве непросмотренных вершин X\(xi U х2 U хз) выбирается единственная оставшаяся непросмотренной вершина Х4.. Единственная исходящая из нее дуга сразу помечается (рис.2.6).
В результате сохраняется оптимальное решение, полученное на первой итерации.
Легко убедиться, что объем перебора алгоритмом 2.2 пропорционален п3. Сравнение алгоритмов 2.1 и 2.2 позволяет утверждать, что каждый из них имеет свои достоинства: первое же допустимое решение, полученное алгоритмом 2.1, является глобально оптимальным планом задачи (1.1), что позволяет прекратить поиск в то время, как алгоритм 2.2, даже после того, как глобально оптимальное решение найдено, вынужден продолжать поиск, чтобы убедиться в том, что полученное решение действительно является глобально оптимальным. Последнее было продемонстрировано примером 2.3 - глобально оптимальное решение было найдено на первой итерации, все остальные итерации были необходимы только для того, чтобы убедиться, что оно является глобально оптимальным. Более эффективным представляется подход, базирующийся на поиске кратчайших путей на графах, содержательное описание и пример реализации которого приводятся в следующем параграфе.
Свойства оптимальных стратегий размещения данных
В простейшем случае все данные могут быть размещены в двух массивах 1 и Ij: первый используется для хранения данных, необходимых для решения любой задачи, второй - всех остальных данных.
Если при переходе от і-го к j-му вектору переменных массивы 10 И І! сканируются соответственно N(0,ij) и N(l,iJ) раз, то задача минимизации числа обращений к внешней памяти при однократном проходе по зацикленной программе, отвечающей простому контуру аь имеет вид:
Так как решение системы (3.1) оптимально, если минимально каждое слагаемое целевой функции, заключенное в квадратные скобки, поиск решения этой системы можно заменить поиском решения U(ak) задач вида: причем задача (3.2) решается для каждой дуги (ij)eU(aic). Избавляясь от постоянного слагаемого целевой функции задачи (3.2) легко убедиться, что оптимальные векторы переменных последней и приведенной ниже совпадают [12,16]:
Обобщением (3.3) на случай, когда число массивов пользователя Н превышает 2, является постановка (2.1). При этом для того, чтобы перейти от числа обращений к d-му массиву N(d,ij) к соответствующей вероятности, достаточно разделить каждое слагаемое полученной системы на величину D(iJ): D(UJ)=ZN( UJ). d=0 Свойства, используемые для решения задач (3.1) -(3.3), (1.2) анализируются ниже.
Объем перебора на полных планах, необходимый для получения глобально оптимального решения задачи (1.2), равен Q: Q=nW(i), что затрудняет поиск решения.
Анализ свойств задачи (1.2) позволяет сократить объем перебора, а применительно к задаче (3.3) - исключить его. Последнее достигается благодаря приводимой ниже теореме:
Теорема 3.1. Нижняя граница значения целевой функции системы (3.3) достигается следующими значениями переменных U(0,ij) и U(l,ij): U(0,i,j)=V2 VW(0)N(0,i,j) /G; U(l,i,j)=V2VW(l)N(l,i,j) /G; (3.4) где G=VW(0)N(0,i,j) +VW(l)N(l,iJ) . Доказательство: Пусть Vd, y(d,ij) = 1, а неравенство, содержащее V2 в (3.3) заменено равенством, т.е.: U(d,i,j)=V2. d=0
Тогда одну переменную системы (3.3) можно заменить другой: U(0,i,j)=V2- U(l,i,j) (3.5) после чего, подставляя правую часть (3.5) в целевую функцию системы (3.3), получим функцию F(iJ) одной переменной:
Приравнивая нулю производную dF(ij)/dU(l,i,j), получим (3.4). Так как в точке экстремума значение второй производной неотрицательно, полученная точка соответствует минимуму функции F. Теорема доказана.
Следует отметить, что полученные на основании (3.4) значения переменных могут быть дробными, что, формально, в связи с переходом к целочисленным значениям, может ухудшить значение целевой функции. Однако реальное число обращений к внешней памяти также целочисленно, и это демпфирует колебания значений переменных. Ниже такое положение дел иллюстрируется примером. Пример 3.1. Пусть в задаче (3.3) исходные данные имеют следующие значения: W,=100; N(l,ij)=4; W0=144; N(0,ij)=l; V2=100
Тогда, на основании (3.4) значения переменных определяются следующим образом:
Обобщением задачи (3.3) является следующая: в оперативной памяти постоянно присутствуют вспомогательные массивы, число которых равно (Н+1), где Н - число массивов, размещенных во внешней памяти, информация в которых может полностью меняться, причем размеры и число обращений к этим массивам совпадают. Формальная постановка задачи минимизации числа обращений к внешним носителям тогда имеет вид: где W(iJ) и N(ij) - соответственно размер и число обращений к меняющимся массивам пользователя, a U(iJ) - емкость вспомогательных массивов, используемых для их считывания.
Сравнивая (3.2) и (3.7) легко убедиться, что системы совпадают с точностью до обозначений, откуда следует справедливость следующей теоремы
Поиск оптимальной декомпозиции зацикленного алгоритма
Пусть требуется определить число процессоров Z в специализированной однородной ЛВС, решающей однотипные задачи зацикленным алгоритмом, если параметры а, Ь, с и d соответственно равны: 1; 2; 1; 8, а стоимость однократного решения всех задач не превосходит величины F=25. Легко убедиться, что решением полученной системы: + »min; является Z=2, т.е. сеть, удовлетворяющая поставленным выше условиям, должна содержать два процессора.
Переходя к многокритериальной оптимизации имеет смысл выделить случаи, позволяющие использовать рассмотренные выше подходы. Один из таких подходов связан с лексикографическим упорядочением критериев -если минимизация стоимости доминирует над минимизацией времени, то в силу специфики задачи справедлива следующая лемма.
Лемма 4.1. Если в (4.9) доминирующим по отношению ко времени счета критерием является стоимость однократного решения задачи, то решение этой системы определяется теоремой 4.1.
Доказательство. Так как решение, определяемое (4.10), отвечает оптимизации по доминирующему критерию, а дальнейшее сокращение времени счета связано с увеличением величины Z и, соответственно, с ухудшением значения доминирующего критерия, то решение, определяемое (4.10), является оптимальным и для (4.9), если доминирует стоимость решения.
Аналогичная лемма может быть доказана для случая, когда в (4.9) доминирует минимизация по времени счета, затраченному на однократное решение всех подзадач.
Лемма 4.2. Если в (4.9) доминирующим критерием является время, затрачиваемое на однократное решение всех подзадач, а верхняя граница величины Z равна Р, то оптимальным решением (4.9) является Z=P.
Доказательство леммы тривиально: поскольку дальнейшее увеличение Z невозможно, оптимизация по второму критерию может быть связана только с уменьшением аргумента Z, что, в свою очередь, повлечет ухудшение доминирующего критерия, а это противоречит принципу Парето. Таким образом, оптимальным является значение Z, равное Р. Лемма доказана. Из лемм 4.1 и 4.2 вытекает обобщающая их теорема: Теорема 4.2. Если в (4.9) критерии лексикографически упорядочены, то оптимальное решение зависит только от доминирующего критерия, доминируемый же может игнорироваться.
Иными словами выше доказано, что постановка многокритериальной оптимизационной задачи с лексикографически упорядоченными критериями применительно к исследуемой предметной области не имеет смысла.
Выводы
В этой главе рассмотрены методы оптимизации, базирующиеся на разбивке задачи на несколько независимых подзадач, каждая из которых может решаться теми же алгоритмами, что и исходная. Это имеет смысл при наличии многопроцессорных ЭВМ, или ЛВС.
Заключение
Настоящее исследование посвящено актуальной проблеме оптимизации обработки информации в системах электронной торговли.
В последние годы наблюдается «взрывной» рост объемов торговли через Internet. Причем этот рост характерен не только для развитых стран Америки, Европы и Азии, но и для России и стран СНГ. Однако, как показывают исследования, почти половина покупок в онлайне срывается из-за медленной загрузки электронных магазинов, а плохое качество и недостаточная оптимизация сайтов - причины 82 % упущенных прибылей предприятий электронной торговли.
Выполненная автором работа направлена, в первую очередь, на создание быстрых и надежных методов обработки социально-экономической информации в системах электронной торговли, что позволяет решать многие наболевшие вопросы, которые препятствуют дальнейшему развитию электронной торговли. Основное внимание при этом уделялось оптимизации использования ресурсов ЭВМ в зависимости от решаемых задач. В частности, одной из важнейших задач была разработка алгоритмов эффективного распределения оперативной памяти в зависимости от выполняемой подпрограммы и объема информации, обрабатываемого этой подпрограммой. Решение этой задачи позволяет обрабатывать информацию с максимальной полнотой и скоростью.
