автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Развитие конечных методов решения задач оптимизации. Декомпозиционный подход

РОССИЙСКАЯ АКАДЕМИЯ НАУК ' - ч А "ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА

« 5 О V ! I

1 1 !'• О Л '¡ Специализированный совет Д 003.63.02

На правах рукописи

КРИВОНОЖКО Владимир Егорович

РАЗВИТИЕ КОНЕЧНЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ. ДЕКОМПОЗИЦИОННЫЙ ПОДХОД

Специальность 05.13.01 - управление в технических системах

АВТОРЕФЕРАТ

Диссертация на соискание ученой степени доктора физико-математических наук

Москва - 1996

Работа выполнена в Институте системного анализа Российской Академии Наук (ИСА РАН)

Официальные оппоненты: член-корреспондент РАН, д.т.н., профессор доктор физ.-мэт. наук, профессор доктор физ.-мапг. наук, профессор

Коровин С.К. Антипин А.С. Бобылев Н.А.

Ведущая организация: Московский физико-технический институт Защита состоится

1996 г в

час. на заседании

специализированного совета Д 003.63.02 Института системного анализа РАН по адресу: 117312, г.Москва, проспект 60-летая Октября, д. 9.

С диссертацией Можно ознакомиться в библиотеке Института системного анализа РАН.

Автореферат разослан 1996 г.

Ученый секретарь специализированного совета, д.т.н.,

профессор

Пропой А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Модели и методы оптимизации являются в настоящее время важнейшим инструментом для изучения и анализа сложных систем. К моделям оптимизации сводятся многие прикладные задачи: управление в технических системах, управление социально-экономическими системами, моделирование развития топливно-энергетических комплексов, модели расширения и развития производства, сетевые и транспортные задачи, календарное планирование и оперативное управление в производственных системах и многие другие.

Оптимизационное моделирование позволяет находить не только одно наилучшее решение задачи, но и исследовать объект при различных критериях оптимизации, при изменениях параметров модели, выявлять зависимость между отдельными факторами модели, учитывать неопределенность в значениях параметров.

Увеличение размеров прикладных задач, появление новой вычислительной техники, параллельных вычислений, вызывает необходимость развивать и совершенствовать теорию и методы решения задач оптимизации большой размерности, -ч Конечные методы оптимизации показывают надежность и стабильность при решении прикладных задач и, поэтому, получили широкое распространение на практике.

Многие конечные методы решения для задач оптимизации большой размерности можно разбить на три группы: декомпозиция, блочная факторизация и варианты мультипликативного симплекс-метода.

Достоинства и недостатки этих подходов хорошо известны.

Декомпозиция является широко признанным инструментом для решения и анализа структурных задач оптимизации. В методах декомпозиции, имеется в виду прямая и двойственная декомпозиция, исходная задача разбивается на главную задачу и подзадачи и организуется взаимодействие между задачами; подзадачи генерируют столбцы или строки (в двойственной декомпозиции) и передают их в главную задачу.

Декомпозиция имеет естественную концептуальную и экономическую интерпретацию. В журнале 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-й Международной конференции 1ПР "Моделирование систем и оптимизация" (Цюрих, Швейцария, 1991), на Международном симпозиуме 1РАС "Большие системы; теория и приложения" (Пекин, Китай, 1992), на 16-й Международной конференции 1ПР "Моделирование систем и оптимизация" (Компьень, Франция, 1993), на 15-м Международном симпозиуме "Математическое программирование" (Энн Арбор, США, 1994).

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, списка литературы из 174 названий и приложения , включает 14 рисунков, 10 таблиц, содержит 273 страницы машинописного текста.

Публикации. По теме диссертации опубликовано 29 научных работ. Больше половины работ выполнены без соавторов. Основные результаты, вынесенные на защиту, получены лично автором.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы исследования, приводится обзор литературы, сформулированы цель и задача работы, дается ' краткое изложение основных положений диссертации.

В первой главе рассматривается сначала общая схема

факторизации для задач с нижней блочно-треугольной структурой.

Затем эта схема детализируется и используется для построения

методов решения следующих важных классов задач: динамического

линейного программирования (ДЛП), динамических задач с

запаздываниями, динамических транспортных задач (ДТЗ), задач с

блочно-диагональной структурой .

Рассмотрим задачу линейного программирования с

6

блочно-треуголыюй матрицей условий.

Задача 1. Максимизировать функционал

при условии

I = £ (С1,хг) -

> шах,

t=l

I ^ Л = V

J=l

4=1,....р.

ХЛ ~ 0 '

(2)

(?)

Здесь матрица размерности гаьхг.)' вект0Ры ,Х1 ' С{=1.....р) имеют размерности г,., гъ, ик# соответственно.

Основнши моментами в методах факторизации являются способ факторизованного представления базисных матриц и процедуры преобразования факторизованного представления на каждой итерации алгоритма. Поэтому основное внимание уделяется именно этим операциями.

Согласно структуре матрицы ограничений (1) - (3) базисная матрица В имеет вид

В =

11

В21 В22 В31 взг взэ

рр

где через В^ обозначены подматрицы, составленные из базисных столбцов матриц

Базисную матрицу В можно представить в виде

В = в*и ...и = в*и. р 1

Матрицы В и и имеют следующую структуру

В* =

н.

*2 А .....*

Р

"к =

ГФ.. ,0. . ,Ф. .0 к кк+1 кр

•I

Здесь Н1(2=1,...,р) - квадратные неособенные матрицы порядка га., 1т - единичная матрица порядка п^. Матрицы И (1=1,... р) будем называть локальными базисами.

Введем обозначения

Фк = [ф,. ..Фь ), и. , = 10; Ф. .; 01.

кк+1 кр О 10*

Здесь матрица имеет размерность и.х т и получена из

матрицы "Ф^ добавлением, в случае необходимости, нулевых столбцов. Тогда матрица (/ (4) имеет вид

и =

1р

I/

р-1р I

т

Р

С учетом перестановки . столбцов в процессе факторизации

разобьем вектор базисных переменных в соответствии с представлением (4) Х=(Х^,.. . ,Хр), где вектор Х1 связан с локальным базисом Н

