2.6. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП – двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому.

Задача ЛП в канонической форме имеет вид:

максимизировать L(x) =                  (2.6.1)

при условиях

 ( )                           (2.6.2)

или                                         ,

 j = .

Предположим, что n m и ранг матрицы А равен m.

Двойственная задача к задаче (2.6.1), (2.6.2) записывается так:

минимизировать                    (2.6.3)

при условиях

 , , .                  (2.6.4)

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

 , i есть                           (2.6.5)

удовлетворяет всем ограничением (2.6.4).

Разложим вектор b по сопряженному базису

                                               .                      (2.6.6)

Решив систему (2.6.6), получим некоторое ее базисное решение { } iÎ , которое называется псевдопланом прямой задачи, так как для него может выполняться условие неотрицательности переменных .

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

Как известно, оценки для небазисных векторов определяется в соответствии с

 = , j = .                   (2.6.7)

Псевдоплан можно найти и независимо от двойственной задачи. Пусть { } i Î - произвольная система линейно-независимых векторов прямой задачи.

Выразим все небазисные векторы { } через базисные:

,                                    (2.6.8)

.                               (2.6.9)

Обозначим решение (2.6.9) через х₀. Тогда можно дать дополнительное определение псевдоплана: n-мерный вектор , для которого = при iÎ , и = 0 при j I_б, является псевдопланом тогда и только тогда, когда все 0,

j = .

Доказательство. Векторы { } i Î I_б, линейно независимы.

Поэтому можно вычислить такой y ={ }, для которого

 , i Î I_б               (2.6.10)

Тогда

С учетом (2.6.4) получим

 ,                   (2.6.11)

что и требовалось доказать.

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

Справедлив следующий признак оптимальности: если среди базисных компонентов псевдоплана Х нет отрицательных, то псевдоплан  Х={ } оказывается оптимальным решением прямой задачи.

Доведение. Имеет место такая цепочка равенств:

 .

Равенство (1) следует из (2.6.2), равенство (2) получено переменой порядка суммирования, равенство (3) следует из (2.6.10).

Так как

х_j = 0 при j ¹ I_б                                                                   (2.6.12)

то

                               (2.6.13)

Таким образом, , что и является признаком оптимальности планов х и у, если х  0 (теорема 2.5).

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

Пусть известен некоторый сопряженный базис {A_i}, и I_б которому соответствует псевдоплан х. Очевидно, А_j = , А₀ = . При этом в зависимости от знаков {x_i} и {x_ij} может иметь место один из трех случаев: 1) базисные компоненти х_i = х_i0 0 для всех i I_б; 2) среди х_i имеются отрицательные, причем  для некоторого i: х_i0<0, а все х_ij 0 j = 1, …, n; 3) псевдоплан содержит отрицательные компоненты х_i0<0, но для каждой из них среди элементов {х_ij}, j = 1, …, n , имеются отрицательные. В первом случае, как следует из достаточного признака оптимальности, псевдоплан х – оптимальное решение. Во втором случае задача не разрешима. В третьем случае можно перейти к некоторому новому сопряженному базису и, следовательно, к новому псевдоплану с меньшим значением L.

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

Каждая итерация содержит два этапа. На первом этапе выясняют, не  является ли  псевдоплан оптимальным планом прямой задачи, и если нет, то разрешима ли  задача. Для этого необходимо вычислить { }, i I_б и установить их знаки. Второй этап состоит в осуществлении элементарного преобразования — (одной итерации) метода полного исключения Жордана-Гауса, приводящего к новому псевдоплану с меньшим значением целевой функции.

Описание алгоритма. Задача ЛП должна быть задана в канонической форме (2.6.1), (2.6.2) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его {A_i}, i I_б . Разложим А₀ по векторам базиса А_і1, … ,А_іm в соответствии с (2.6.9) и найдем псевдоплан {х_i0}, i I_б прямой задачи.

Исследуем знаки {х_i0}. Если имеет место случай х_i0 0,  i I_б , то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {х_i0} вычисляем коэффициенты разложения векторов A_j по векторами сопряженного базиса {х_ij} в соответствии с (2.6.8).

Если для некоторого r такого, что х_r0<0, все х_rj 0 то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.

Если имеет место третий случай (то есть для каждого r такого, что х_r0<0, по крайней мере одна из компонент х_rj<0), то переходим к второму этапу. С этой целью составляют таблицу k-й итерации (аналогичную симплекс-таблице), которая состоит (m + 2) строк и (n+1)-го столбца(табл. 2.24).     

Столбец В_х таблицы, как обычно, содержит векторы {A_i} базиса псевдоплана х_k, а столбец А₀ – базисные компоненти псевдоплана{х_i0^(k) }. Строка (m + 1)-индексная, ее заполняют параметрами  , являющимися оценками векторов А_j:

 ,

величина – значение целевой функции при псевдоплане

 .

Итерацию k завершают заполнением главной части таблицы (от первой до (m + 1)-й строк).

 

 

 

Таблица 2.24.

Сии			С1	С2	…	Сj	…	Сn
	Bx	A0	A1	A2	…	Aj	…	An
