Введение к работе
Актуальность проблемы. Модели и методы оптимизации являются в настоящее время важнейшим инструментом для изучения и анализа сложных систем. К моделям оптимизации сводятся многие прикладные задачи: управление в технических системах, управление социально-экономическими системами, моделирование развития топливно-энергетических комплексов, модели расширения и развития производства, сетевые и транспортные задачи, календарное планирование и оперативное управление в производственных системах и многие другие.
Оптимизационное моделирование позволяет находить не только одно наилучшее решение задачи, но и исследовать объект при различных критериях оптимизации, при изменениях параметров модели, выявлять зависимость между отдельными факторами модели, учитывать неопределенность в значениях параметров.
Увеличение размеров прикладных задач, появление новой вычислительной техники, параллельных вычислений, вызывает необходимость развивать и совершенствовать теорию и методы решения задач оптимизации большой размерности. -ч Конечные методы оптимизации показывают надежность и стабильность при решении прикладных задач и, поэтому, получили широкое распространение на практике.
Многие конечные методы решения для задач оптимизации большой размерности можно разбить на три группы: декомпозиция, блочная факторизация и варианты мультипликативного симплекс-метода.
Достоинства и недостатки этих подходов хорошо известны.
Декомпозиция является широко признанным инструментом для решения и анализа структурных задач оптимизации. В методах декомпозиции, имеется в виду прямая и двойственная декомпозиция, исходная задача разбивается на главную задачу и подзадачи и организуется взаимодействие между задачами; подзадачи генерируют столбцы или строки (в двойственной декомпозиции) и передают их в главную задачу.
Декомпозиция имеет естественную концептуальную и экономическую интерпретацию. В журнале Mathmatlcal Programming (11,1976) академик Кантарович подчеркнул: "Мы должны отметить блестящий математический формализм идеи декомпозиции, предложенной Данцигом и Вульфом. Значение их статьи (1960) гораздо больше чем рамки предложенного ими алгоритма и его математического обоснования".
Однако, методы декомпозиции существенно замедляют процесс решения, особенно при ближений к оптимуму. Методы декомпозиции обладают одной особенностью. При переходе к новому пространству переменных ( на примере прямой декомпозиции ) в главной задаче число вершин, а, следовательно, и число итераций, значительно возрастает, процесс решения замедляется. Кроме того, после получения оптимального решения требуются еще дополнительные операции для восстановления решения в исходных переменных.
Методы блочной факторизации следуют в процессе решения по вершинам и ребрам исходной задачи, как ив методах третьей группы, но при этом информация преобразуется с учетом блочного разбиения исходной задачи, подобно методам декомпозиции. Методы блочной факторизации оперируют с исходными переменными в процессе решения , однако , они вызывают слишком часто обмен между задачами, что также замедляет процесс решения.
Большинство научных работ, связанных с указанными подходами, в основном расширяют эти идеи на различные классы задач (нелинейные, целочисленные, стохастические), применяют к прикладным задачам. Мало внимания уделяется их вычислительной эффективности.
Цель работы. Основной целью работы является построение теории для обобщения конечных методов решения задач оптимизации и создание на ее основе эффективных методов решения. Разработка методов агрегирования для анализа и решения задач оптимизации большой размерности. Применение предложенных подходов для моделирования производственных процессов.
Методы исследования основаны на применении методов системного анализа, исследования операций, математического программирования, методов решения задач оптимизации большой размерности, теории оптимального управления. Научная новизна работы. В диссертации предложен подход, позволяющий рассматривать и анализировать конечные методы решения задач оптимизации с единой позиции.
Предложена модификация метода прямой декомпозиции, метод ключевых базисов (МКБ). Разработан вариант метода блочной факторизации, метод стратегии допустимых базисов (СДБ). Доказывается, что эти методы в процессе решения следуют по эквивалентным траекториям.
Доказывается также, что в предложенных методах отсутствуют лишние итерации, характерные для методов декомпозиции.
На основе разработанного аппарата предлагается развитие методов декомпозиции, блочной факторизации и симплекс-метода. Этот подход позволяет объединить некоторые полезные свойства этих групп методов. Первое, исходная задача
разбивается на главную задачу и подзадачи в процессе решения как в методах декомпозиции, тем самым давая возможность развязать исходную задачу и решать подзадачи по отдельности. Второе, в предложенном подходе траектория решения выходит время от времени на ребра и вершины исходной задачи подобно методам блочной факторизации или симплекс-методу. В дальнейшем этот подход будем называть компаунд декомпозицией.
В работе предлагаются новые стратегии для ускорения сходимости декомпозиционных методов. Эти стратегии, под названием методы глобальных функций, основаны на декомпозиционных принципах и позволяют оставаться в рамках декомпозиционного подхода. Предложенные стратегии строятся с использованием геометрических свойств многогранников.
Предложен подход для анализа и решения задач оптимизации на основе агрегирования. Суть подхода состоит в том, чтобы заменить исходную задачу оптимизации большой размерности агрегированной задачей, при этом разность оптимальных значений функционалов исходной и агрегированной задач должна находиться в заданных пределах для некоторой области изменения параметров задачи. Если при изменении условий задачи оценка разности функционалов выходит за допустимые пределы, то задается новая агрегированная задача, лучше приближающая исходную задачу.
В результате исследований осуществлено теоретическое обобщение конечных методов решения задач оптимизации большой размерности и разработана теория построения декомпозиционных методов, имеющая важное значение для управления сложными системами. Теоретическая и практическая ценность работы. Доказанные в работе теоремы дают возможность установить взаимосвязь между методами декомпозиции, блочной факторизации и симплекс-методом,
а также развить на этой основе новый подход для построения эффективных декомпозиционных алгоритмов и программ.
Теоретические и методологические основы диссертации позволяют распространить предложенный подход на широкие классы задач оптимизации: нелинейную и двойственную декомпозицию, целочисленные задачи, транспортные и сетевые задачи, стохастическое программирование, задачи с различной блочной структурой, декомпозиция с распределением ресурсов и многие другие.
Предложенный в работе подход по декомпозиции и агрегированию использовался для моделирования производственных процессов.
Апробация работы. Основные результаты диссертационной работы докладывались на IV и V Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (г. Усть-Нарва, 1976, 1978), на IX Международном симпозиуме по математическому программированию (Будапешт, ВНР, 1976), на VI, VII и VIII Всесоюзном симпозиуме "Системы программного обеспечения решения задач оптимального планирования" (Пущино, 1980; Усть-Нарва, 1982, 1984), на Международной конференции "Оптимальное управление - Теория и Приложения" (Лейпциг, ГДР, 1983), на Международной конференции "Моделирование и оптимизация систем" (Лихте, ГДР, 1984), были прочитаны в виде лекций на научных школах "Декомпозиция и координация в задачах проектирования и управления" (Миасс, 1988) и "Декомпозиция и координация в сложных системах" (Алушта, 1990), докладывались на Международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 1989), на 14-й Международной конференции IFIP "Моделирование систем и
оптимизация" (Лейпциг, ГДР, 1989), на 15-й Международной конференции IFIP "Моделирование систем и оптимизация" (Цюрих, Швейцария, 1991), на Международном симпозиуме IFAC "Большие системы; теория и приложения" (Пекин, Китай, 1992), на 16-й Международной конференции IFIP "Моделирование систем и оптимизация" (Компьень, Франция, 1993), на 15-м Международном симпозиуме "Математическое программирование" (Энн Арбор, США, 1994).
Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы из 174 названий и приложения , включает 14 рисунков, 10 таблиц, содержит 273 страницы машинописного текста.
Публикации. По теме диссертации опубликовано 29 научных работ. Больше половины работ выполнены без соавторов. Основные результаты, вынесенные на защиту, получены лично автором.