Локальный базис Нь может состоять из стобцов матрицы В1(., а также из некоторых столбцов, принадлежащих шагу т С т<( ), пересчитанных на шаг Точно так же компонентами вектора Хь могут быть некоторые компоненты вектора хт ( т<( ).

Пусть векторы X и X разбиты на части в соответствии с

"У-

* ¿г

разбиением матрицы В; Х=(Х1>... ,Х ), X =(Хг

прямом ходе вычисляется вектор вспомогательных переменных X":

■ ■ =

При

< = ^

1-1

1 ¿_ и

Л=1

1=2,

При обратном ходе вычисляется вектор X:

X = X , р р

(5)

(6)

х= х* - У и, .х., 1=р-1, 1 1 и л 0=1 + 1

Аналогичным образом находятся коэффициенты разложения вводимого вектора по текущему базису и двойственные переменные.

Во втором разделе описывается процедура преобразования факторизованного представления (4).

При решении систем линейных уравнений на каждой итерации симплекс-метода используются матрицы Н~1(т=1,...,р) и фТ(т=2,...,р-1). При замене столбца в базисе Б эти матрицы необходимо преобразовать. Эффективность предлагаемого подхода в значительной степени зависит от эффективности процедуры преобразования обратных матриц локальных базисов и матриц Фт

(X= ], . ..,р-1).

Сложность преобразовния состоит в том, что, во-первых,

изменение локального базиса влияет на последующие локальные

базисы Нт("т={ + 1,... ,р) и, во-вторых, номер шага, которому

принадлежит вводимый вектор Л[ , может не совпадать с номером

1

локального базиса Я , которому принадлежит выводимый вектор, т.е.

Приводимая ниже теорема дает достаточное условие, при котором замена столбца в локальном базисе И1 не изменит других локальных базисов.

Теорема 1.1. Замена .¡-го столбца в локальном базисе Я не изменит других локальных базисов, если 1-я строка матрицы

I ~1 2

Ф =Н1 равна нулю.

В диссертации разработана конструктивная процедура

преобразования факторизованного представления при замене

базисного столбца. Определяется операция перестановки двух

столбцов между локальными базисами- Доказывается, что в

результате одной перестановки преобразуются только два

локальных базиса, преобразование обратных матриц локальных

базисов происходит посредством умножения слева на элементарную

(строчную или столбцевую) матрицу, что позволяет хранить

обратные матрицы локальных базисов в мультипликативном виде.

При помощи последовательных перестановок переведем

выводимый вектор в такой локальный базис Я , где выполняется

з

условие теоремы 1.1 или, если такого не существует, в последний локальный базис Нр . В локальном базисе Иг произведем замену

выводимого столца вводимым. Доказывается. что указанные перестг.ноаки возможны. В результате будет получена новая

и

система невырожденных локальных базисов.

В предложенном подходе вместо обращения всей глобальной матрицы задачи 1 в процессе решения достаточно оперировать лишь с системой из р обратных матриц локальных базисов размерности тх 1=1,...,р). Существенно, что на одной итерации преобразуется только часть локальных базисов. Кроме того, так как обратные матрицы локальных базисов преобразуются посредством умножения слева на элементарные (строчные или столбцовые) матрицы, то локальные базисы можно представлять также в факторизованном виде и использовать для этого эффективные процедуры, разработанные для общих задач ЛП.

В третьем разделе рассматривается метод факторизации 1 для задач динамического линейного программирования (ДЛП).

В достаточно общем виде задача динамического линейного программирования (ДЛП) может быть сформулирована следующим образом.

Задача ДЛП. Найти управление и={и(0),...,и(Т-1)) и траекторию х = (х(0),..., х(Т)}, удовлетворяющие уравнениям движения

ха+1) = лсшси + вами, х(о) =х° а=о,1, ■ ■ .,т-1)

и фазовым ограничениям

СШхШ + 0Ши(О = иг),

и(1) £ 0 ("{=0, ],..., Г-Л, для которых показатель качества 11(и)=(с(Т), х(Т)) принимает максимальное значение. Здесь хСОе £" , иСПе £г, Ет,

матрицы A(t), бСО, DCt)l Ва), и векторы х°.с(Т) имеют соответствующие размерности и считаются заданными. Число шагов планирования Т фиксировано.

Применяя процесс факторизации,' описанный в разделе 1, и используя структуру базисной матрицы В задачи ДДП, можно показать, что В представима в виде" . . V ,

В\-2(/Т-2--Ли0 =Уи ■ {1)

На главной диагонали в матрице В* стоят либо единичные

подматрицы -.1 ( порядка п, либо квадратные неособенные матрицы

ЯпоСПС••■,Т-1) порядка га, которые также назовем локальными ов

Л

базисами. В матрицу ВовСи могут входить столбцы матрицы 0да), а также некоторые столбцы с шага т(т<Ь), пересчитываемые в процессе факторизации на шаг Ь.

Матрицы [/ь, У являются верхнетреугольными матрицами с единичной главной диагональю. В этих матрицах ненулевые подматрицы, стоящие над главной диагональю, имеют вид Ф^а) для матриц -В (V - для матриц Vь( 1=0,..., Ь; j=t+ll ... ,Т~1), где матрица Ф ^а) (В^а)) состоит из столбцов, которые соответствуют столбцам матрицы ВВП), пересчитываемых в

/ч .

процессе факторизации в матрицу DQB(J/. Подматрицы Ф^а) и -Вг1 ("О расположены в тех же строках матриц II и V , соответственно,, что и. подматрицы и

п*

соответственно, в матрице В , Введем обозначение

фсо •= [Ф^ПО.-Ф^Ш,.,

вЧо = .в^а). . .;в^~1а)1.

1 -Размер матриц ФСО, В1(О меняется в процессе решения. На первых итерациях метода их вообще нет, так-как локальный базис ОррСи (1=0. -... ,Т-;1) строится из столбцов, принадлежащих :шагу. Теорема 1.2. Число столбцов в матрице Фа).. СВ^СХ))

< 1=0.....Т-1) не больше п. ■ .,..,..

" 12

Особенность данной факторизации (7) состоит в том, что на каждом четном шаге процесса факторизации в качестве квадратной неособенной матрицы выбирается единичная матрица -I , связанная с фазовыми переменными х(Ь) .

В работе показывается как вычисляются вектор решений, коэффициенты разложения вводимого вектора и симплексные множители относительно данного факторизованного представления.

Схема преобразования факторизованного представления базиса (7) на каждой итерации алгоритма совпадает с общей схемой преобразования, описанной в разделе 2. Заметим, что при данной факторизации матрицы -I , Аа), 0(1), связанные с фазовыми переменными, в процессе решения преобразовываться не будут. Это позволяет повысить точность вычислений и уменьшить объем оперативной памяти.

