+ АпХл = bo
= Ь,
= ь2
D„Xn = Ьл
Х;>0, ; = 1,2.....п.
При необходимости ограничения в виде неравенств с помощью дополнительных переменных преобразуются в равенства.
Метод декомпозиции основан на определении крайних точек множеств {Xj DyXy = b;, Ху > О}, / = 1, 2, п. Для этого необходимо, чтобы каждое множество {XjXb,, Ху>0} было ограниченным. Это требование выполнимо всегда, поскольку при необходимости для любого множества / можно добавить искусственное ограничение IX. < М, где М - достаточно большое положительное число.
Обозначим через Yyt, k=l, 2, KJt крайние точки множества {XjDXb X. > 0}. Тогда можно записать
ху=ЕРЛ У-1.2,..., п,
где Р>4 > 0 для всех k и /*, причем = 1.
Теперь переформулируем исходную задачу в терминах крайних точек и получим так называемую главную задачу, определяемую следующим образом.
*1 к. к.
Максимизировать z = XCiyi.Pu +ZC2Y2*P2. + - + ZC»Y»»P«* при ограничениях
I A.Y»P" +I a2y..p*+-+=b0.
4=1 4=1 4 = 1
IP- =1-
4 = 1
P > 0 для всех k и j.
В главной задаче новыми переменными являются pJt. После того как будет найдено оптимальное решение Рд этой задачи, оптимальное решение исходной задачи
вычисляется путем обратных подстановок по следующей формуле.
Х,=1Р"Л , / = 1,2,...,п.
4 = 1
AiXi + D,X,
А2Х2 + D2X2
Может показаться, что для решения главной задачи необходимо предварительно найти все крайние точки Ylk, что является очень трудной задачей. К счастью, это не так.
При решении главной задачи с использованием модифицированного симплекс-метода (раздел 7.2) на каждой итерации нам необходимо определить вводимую и исключаемую переменные. Начнем с определения вводимой переменной. Зная текущий базис главной задачи (и, следовательно, матрицы Св и В"1), для любой небазисной переменной Pyt. имеем
-СвВ"Р-Сд,
j Х1к
Напомним: чтобы определить, какая из небазисных переменных Рук должна войти в базис, следует найти
гг1.-с,.к.= min {zjk-cjt\.
по всем] и к
Если z .к. -с/,1, <0 , тогда в соответствии с условием оптимальности задачи максимизации переменная р t, должна войти в базис. При выполнении обратного нера-
с;,4.. "Секрет" вычисле-
венства считаем, что оптимальное решение достигнуто. Теперь покажем, как можно вычислить разность zf
ний заключается в равенстве
min \zjk-ск} = mm\mm{zJk -с,}}
Это равенство вытекает из того, что каждое выпуклое множество, определяемое ограничениями DX; = Ьу, Ху > 0, имеет собственное независимое множество крайних точек. В соответствии с этим равенством мы можем найти разность 7ч,к. - cJ4. за два этапа.
1. Для каждого выпуклого множества {XjDXb, Х>0} определяем крайнюю точку Yjk„ на которой достигается минимум разностей zjk - cjk, т.е. zjk, -<: = mmk{zik-cjk}.
2. Далее определяем zt.k,-crk, =mmi{zjkt- с1к,}.
Из теории линейного программирования мы знаем, что конечное оптимальное решение ассоциируется с крайней точкой пространства решений. Поскольку каждое из множеств {X. D;X. = b;, Х; > 0} ограничено по определению, действия, выполняемые в п. 1, математически эквивалентны решению п задач линейного программирования вида
минимизировать wj = {z; - cj D.X. = Ъг Ху > 0}.
Фактически здесь целевая функция wj является линейной функцией от Ху (см. упражнение 7.4.1.8).
Таким образом, определение вводимой переменной pfk, в главной задаче сведено к решению п задач линейного программирования (меньшего размера) для вычис-
ления "вводимых" крайних точек Yy,t.. Такой подход не требует определения всех крайних точек всех п выпуклых множеств. После того как требуемая крайняя точка определена, нетрудно определить все элементы вектора Р . На основе этой информации мы можем определить исключаемую переменную. Далее с помощью модифицированного симплекс-метода вычисляем следующую обратную матрицу В"1.
Пример 7.4.1
Решим с помощью метода декомпозиции следующую задачу ЛП.
Максимизировать z = Здс, + 5х2 + х3 + х4
при ограничениях
х, + х2 + х3 + х4 < 40, 5x, + x2<12, х3 + х4> 5, х3 + 5х4 < 50, Х, х2, х3, х4 - 0.
Данную задачу можно разбить на две подзадачи, которым будут соответствовать следующие множества переменных:
X, = (xv х2) , Х2 = (х3, х4) .
Основную задачу можно записать следующим образом.
Подзадача 1 | Подзадача 2 | Начальное базисное решение |
Р" Р« - Р„, | р21 ргг - р2а:, | Х5 Хб х7 |
С,Уц C,Y12 C,YlK, | C2Y21 C2Y22 ... C,Y,, | 0 -М -М |
AiY,, A,Y12 ... A,Y,X] 1 1 ... 1 0 0 ... 0 | AaY21 AaY22 ... A,Y2Jt, 0 0 ... 0 1 1 ... 1 | 1 0 0 =40 0 1 0 =1 0 0 1 =1 |
С, = (3, 5), А, = (1, 1). Пространство решений D1X1 < Ьь 5xi +х2 < 12, xi, х2 >0. | C2 = (1, 1), Аг = (1. 1). Пространство решений 02Хг < b2: Хз + xi > 5, хз + 5xi < 50, Хз, Х4 > 0. | |
Отметим, что дополнительная переменная х5 введена для преобразования общего ограничения к виду равенства
jCj + х2 + х3 + х4 + хь = 40.
Эта переменная не входит ни в одну подзадачу, ее значение находится как часть решения главной задачи. Другие переменные в начальном базисе, хе и х7, являются искусственными переменными.