C1	X1	X10	X11	X11	…	X1j	…	X1n
C2	X2	X20	X21	X22	…	X2j	…	X2n
…	…	…	…	…	…	…	…	…
Ci	Xi	Xi0	Xi1	Xi2	…	Xij	…	Xin
…	…	…	…	…	…	…	…	…
Cm	Xm	Xm0	Xm1	Xm2	…	Xmj	…	Xmn
	D	D0	D1	D2	…	Dj	…	Dn
	q		q1	q2	…	qj	…

На первом этапе (k + 1)-и итерации выясняют, имеет ли место первый, второй или третий случай.

В третьем случае переходим ко второму этапу. Сначала определяют вектор А_r, который необходимо вывести из базиса. Его индекс r определяют из условия

х_r0= ,                        (2.6.14)

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

Затем заполняют элементы { } (m + 2)-й строки, которые вычисляют по формуле

 ={ }.                     (2.6.15)

В строке  заполняют лишь те позиции, для которых x_rj<0. Вектор А_l , который должен быть введен в базис, находят из условия

 .

Определив направляющую строку r и столбец l, вычисляют элементы главной части таблицы (k + 1)-й итерации по рекуррентным соотношениям

                              (2.6.16)

где  – направляющий элемент преобразования.

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

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

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

Отметим некоторые важные свойства двойственного симплекс-метода.

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

Рассмотрим, например, типичную задачу минимизаци

                                   (2.6.17)

при условиях

 , и = ,                     (2.6.18)

,                                        (2.6.19)

.                                        (2.6.20)

Для задачи такого вида найти сразу начальный опорный план нельзя, и поэтому необходимо применить метод искусственных переменных и выполнить значительный объем вычислений. В то же время псевдоплан находится почти автоматически. Действительно, перейдем от (2.6.17) - (2.6.19) к эквивалентной задаче в расширенной форме,  введя свободные переменные x_n+1, x_n+2, … , x_n+m...

максимизировать                          (2.6.21)

при условиях

 .                           (2.6.22)

Запишем ограничения двойственной задачи

 j =,                                 (2.6.23)

 i =.                                       (2.6.24)

Из неравенств (2.6.23) - (2.6.24) видим, что поскольку решение  при i=1,m удовлетворяет всем ограничениям (2.6.23), то сопряженный базис образуют векторы  при свободных переменных. При этом начальный псевдоплан такой:

 , i = .

Итак, для задачи вида (2.6.17) – (2.6.18) пpи условии (2.6.20) применение двойственного симплес-метода оказывается предпочтительнее в сравнении с прямым.

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

Пример 2.9. Решить задачу линейного программирования двойственным симплекс-методом.

максимизировать (x₁+x₂)

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

2 x₁ + 11 x₂£38,

x₁ + x₂£7,

4 x₁ – 5 x₂ £5,

x₁, x₂ ³0,

или в расширенной форме

2 x₁ + 11 x₂ + 1 x₃ + 0 x₄ + 0 x₅ = 38,

1 x₁ + 1 x₂ + 0 x₃ + 1 x₄ + 0 x₅ = 7,

4 x₁ – 5 x₂ + 0 x₃ + 0 x₄ + 1 x₅ = 5,

x₁, … , x₅ ³0...

Двойственная задача записывается так:

минимизировать ( )

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

,

,

 

Выберем в качестве сопряженного базиса векторы {A₁, A₃, A₅}.

Тогда решением системы линейных уравнений

,

,

,

 

                                         является  

Подставив это решение в ограничения{A₂} и {A₄}, замечаем, что они также удовлетворяются, а потому {A₁, A₃, A₅} – сопряженный базис двойственной задачи.

Находим псевдоплан X₀ прямой задачи. Для этого решим систему уравнений
A₀ = A₁х₁₀ + A₃х₃₀ + A₅х₅₀. Отсюда х₁₀ = 7; х₃₀ = 24; х₅₀ = -23.

Вычисляем коэффициенты разложения { х_ij }

A₂ = A₁х₁₂ + A₃х₃₂ + A₅х₅₂

и находим

х₁₂ = 1; х₃₂ = 9; х₅₂ = -9.

Аналогично имеем

A₄ = A₁х₁₄ + A₃х₃₄ + A₅х₅₄

Решение этой системы уравнений: х₁₄ = 1; х₃₄ = -2; х₅₄ = -4.

Таблица. 2.25.

					↓
Cj				1	1	0	0	0
		Bx	A0	A1	A2	A3	A4	A5
	1	X1	7	1	1	0	1	0
	0	X3	24	0	9	1	-2	0
¬	0	X5	-23	0	-9	0	-4	1
		D	7	0	0	0	1	0
		q			0		¼

Первая итерация.

Определяем направляющую строку. Это строка X₅, так как X₅₀ = -23 < 0. Находим направляющий столбец, для чего заполняем строку . Направляющая строка А₂, так как . Следовательно, направляющий элемент Х₅₂ = -9. Выполнив первую итерацию симплекс-метода, получим таблицу 2.26.

Таблица 2.26.

Сj			1	1	0	0	0
	Ax	A0	A1	A2	A3	A4	A5
1	X1	40/9	1	0	0	5/9	1/9
0	X2	1	0	0	1	-6	1
1	X3	23/9	0	1	0	4/9	-1/9
	D	7	0	0	0	1	0

        Так как все элементы столбца А₀  х_і0 ³ 0, "и Î І_б, то найден оптимальный план, причем                                               

Целевая функция L_max = 7.