В задачах ДЛП переменные по своей физической природе делятся на фазовые ха) и управляющие и ("О переменные. С точки зрения ЛП фазовые переменные являются свободными. При данной факторизации в локальные базисы будут входить только управляющие переменные. Решение систем линейных уравнений относительно базисной матрицы записываются в виде уравнений динамики. Таким образом, предложенный метод существенно использует динамический характер задач.

В предложенном методе в процессе решения вместо глобального базиса достаточно оперировать лишь с системой из Т обратных матриц локальных базисов порядка та, связанных между собой простыми соотношениями. Поэтому предлагаемый подход может рассматриваться, по существу, как декомпозиции динамических задач.

В четвертом разделе приводится метод факторизации II яг.~.

13

задач динамического линейного программирования. Рассматривается метод факторизации для задач ДЛП с разбиением фазовых переменных. В методе факторизации, изложенном в предыдущем разделе, использовался тот факт, что фазовые переменные является свободными переменными и поэтому всегда входят в глобальный базис задачи. При наличии отдельно выделенных ограничений на знак фазовых переменных возможна другая схема факторизации, так как фазовые переменные могут входить в базис и выходить из базиса. В этом параграфе строится схема факторизации, учитывающая возможность наличия ограничений на знак или ограничений сверху на значение фазовых переменных.

В пятом разделе рассматриваются динамические задачи с запаздыванием. При небольшом времени запаздывания относительно периода планирования Г эти задачи можно решать как обычные задачи ДЛП, если увеличить локальные базисы за счет введения в них строк и столбцов с соседних шагов планирования. При запаздывании близком к Т , структура матрицы условий задачи ДЛП с запаздыванием аналогична структуре задачи 1 и поэтому для нее справедлива вся техника, описанная для задачи 1.

В шестом разделе рассматриваются динамические транспортные задачи (ДТЗ). Транспортные алгоритмы линейного программирования, разработанные на базе конечных методов решения общей задачи ЛП. полностью учитывают специфику транспортных задач и весьма эффективны в вычислительном отношении. Следует отметить, что прямо использовать эти методы для решения динамических задач невозможно, так как структура матрицы условий ДТЗ отличается от структуры матрицы условий статической транспортной задачи.

Следующие теоремы позволяют существенно упростить решение

14

динамических транспортных задач.

Теорема 1.3. Локальные базисы Ж О ((=0,...,Г-]) ДТЗ приводятся к треугольному виду.

Теорема 1.4. Если объемы производства и потребления ДТЗ -целые числа, то любой ее опорный план составлен из целочисленных компонент и среди решений задачи имеется хотя бы одно целочисленное.

В работе устанавливается, что коэффициенты разложения любого вектора условий по столбцам глобального базиса принимают значения 0,-1,*1.

Схемы преобразования локальных базисов на каждой итерации алгоритма для общих задач ДЛП остаются справедливыми для ДТЗ.

Подчеркнем, что в процессе решения ДТЗ предложенным методом не происходит накопления ошибок округления, что особенно важно при решении задач большой размерности.

В седьмом разделе описывается детализация общей схемы решения задачи 1 для задач с матрицей условий, имеющей блочно-диагональную структуру со связывающими строками.

Во второй главе проводится анализ траекторий решения в методах декомпозиции, блочной факторизации и симплекс-методе. Для задач линейного программирования с блочно-треугольной структурой разрабатываются специальные модификации методов декомпозиции и блочной факторизации, которые имеют эквивалентные траектории решения, т. е. следуют в процессе решения по одинаковым базисным решениям. Предложенный подход позволяет выявить различие и подобие методов декомпозиции, блочной факторизации и симплекс-метода, а также анализировать эти методы с единых позиций.

Рассмотрим задачу оптимизации с независимыми блоками

15

связывающими ограничениями

тт с х +

1 = 1

Ах + ^ С1у* = Ь , 1 = 1

(9)

о'у1 = Ь1, 1=1, — ,к, х г 0 , у1 0 , 1=1,...,к,

(10) (11)

Пп 1 п< тп 1 т! 0 1

где х 6 К Й \ Ь е И , Ь'е \ а векторы си и с1 и

матрицы Л, С1, 01(1=1,...,к) имеют соответствующие размерности.

Изложим специальный вариант метода блочной факторизации,

который позволяет провести сравнение рассматриваемых подходов. Метод стратегии допустимых базисов ССДБ)

1. Начинаем симплекс-метод с квадратных диагональных матриц в качестве базисов для главной задачи и подзадач, это могут быть, например, единичные матрицы, соответствующие искуственным или дополнительным переменным.

2. Установим множество потенциально вводимых переменных .7,

л

которое состоит из переменных х и у а=1,..., к), т.е. тех,

которые в данный момент находятся в рабочем базисе У, а также

возможно, из переменных-предложений из подзадач. (Пока

в

множество 3 не переопределится, переменные в текущем у могут входить и выходить из базиса)! Выполняем симплексные итерации только на множестве переменных ] , пока не обнаружится, что

а) выводимая переменная находится вне множества J ;

б) ни одна из переменных множества J не может быть введена в базис;

в) задача неограничена.

В случае в) останов, исходная задача неограничена. Преобразуем множество J , исключая из него переменные из подзадач, не входящие в рабочий базис, кроме вводимого столбца. В случае а) переходим к шагу 3. В случае б) переходим к шагу 4.

3. Пусть переменная, выводимая из локального базиса, будет

у1 и, без ограничения общности, соответствует г-ой позиции

Р в.

локального базиса D .

а) Если вводимая переменная у' , то в блоке 1 решаем

задачу

min у^

Л. Л

В -В в в D 1у 1 + D iy 1 + D1 у1 = h\ (12)

о ■

у 1> 0, у г о, у* > 0 ,

Л

, , В

здесь 0 обозначает j-й столбец матрицы 0 и у есть вектор

переменных из у1 , которые входят в текущий рабочий базис.

в1

В качестве нового локального базиса д возьмем

й в

оптимальный базис задачи (12). Модифицируем вектора у , у

и множество J согласно перестановкам переменных между этими

векторами в процессе решения задачи (12). Преобразуем рабочий

в

базис в соответствии с изменением локального базиса д и

Л

в.

матрицы Э 1 . Если переменная ур 'находится в рабочем базисе, то выводим ее из рабочего базиса и вместо нее вводим ту

переменную, которая оказалась вне векторов у и у в результате решения задачи (12).

Исключаем переменную у^ из базисных переменных и множества 3 . 17

в) Если вводимая переменная у' , т.е. 1*1 . то в

блоке 1 решаем задачу

т1п у'

Л Л

о%В1 ♦ 0\в' = И1. (13)

в. в» у ^ 0, у £ О,

в

где у есть вектор переменных, которые входят в текущий рабочий базис.

в.

В качестве нового локального базиса 0 возьмем

В1 ®|

оптимальный базис задачи (13). Модифицируем вектора у , у

и множество J согласно перестановкам переменных между векторами

в процессе решения задачи (13). Преобразуем рабочий базис^ в

в в

соответствии с изменениями локального базиса И и матрицы 0 . Переменную у^ выводим из рабочего базиса и вместо нее вводим у^. Исключаем переменную у^ из базисных переменных и множества

J.

с) Переходим к шагу 2.

4. Производим оценку столбцов в подзадачах начиная с подзадачи 1=1 , если подходящий столбец не найден, то полагаем 1=1+1 , и так до последнего блока к .

Если подходящий вводимый столбец найден, то добавляем его в множество 3 и переходим к шагу 2.

Иначе останов, получено оптимальное решение задачи.

Задача (12) или (13) имеет оптимальное базисное решение, потому что она имеет оптимальное небазисное решение и начальный

допустимый базис.

Следующее утверждение помогает нам прояснить некоторые

существенные моменты алгоритма.

Теорема 2.1. После изменения локального базиса на шаге За

или Зв алгоритма преобразованный рабочий базис будет

невырожденным, а выводимая переменная у^ будет удалена из

рабочего базиса.

Перейдем к изложению специального варианта метода

декомпозиции, который позволяет сравнить рассматриваемые

подходы.

Метод ключевых базисов (МКБ)

1. Выберем допустимое базисное решение в каждой подзадаче и передадим в ограниченную главную задачу. Назовем столбцы, полученные из этих базисных решений, ключевыми столбцами. Решаем ограниченную задачу. Пусть Ь1=0 и Р1=0 для всех 1.

2. Пусть допустимые базисные решения, которые сгенерировали ключевые столбцы, будут начальными базисными решениями для подзадач. Для ]-й подзадачи (1=1,...,к) производим оценки столбцов для того, чтобы найти подходящую переменную для ввода в базис.

а) Если такая переменная у^ найдена, то добавляем з к 7множеству подходящих переменных из подзадачи 1. Если выводимая переменная в подзадаче существует, то по переменной у^ находим в подзадаче новую смежную вершину

+ е1,1-1+1еа , (14)

здесь - множество базисных номеров в векторе у1,0 ,

который назовем ключевой вершиной 1-й подзадачи, ё

19

единичный вектор-столбец размерности п. с единицей в ;-й строке, ? - единичный вектор-строка размерности

/л1 с единицей в столбце К}) , где базисный столбец подзадачи занимает 1-ю позицию в базисе, - единичный вектор-столбец размерности п. с единицей в Б-й строке, вектор у1,0 определяется соотношением

В.-.-1

«¿Л »'Г'1

■К'0

Добавляем столбец, определяемый вектором у1 *ь +1 , в ограниченную главную задачу, устанавливаем Ь1=Ь1+1.

Если переменная у^ определяет неограниченное крайнее ребро, то добавляем столбец, сгенерированный этим ребром, к ограниченной главной задаче.

