Ь) Максимизировать г = хг + 5х2 - 2х3 при ограничениях

4*! + 2х2 + 2х3 < 26, + Здс2 + 4х3> 17, О < х, < 2, 0 < х2 < 3, 0 < х3 (х3 сверху не ограничена).

7.4. МЕТОД ДЕКОМПОЗИЦИИ

Рассмотрим разработку производственного плана предприятия, состоящего из нескольких подразделений. Хотя каждое подразделение имеет собственные производственные возможности и соответствующие ограничения, производственные планы отдельных подразделений обобщаются на уровне управления предприятием. Таким образом, результирующая модель рассматриваемого предприятия будет содержать ограничения двух типов: общие, соответствующие уровню всего предприятия, и независимые, отображающие производственные ограничения отдельных подразделений. На рис. 7.5 показана структура ограничений для п подразделений. Отсутствие общих ограничений означает, что все подразделения независимы.

Метод декомпозиции предлагает эффективный вычислительный алгоритм решения задач со структурой ограничений, подобной показанной на рис. 7.5, путем разбиения исходной задачи на п подзадач, которые решаются независимо друг от друга. Вместе с тем отметим, что применение этого метода особенно оправдано, когда расчеты выполняются на вычислительном устройстве с ограниченной скоростью выполнения операций и ограниченным объемом памяти. Сегодня, когда вычислительная техника имеет огромную (по сравнению с недавним прошлым) производительность, необходимость в методе декомпозиции не так очевидна. Несмотря на это мы рассмотрим данный метод, поскольку он представляет интерес в теоретическом плане.

Общие ограничения

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

Подразделение 1

Подразделение 2

Подразделение л

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

Математическую модель, к которой применяется метод декомпозиции, запишем в следующем виде.

Максимизировать г = С;Х, + С2Х2 + ... + СлХп

при ограничениях

+ АпХл = 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, в главной задаче сведено к решению п задач линейного программирования (меньшего размера) для вычис-