в) Если ни в одной из подзадач ] подходящей переменной для ввода в базис не найдено, то останов, получено оптимальное решение задачи.

3. Решаем ограниченную главную задачу, ключевые переменные оставляем в базисе, позволяя им быть отрицательными, пока а) остаются подходящие столбцы для ввода в базис, или в) пока не нарушаются ограничения

I.*

- £ [ 01'1] Л1-'1 * 0 , (15)

1 = 1 1

В — 1

для некоторого 1 , V1 =[ Х> '] И1 . величины в1,1

■«! I • J 'Б1

определены при построении вершин у1,1 (14), или

с) пока не обнаружилась неограниченность задачи.

В последнем случае останов, исходная задача неограничена.

Преобразуем каждое множество 71 . исключая из него индексы

20

переменных, которые генерируют столбцы, не входящие в базис

ограниченной задачи, исключим эти столбцы из ограниченной

главной задачи, перенумеруем оставшиеся столбцы и преобразуем,

соответственно, множества Ь1 и Р1.

Если ограничения (15) не нарушены, переходим к шагу 2.

Иначе, пусть вектор коэффициентов разложения вводимого

столбца относительно текущего базиса ограниченной главной

задачи будет а , без ограничения общности будем считать, что • а

1.1

переменные \ .....Д.

1.1,

из подзадачи 1 являются базисными в

1.1

главной задаче, причем А является базисной в позиции 0(1, I) и {¡(¡,1) < 0(1,1+1), 1=1,..., I -1 , и пусть Н1 будет значением левой части соотношения (15) при последнем решении, которое удовлетворяет (15) при всех 1 . Для нахождения ограничения, которое первым нарушается в подзадаче, для каждого 1 вычислим вектор ^ , где

Г\ =

1

1 = 1 1 р если а соответствует Л1,р для некоторого р ,

^ ■ * и у V * * м * V *

К V

(16)

1 = 1

если а соответствует либо Л1'р для

• о

некоторого р и 1 * ( или х для некоторого к .

Находим индексы д и г такие, что

К ^ .

—г = ш1п —? , ■ (17)

г}<0

где минимум достигается на тех q иг. где ограничение (15)

21

нарушается.

4. Пусть переменная, выводимая из локального базиса, будет

у4 и, без ограничения общности, соответствует позиции г

г в

локального базиса D ч.

а) Если а соответствует некоторой переменной у|| , т. е. • 9 Р

переменная у£ вошла в ключевой базис q и образовала смежную вершину в соответствии с (14), которая сгенерировала столбец а для главной задачи, то в блоке q решаем задачу

• я

min

1

в в

D чу 4 + У D4 у4 + D4 у4 = ftq , (18)

si si -P P

1=1

yBq - 0 , у4 г 0 , 1=1,...,I .

где переменные у4 (1=1,...,1 ) принадлежат множеству и

1 ч

соответствуют столбцам, которые в текущем базисе ограниченной

главной задачи, обозначим множество этих переменных через ^ .

В качестве нового ключевого базиса для q-ti подзадачи

возьмем оптимальный базис задачи (18), Модифицируем множество

Jq и ^ в соответствии с перестановками переменных в процессе

решения "задачи (18). Смежные вершины, определяемые множеством

J(i , пересчитаем относительно нового ключевого базиса.

Преобразуем базис главной задачи в соответствии с изменением

ключевого базиса и смежных вершин. Если столбец главной задачи.

соответствующий переменной , находится в базисе главной

задачи, то выводим его оттуда, заменив одним из столбцов,

соответствующего переменной задачи (18), не вошедшей в

множество или в вектор ключевых локальных базисных

переменных в результате решения (18). Исключаем переменную у4

22 г

из множества J4 , соответственно, преобразуем множества L4 и Рч .

в) Если а соответствует переменной, не связанной с

• j

подзадачей q, то в блоке q решаем задачу

min у4

1

в в -3-

D чу 4 + У D4 у4 = h4 , f-. si si

(19)

.3,-5,

1 = 1

в

у 4 > 0 , у4 > 0 , 1=1,..., 1„, } <7

где переменные у4 принадлежат множеству ,/4 и соответствуют

столбцам, которые находятся в текущем базисе ограниченной главной задачи.

В качестве нового ключевого базиса для д-й подзадачи возьмем оптимальный базис задачи (19). Модифицируем множество ./ч в соответствии с перестановками переменных в процессе решения задачи (19). Смежные вершины, определяемые множеством , пересчитаем относительно нового ключевого базиса. Преобразуем базис главной задачи в соответсвии с изменением ключевого базиса и смежных вершин. Базисный столбец главной задачи, соответствующий переменной , выводим из базиса и вместо него вводим столбец а . Исключаем переменную у4 из

•я ^

множества Л4 . Соответственно преобразуем множества Ьч и Рч . с) Переходим к шагу 3.

Задачи (18) и (19) имеют оптимальное базисное решение по той же причине как и в предыдущем алгоритме.

Следующие две леммы, доказанные в работе, помогают установить фундаментальный результат о траекториях исследуемых методов.

Лемма 1. Методы СДБ и МКБ следуют по одной и той же траектории, пока не произойдет смена ключевого (локального) базиса (нарушение ограничения в подзадаче).

Лемма 2. Методы СДБ и МКБ получат одно и то же решение на итерации после смены ключевого (локального) базиса.

Сформулируем утверждение, характеризующее работу МКБ алгоритма.

Теорема 2.2. После смены ключевого базиса подзадачи на шаге 4а и 4в алгоритма МКБ преобразованный базис в ограниченной главной задаче будет невырожденным и столбец, соответствующий выводимой переменной у^, будет удален из базиса главной задачи.

В диссертации доказывается следующий важный результат, устанавливающий взаимосвязь исследуемых подходов.

Теорема 2.3. Стратегии методов СДБ и МКБ следуют по одной и той же траектории решения в задачах линейного программирования с независимыми блокамии и связывающими ограничениями.

Эквивалентность траекторий решения в методах СДБ и МКБ, доказанная во второй главе, дает возможность сравнивать траектории решения в методах декомпозиции, блочной факторизации и симплекс-методе, выявлять взаимосвязь между ними и развивать на этой основе новые подходы.

Б третьей главе рассматривается развитие методов решения для .задач оптимизации большой размерности. Подчеркнем, что в основном рассматриваются методы, которые могут быть разбиты на три группы: методы декомпозиции, блочная базисная факторизация и варианты мультипликативного симплекс-метода.

В предыдущей главе был получен теоретический результат, который устанавливает взаимосвязь между этими группами методов. В этой главе излагается развитие упомянутых групп методов. В представленном подходе подзадачи генерируют специальный тип предложений, строки или столбцы, которые назовем компаунд предложения, наряду с обычными предложениями для главной задачи.

В методах декомпозиции при переходе к эквивалентной главной задаче, пространству А переменных, возникает одна особенность, существенно влияющая на сходимость декомпозиционных алгоритмов. Исходная блочная задача и главная задача в декомпозиции эквивалентны в том смысле, что любое решение исходной задачи может быть представлено через суперпозицию переменных главной задачи. И обратно, суперпозиция переменных главной задачи дает решение исходной задачи. Однако, в главной задаче, пространстве Л переменных, возникают дополнительные вершины, которых нет в исходной задаче. А это вызывает в декомпозиционных методах выполнение лишних итераций, которые определим как внутренние итерации.

Развиваемый . в работе подход позволяет избежать дополнительных внутренних итераций в прямой и двойственной декомпозиции.

Теорема об эквивалентности траекторий методов СДБ и МКБ, доказанная в предыдущей главе, помогает получить еще один

25

важный результат.

Теорема 3.1. В методах СДБ и МКБ отсутствуют внутренние итерации.

В данной главе побробно описывается метод компаунд декомпозиции, который позволяет объединить полезные свойства декомпозиции, базисной факторизации и симплекс-метода.

За исходную задачу возьмем задачу (8-11).

Метод компаунд декомпозиции (МКД).

1. Выбираем допустимое базисное решение из каждой подзадачи для включения в начальную ограниченную главную задачу. Установим множества 1^=0 и Ji=0 для всех 1 . Решаем ограниченную главную задачу.

2. Пусть допустимые базисные решения, которые включены в главную задачу из подзадач, будут у1,0 . Увеличиваем К 1=1,... ,Ю пока существуют некоторые переменные для ввода в базис подзадачи.

а) Если некоторые переменные у' найдены, тогда приписываем индексы этих переменных к Jl и добавляем их к /Л множеству переменных предложений из подзадачи 1. Переменные у*, seJi, определяют направления

крайних лучей, выходящих из вершины у1,0, где есть

множество базисных индексов в векторе у1,0 , ё^ есть единичный вектор-столбец размерности л1 с единицей в строке ] , есть единичная вектор-строка размерности л^ с единицей в столбце Н]) , где столбец j занимает 1-ю позицию в базисе, ез

26

- единичный вектор-столбец размерности п{ с единицей в s-й строке, и где

'■ЧЕ «AlfoT»'-

Пусть

|д11 . < = - ,3' 2 . «J1, (21)

4 z •s Ii2

где Д' есть приведенная оценка столбца, связанного с у'. Определяем направление

il = У а'г1 •

4,1 3

(22)

S

€J1

луча «r'd1 с переменной с1.

Добавляем столбец, сгенерированный предложениями (21) и (22), к ограниченной главной задаче. Определяем столбец, сгенерированный предложением (22), как компаунд столбец или (г-столбец.

в) Если ни одна из подзадач 1 не дает подходящий столбец для вывода в базис подзадачи, тогда останов, исходная задача решена.

3. Решаем ограниченную главную задачу

к к min .ЗД + I

i = 1jeL 1 = 1

Лх

i=ijeL i=i i=i

X, yj, 0ла 0,

где столбец ü1^ и коэффициенты стоимости с*, JeL1, получены как в методе базисной факторизации (Гл. 11) и

-1 .«К • * ■ I «К. •

seJ1 seJ1

пока

а) ни одна из переменных в ограниченной главной задаче не будет подходить для ввода в базис главной задачи, или в) не нарушатся ограничения

в,i-l , .

(23)

[»'Г- Е Л0

jeL1

для некоторого I, где ülj = [ О J и = ' или

sei1

с) не встретится неограниченность задачи.

В случае (с) останов, исходная задача неограничена. Удаляем некоторые предложения в главной задаче, если необходимо, и преобразуем JL1 . В случа (а) удаляем о-1-столбцы, если они небазисные и устанавливаем J1=0, соответственно. Переходим к шагу 5.

Иначе, находим индексы подзадачи и строки такие, что неравенство (23) нарушается. Пусть представление вводимого столбца относительно текущего базиса главной задачи будет а .

28

4. Пусть переменная, выводимая из базиса подзадачи, будет yq, и, без ограничения общности, соответствует позиции г в базисе подзадачи q . Пусть J* обозначает множество индексов переменных из блока i , которые принадлежат рабочему базису У. а) Если а соответствует <гч , тогда удаляем этот столбец.

• о

Пусть Jq=J4uJ?. Устанавливаем ß=0.

О

в) Если а соответствует некоторой переменной у4 и - о Р

переменная <гч является базисной в V , тогда заменяем столбец <гц в I/ одним из столбцов из J4, удаляем столбец <гч. Пусть Iq=JquJqup. Устанавливем Jq=0.

D

z) Если а у соответствует некото4 лй переменной yq и <гч не является базисной в W, тогда пусть Jq=Jqup.

d) Если а соответствует некоторой переменной, не

• о

связанной с подзадачей q и переменная с4 является базисной в У, тогда заменяем столбец crq в У на один из столбцов из J4, удаляем столбец <гч. Пусть J4=JquJq. Устанавливаем Jq=0.

О

e) Если а соответствует некоторой переменной, не

• i

связанной с подзадачей q и переменная <гч не входит в базис I/,

тогда пусть /4=Jq.

в

Решаем подзадачу вида

min у4

J г

В В _

D qy 4 ♦ ) Dq уЧ = f (24)

J€/q J

yBq í О , yq > 0 , je/4 .

здесь D4j есть j-й столбец матрицы D4 .

Если yq для некоторого р должна быть введена в базис подзадачи в процессе решения (24) и peíq\Jq , ТОгда сначала у4

заменяет одну из переменных в V и после этого она вводится в базис подзадачи. Однако, если представление столбца yj¡ относительно V нулевое, тогда переменная yjj вводится в базис подзадачи непосредственно.

Пусть новый начальный допустимый базис для q будет

оптимальный базис задачи (24). Преобразуем множества L4 и J|j.

Преобразуем рабочий базис. Преобразуем столбцы в ограниченной

главной задаче, связанные с подзадачей q . Если столбец yj}

находится в рабочем базисе после решения (24), тогда заменяем

его на а или на столбец, соответствующий некоторой • 7

переменной в задаче (24).

Переходим к шагу 3.

5. Увеличиваем i (1-1,...,к) пока не найдется некоторая переменная у^ для ввода в базис подзадачи для некоторых i и j. Если ни одна из подходящих переменных не найдена, тогда исходная задача решена. Если оптимальное решение небазисное и/или некоторые <г1 столбцы находятся в рабочем базисе, тогда получаем базисное решение и/или заменяем <г1 столбцы в базисе на их компоненты. Останов.

Иначе,

а) если столбец <г1 уже существует в ограниченной главной задаче, тогда генерируем обычные предложения в подзадаче i как в (20), переходим к шагу 3.

в) если столбца о-1 еще нет в главной задаче, тогда поступаем как в шаге 2, т. е. генерируем столбец <г1 и обычные столбцы для главной задачи, переходим к шагу 3.

Приведенные ниже теоремы разъясняют некоторые существенные моменты излагаемого подхода.

Теорема 3.2. Если некоторый <г* столбец находится в рабочем базисе, тогда он может быть заменен одним из небазисных столбцов, принадлежащих множеству .

Теорема 3.3. После изменения базиса подзадачи на шаге 4 метода модифицированный рабочий базис будет невырожденным и выводимая переменная будет удалена из рабочего базиса.

Эти теоремы дают возможность удалять компаунд столбцы на шаге 4 или 5 алгоритма и рассматривать вместо них их компоненты.

Отметим, что небазисные решения могут появляться в процессе решения из-за ввода компаунд столбцов. Эта ситуация аналогична до некоторой степени ситуации в нелинейных методах. К базисному решению можно перейти обычными ведущими итерациями.

Предлагаемый подход является развитием методов декомпозиции и базисной факторизации и обладает некоторыми полезными свойствами обоих подходов.

1. Исходная структурная задача разбивается в процессе решения на главную задачу и подзадачи, таким образом, можно выполнять итерации некоторое время в главной задаче без вызова подзадач как в методах декомпозиции. Реализация алгоритма выполняется так, что обращение к подзадачам происходит только тогда, когда необходимо выбрать новые предложения.

2. Предлагаемый метод следует в процессе решения почти по вершинам и ребрам исходной задачи подобно методам базисной факторизации или симплекс-методу.

В главе рассматривается также развитие данного подхода на нелинейный случай и применение к двойственной декомпозиции. Приводятся результаты численных экспериментов и описывается иллюстративный пример.

В четвертой главе предлагаются новые стратегии ускорения сходимости методов прямой и двойственной декомпозиции. Этот подход основан на принципе декомпозиции и позволяет нам оставаться в рамках декомпозиционной схемы.

В предлагаемом подходе подзадачи генерируют специальные дополнительные предложения согласно некоторому новому критерию, наряду с обычными предложениями для главной задачи. Это дает возможность нам уменьшить число главных циклов, т. е. число решений главной задачи, следовательно уменьшить число обменов между главной задачей и подзадачами. Кроме того, этот подход уменьшает число итераций в главной задаче.

Предлагаемые стратегии строятся с использованием геометрических свойств многогранников.

Рассмотрим блочную задачу оптимизации (8-11).

Для сходимости алгоритма Данцига-Вульфа важную роль играет выбор вычислительной стратегии. Во время процесса решения подзадачи множество допустимых базисных решений обычно выбирается для генерирования предложений в главную задачу согласно определенному механизму.

Прежде всего, проверяется следующий тест для кандидата

V1 = (с1 - т^сЪу1,1 - «г1 < - сг , (25)

где у1,1 текущее допустимое безисное решение подзадачи , е1 -параметр, определяемый пользователем.

Если решение у1,1 удовлетворяет (25), тогда проверяются правила, которые управляют генерированием предложений. Эти правила для стандартного алгоритма декомпозиции могут быть следующими.

1. Относительное улучшение целевой функции подзадачи.

2. Относительное улучшение приведенной стоимости кандидата.

32

3. Частотный контроль.

4. В случае неограниченности генерируются два совместных предложения: одно из крайнего луча и одно из крайней точки, соответствующей текущему базисному допустимому решению.

5. Процедура для генерирования предложения (решение подзадачи i ) оканчивается, если

(а) подзадача i оптимизирована, или (в) NCls достигает , где NC^ указывает как много предложений было сгенерировано из подзадачи i . ЯС' является параметром, который ограничивает число предложений, сгенерированных из подзадачи 1 во время одного решения, или

(с) N С достигает ÏJC , где NC является текущим числом предложений, сгенерированных из всех подзадач во время одного главного цикла, параметр NU определяет максимальное число кандидатов из всех подзадач за один главный цикл.

Назовем описанный выше механизм для генерации столбцов Процедурой 1.

В представляемом подходе предлагается генерировать дополнительные предложения, если число WC* обычных предложений после решения подзадачи i меньше чем ÏÏU1 .

s

Для этой цели решается подзадача min c'y'

DV = h1 , (26)

У1 2 О

В этом случае применяется следующий тест для кандидатов

и1 = сУ'1 - ¡Г1 < - с, , (27)

8 1

где

¡Г1 = У (с'у'-'д1'^ У (с1 г1'"^1*' 8 Ь-г 1

(28)

здесь /1 есть множество базисных индексов ограниченной главной

О

задачи, связанных с переменными из подзадачи 1 . Индексное множество Гр и значение определяются после решения

ограниченной главной задачи перед вызовом подзадач.

Процедура 2 для генерирования дополнительных предложений может быть написана в форме Процедуры 1, в которой решаются подзадачи (26) и тест для кандидатов (27) заменяет соотношение (25).

Отметим, что общее число ИС^ предложений из подзадачи I остается то же самое, а значение ЛК7* суммирует предложения, сгенерированные Процедурой 1 и Процедурой 2.

Теперь дадим общую схему генерирования предложений для алгоритма Данцига-Вульфа на стадии решения подзадачи 1 . Стратегия Глобальной Функции (СГФ)

1. Решаем подзадачу 1 , используя Процедуру 1 для генерирования предложений.

2. Если КС* = 0 , переход к шагу 4.

Если ИС1в < тогда переход к шагу 3, иначе переход к

шагу 4.

3. Решаем подзадачу 1, используя Процедуру 2 для генерирования предложений пока < ЯС*. где МС^ есть текущее число дополнительных предложений, сгенерированных во время этого

■ шага, параметр КС^ определяет максимальное число

34

дополнительных предложений. 4. Вызываем следующую задачу для решения или возвращаемся в ограниченную главную задачу.

Отметим, что наряду с правилами окончания в Процедуре 1, шаг 5, здесь добавлено ограничение на число дополнительных предложений, параметр ЯС* .

Значение NC* включает как число обычных предложений, так и число дополнительных предложений, но NCl& суммирует только дополнительные предложения.

Во втором разделе четвертой главы описывается стратегия глобальной функции в двойственной декомпозиции.

Рассмотрим задачу математического программирования с блочной структурой и связывающими переменными. Эту задачу можно представить в компактном виде

min сх + fT у

Dx + В у = h , (29)

х 2 0 , у € У с я"0 .

Применение леммы Фаркаша и теории двойственности приводит решение задачи (29) к двухуровневой схеме декомпозиции Бендерса.

На верхнем уровне решается ограниченная главная задача min г

z 2 (h - ßy)Tul+ fTу , i € Jp (30)

(h - By)7vJ £ 0 , j e Jr

nn

у € У с R 0 ,

здесь Jp и Jr подмножества вершин и направляющих векторов неограниченных ребер, соответственно, которые генерируются из решения подзадачи

шах V = (Ъ - Ву)ти

И и £ с . (31)

Подмножества 1р и ^обновляются в процессе решения задач верхнего (30) и нижнего (31) уровня.

Так же как и в прямой декомпозиции на шаге 2 схемы Бендерса необязательно решать задачу (31) до конца, получать оптимальное решение. Здесь достаточно выбирать вершины, удовлетворяющие критерию ввода строки и еще некоторым правилам, подобно сформулированным в Процедуре 1 для прямой декомпозиции. Такую операцию для схемы двойственной декомпозиции также назовем Процедурой 1.

Поэтому в схеме двойственной декомпозиции можно также применить Стратегию глобальной функции для генерирования строк в главную задачу.

В программной реализации тест для ввода строки кандидата записывается следующим образом

СЛ - Ву)ти1 > г - {ту + , (32)

здесь а1 текущее допустимое базисное решение подзадачи, г и у текущие переменные главной задачи, параметр , определяемый в программе.

В представляемом подходе предлагается генерировать дополнительные строки , если число обычных предложений

после решения подзадачи меньше чем максимального числа

предложений из подзадачи.

Для этой цели решается подзадача шах V = Ьти В и ^ с . (33)

При этом применяется следующий тест для кандитатов строк

Ь7и1 >2 + е1 , (34)

36

здесь £ текущее значение, переменной в задаче (31) после главного цикла.

Процедура 2 для генерирования дополнительных строк предложений может быть построена в форме Процедуры 1, в которой решение подзадачи (31) и тест для кандидатов (32) заменяются соотношениями (33) и (34), соответственно.

Вычислительные эксперименты показывают, что число главных циклов, общее время ввода-вывода и время решения существенно уменьшаются.

Предложенный подход имеет естественную экономическую интерпретацию, он также может рассматриваться с точки зрения методологии глобальной оптимизации.

В пятой главе рассматривается анализ задач оптимизации большой размерности методами агрегации.

Методы агрегации играют большую роль при решении и исследовании задач большой размерности . Однако, в большинстве научных работ агрегация рассматривается как метод решения задач оптимизации большой размерности. При таком подходе столбцы- и/или строки матрицы ограниченной исходной (большой) задачи разбиваются на группы, в которых формируется столбец и/или строка и из них создается агрегированная задача меньшей размерности. В итеративном процессе решается агрегированная задача, затем уточняются агрегированные столбцы и/или строки, и: так до. тех пор, пока не будет получено решение исходной задачи с заданной точностью. Агрегация при таком, подходе рассматривается локально, в "точке", т.е. при заданных заранее значениях параметров, . характеризующих условия задачи. Агрегированная., задача, полученная , в результате применения описанной процедуры, будет в .а^ак.ом-то .смысле наилучшим

приближением исходной задачи оптимизации в конкретной оптимальной точке.

Между тем цель агрегации состоит не столько в разработке еще одного способа численного решения конкретной задачи большой размерности, а прежде всего в создании интегрального агрегированного образа этой задачи, пригодного для некоторой области изменения параметров задачи. Такой подход к агрегации допускает много различных реализаций, как детерминированных, так и стохастических. В пятой главе рассматривается столбцевая и строчная агрегация для приближения задач линейного программирования большой размерности. При этом точность агрегации оценивается заданным допуском на отклонение функционалов исходной и агрегированной задач.

Цель данной главы состоит в том, чтобы заменить исходную задачу оптимизации большой размерности агрегированной задачей, при этом разность оптимальных значений функционалов исходной и агрегированной задач должна находиться в заданных пределах для некоторой области изменения параметров задачи. Если при изменении условий задачи оценка разности функционалов выходит за допустимые пределы, то создается новая агрегированная задача, лучше приближающая исходную задачу с изменившимися условиями.

В шестой главе предлагается использовать методы агрегирования для задач планирования в гибких производственных системах (ГПС).

Планирование в гибких производственных системах (ГПС) является сложной иерархической задачей со многими экстремумами. В научной литературе по ГПС внимание в основном уделяется задачам загрузки оборудования и построения расписаний. В

38

гораздо меньшем объеме рассматриваются вопросы планирования на заданный период времени с некоторым критерием оптимизации.

Сложность задачи планирования в ГПС состоит в том, что нужно не только выбрать величины партий деталей для обработки за данный период времени в соответствии с некоторым критерием оптимизации, но также определить их порядок обработки, т. е. найти такое расписание работ, чтобы уложиться в заданное время планирования.

В данной главе для решения задач планирования в ГПС предлагается использовать агрегирование в линейной оптимизационной модели и имитационную модель. Методы линейного программирования (ЛП) позволяют быстро и надежно получать решения достаточно больших задач ЛП и легко интерпретируются ЛПР. Оптимизационная модель дает возможность находить номенклатуру выпускаемых деталей на данный период планирования согласно критерию максимизации прибыли. Кроме того, эта модель разбивает детали на подпартии по технологическим маршрутам.

Решение, найденное в оптимизационной модели, уточняется с помощью имитационной модели. Прогонка оптимизационной модели с модифицированными параметрами может быть повторена, если имитационная модель показывает, что полученный производственный план недостижим за данный период времени.

В седьмой главе рассматриваются методы оптимизационного моделирования и агрегации в задачах планирования текстильного производства.

Составление экономического (оптимального) плана выпуска продукции промышленным предприятием на заданный период времени тоебует возможно более полного учета технологии производства, его внутренних резервов, обеспеченности различными видами

39

ресурсов, динамики функционирования, т. е. необходима разработка детализированной оптимизационной модели 'планирования производства*большой размерности. ' г' : г.

Однако даже тщательно разработанный оптимальный план выпуска продукции' на заданный период - времени практически не осуществим из-за влияния ' множества' непредвиденных ^факторов, например, недопоставок сырья, сбоев в работе оборудования и т.д. Проявление хозяйственной самостоятельности:' предприятий предполагает большую свободу в заключении договоров на поставку готовой продукции на основе прямых' хозяйственных: связей производителя и потребителей с учетом их' спроса, т. е. формирование "портфеля заказов" в большей, чем:прежде, степени подвержено влиянию рынка, а сами такие заказы -составляют изменяемую часть плана. ' 1 * ' ' ;

В настоящей главе рассматривается оптимизационная модель планирования' текстильного предприятия. Сначала разрабатывается детализированная модель планирования на заданный период времени (ка1к правило, год) с учетом динамики производства^разбивка интервала планирования на кварталы); Модель предусматривает удовлетворение основных плановых заданий" - . госзаказ, контрольные цифры. Полученное ; оптимальное решение считается базовым для производства. '»Затем происходит :поэтапная ° •корректировка и уточнение производственной базовой- программы в ' "Течекие планового периода вследствие накопления- дополнительных заказов, изменения поставок сырьевых ресурсов, колебания цен :на

• Нахождение скорректированного. плана производства при ■'изменении' параметров и условий' задачи необходимо выполнять в ''•'''оперативном 'режиме. '''Поэтому неэффективно решать и анализировать

40

каждый раз исходную оптимизационную задачу большой размерности. В данной работе предлагается корректировку и уточнение плана производства выполнять на основе агрегированной модели меньшей размерности. Для. оценки точности агрегирования используется подход, предложенный в пятой главе. На каждом этапе определения скорректированного плана находится оценка разности опимальных значений функционалов исходной и агрегированной задач. Если оценка разности выходит за принятый допуск, происходит переход к большой задаче, затем формируется новая агрегированная задача, лучше учитывающая изменившиеся условия, и т. д

В данном разделе описывается детализированная оптимизационная модель текстильного предприятия. Рассматриваются различные способы построения агрегированных моделей исходя из экономических соображений: агрегирование по времени, по взаимозаменяемым ресурсам, по группам однотипных машин в отдельных технологических процессах. Приводятся математические методы оценки функционала исходной задачи по решению агрегированной задачи.

В заключение формулируются основные результаты работы. В приложении рассматриваются вопросы программной реализации декомпозиционных методов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Разработана общая схема блочной факторизации для решения структурных задач оптимизации. Предложена и обоснована процедура преобразования локальных базисов при замене базисных столбцов. Доказывается невырожденность новой системы локальных

41

базисов, полученных в результате преобразования. Показывается применение предложенной схемы для решения задач динамического линейного программирования, динамических транспортных задач, динамических задач с запаздыванием, задач с блочно-диагональной структурой и связывающими ограничениями.

2. Разработан модифицированный вариант метода блочной факторизации, метод стратегии допустимых базисов (СДБ). Разработан модифицированный вариант метода декомпозиции, метод ключевых базисов (МКБ).

3. Сформулирована и доказана теорема о том, что методы СДБ и МКБ следуют в процессе решения по эквивалентным траекториям. Доказывается, что в методах СДБ и МКБ отсутствуют внутренние итерации, характерные для методов декомпозиции, и замедляющие сходимость декомпозиционных методов.

4. Разработан единый подход для анализа методов декомпозиции, блочной факторизации и симплекс-метода.

5. Предложен подход для построения црямых и двойственных методов декомпозиции, метод компаунд декомпозиции (МКД). Этот подход позволяет объединить некоторые полезные свойства методов декомпозиции, блочной фокторизации и симплекс-метода. Первое, исходная задача разбивается на главную задачу и подзадачи в процессе решения как в методах декомпозиции, тем самым давая возможность развязать исходную задачу и решать подзадачи по отдельности. Второе, в предложенном подходе траектория решения следует время от времени по ребрам и вершинам исходной задачи подобно методам блочной факторизации или симплекс-методу.

6. Показывается развитие подхода компаунд декомпозиции на нелинейный случай и применение к двойственной декомпозиции.

7. Построены прямые и двойственные алгоритмы декомпозиции

42

на основе метода глобальных функций (МГФ). В предлагаемом подходе подзадачи генерируют специальные дополнительные предожения согласно некоторому новому критерию, наряду с обычными предложениями для главной задачи. Это дает возможность существенно уменьшить число главных циклов, следовательно уменьшить число обменов между главной задачей и подзадачами.

8. Разработан метод агрегации для анализа и приближения задач линейного программирования большой размероности. Точность агрегации оценивается заданным допуском на отклонение функционалов исходной и агрегированной задач. Если при изменении условий задачи оценка разности функционалов выходит за допустимые пределы, то создается новая агрегированная задача, лучше приближающая исходную задачу с изменившимися условиями.

9. Показывается применение разработанной методологии по анализу и решению задач оптимизации большой размерности на практике при моделировании сложных производственных процессов.

ЛИТЕРАТУРА

1. Кривоножко В.Е., Пропой А. И. Метод последовательного улучшения управления в задачах динамического линейного программирования. Ч. I. II. - Изв. АН СССР, Техническая кибернетика, 1978, N3, 4, стр. 5-16, стр. 5-14.

2. Кривоножко В. Е. Об одном алгоритме разложения для задач линейного динамического программирования. - Изв. АН СССР, Техническая кибернетика, 1977, N 3, стр. 18-25.

3. Krivonozhko V.E., Propoi A.I. A Method for Linear Dynamic Programs with the use of Basis Matrices Factorization.

43

- Abstracts of the IX International Symposium on Mathematical Programming. Budapest, 1976.

5. Кривоножко В. E., Чеботарев С. П. О методе факторизации в задачах линейного динамического программирования. - Автоматика и телемеханика, 1976, N 7, стр. 80-90.

6. Кривоножко В.Е., Пропой А. И. 0 методе решения динамических транспортных задач. - Автоматика и телемеханика, 1979, N 12, стр. 133-145.

7. Кривоножко В. Е. - Методы факторизации для задач с блочно-треугольной структурой. - В сб. Математические методы в теории систем, Вып. 6, М., ВНИИСИ, 1980, стр. 68-87.

8. Krivonozhko, V.E. and Propoi, A.I. (1981) The simplex method for dynamic linear programs. In Large-Scale Li near Programming, G.B. Dantzig, ed., IIASA, Austria, pp. 299-363.

9. Большаков В.A., Кривоножко В.E., Пропой А. И., Ядыкин А. Б. Системы оптимизационного моделирования. - В сб.: Программное обеспечение систем оптимизации. М.: ВНИИСИ, 1982, стр. 3-16.

10. Гарусов В. Н., Кривоножко В. Е. Интерактивная система оптимизации производственной программы для промышленных предприятий (ППП СОЛМИ-ЕС). - В сб.: Программное обеспечение систем оптимизации. М.: ВНИИСИ, 1982, стр. 76-89.

11. Кривоножко В.Е., Пропой А. И., Тверской И. В. Методы блочной факторизации' для задач динамического линейного программирования. // М.: ВНИИСИ, препринт. 1987.

12. Кривоножко В. Е. Система программ для решения задач большой размерности методами декомпозиции. // М. , в сб. Анализ и оптимизация сложных систем, ВНИИСИ, 1987, стр. 38-50.

13. Кривоножко В. Е. Интерактивный анализ оптимизационных

44

моделей большой размерности. - В сб. : Задачи и методы оптимизационного моделирования. М.: ВНИИСИ, 1988, стр. 17-30.

14. Кривонояко В. Е. Система для интерактивного анализа оптимизационных моделей СИАМ. -Препринт, ВНИИСИ, Москва, 1988.

. 15. Кривоножко В. Е., Пропой А. И. Методы столбцевой и строчной агрегации в задачах линейного программирования большой размерности. - М.: ВНИИСИ, 1989. Вып. 4. стр. 21-32.

16. Krivonozhko V. Е. Development of solution methods for large-scale problems on the basis of decomposition and basis factorization. Unified approach. - Abstracts of the 14th IFIP Conference on System Modelling and Optimization. Heft 3, Leipzig, Germany, 1989, p. 39.

17. В. E. Кривоножко, А. И. Пропой. Агрегирование в задачах линейного программирования большой размерности. - Международная школа-семинар по методам оптимизации и их приложениям. Тезисы докладов, Иркутск, 1989, стр. 113.

18. Кривоножко В. Е., А. И. Пропой. Метод решения динамических задач оптимизации на основе агрегации. // Методы анализа и оптимизации систем, вып. 11, М. , ВНИИСИ, 1990 , стр. 7-15.

19. Кривоножко В. Е. , Шибаева Т. В. Методы агрегации в оптимизационных моделях планирования текстильного производства. - М.: ВНИИСИ, 1989. Вып. 4, стр. 32-44.

20. Кривоножко В. Е. Об эквивалентности траекторий решения в методах декомпозиции и блочной факторизации. - Известия РАН, Техническая кибернетика, N 4, 1991, стр. 196-214.

21. Krivonozhko V.Е. Primal and Dual Decomposition Methods for Large-Scale Optimization. - Abstracts of the 15th IFIP Conference on System Modelling and Optimization, v. 1, Zurich, Switzerland, 1991, pp. 154-155.

45

21. Krivonozhko V.E. On comparison of solution trajectories between Dantzig-Wolfe decomposition and basis factorization, Optimization Methods and Software, 1, 1992, pp. 311-337.

22. Krivonozhko V.E. Decomposition methods using compound proposals for large-scale optimization, in System Modelling and Optimization, P. Kail, ed., Springer-Verlag, 1992, pp. 231-240.

23. Krivonozhko V.E. Decomposition Methods for Large-Scale optimization. - Preprints of the IFAC Symposium "Large Scale Systems: Theory and Applications", Beijing, P.R. China, 1992, v. 1, pp. 137-142.

24. Krivonozhko V.E., Kalachev V.N. and Nemchinov B.V. Optimization Modelling for Production Planning in Flexible Manufacturing Systems. - Preprints of the IFAC Symposium "Large Scale Systems: Theory and! Applications", Beijing, P.R. China, 1992, v. 2, pp. 547-550.

25. Krivonozhko V.E. New strategies in decomposition methods. - Abstracts of the 16th IFIP Conference on System Modelling and Optimization, v. 2, Compiegne, France, 1993, pp. 665-667.

26. Krivonozhko V.E. Global function strategy in the decomposition approach. - Optimization Methods and Software, v.5, N 3, 1995, pp. 199-207.

27. Krivonozhko V.E. A development of solution methods for large-scale optimization. - Abstracts of the 15th International Symposium on Mathematical programming, Ann Arbor, USA 1994, p. 123.

28. Krivonozhko V.E. Decomposition and path following methods. - Abstracts of the 17th IFIP Conference on System Modelling and Optimization, v. 1, Prague, Czech Republic, 1995,

46

рр. 311-313.

29. В. Е. Кривоножко, Б. В. Немчинов, В. Н. Калачев. Задачи планирования в гибких производственных системах. - Автоматика и Телемеханика, N 6, 1995,. стр. 155-165.

Подписано в печать 1.10.96г. Заказ 64. Тираж 100. УОП ИЛА РАН 113035 Москва, Б,Ордынка, 21 .