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) через х0. Тогда можно дать дополнительное определение псевдоплана: 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).
Пусть известен некоторый сопряженный базис {Ai}, и
Iб которому соответствует псевдоплан х. Очевидно, Аj =
, А0 =
. При этом в зависимости от знаков {xi} и {xij} может иметь место один из трех случаев: 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) или сведена к ней. Отыскивают сопряженный базис двойственной задачи и обозначают его {Ai}, i
Iб . Разложим А0 по векторам базиса Аі1, . ,Аіm в соответствии с (2.6.9) и найдем псевдоплан {хi0}, i Iб прямой задачи.
Исследуем знаки {хi0}. Если имеет место случай хi0 0, 
i Iб , то начальный псевдоплан является оптимальным планом прямой задачи. При наличии отрицательных компонент {хi0} вычисляем коэффициенты разложения векторов Aj по векторами сопряженного базиса {хij} в соответствии с (2.6.8).
Если для некоторого r такого, что хr0<0, все хrj 0 то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.
Если имеет место третий случай (то есть для каждого r такого, что хr0<0, по крайней мере одна из компонент хrj<0), то переходим к второму этапу. С этой целью составляют таблицу k-й итерации (аналогичную симплекс-таблице), которая состоит (m + 2) строк и (n+1)-го столбца(табл. 2.24).
Столбец Вх таблицы, как обычно, содержит векторы {Ai} базиса псевдоплана хk, а столбец А0 - базисные компоненти псевдоплана{х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)
В строке 
заполняют лишь те позиции, для которых xrj<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) к эквивалентной задаче в расширенной форме, введя свободные переменные xn+1, xn+2, . , xn+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. Решить задачу линейного программирования двойственным симплекс-методом.
максимизировать (x1+x2)
при ограничениях
2 x1 + 11 x2£38,
x1 + x2£7,
4 x1 - 5 x2 £5,
x1, x2 ³0,
или в расширенной форме
2 x1 + 11 x2 + 1 x3 + 0 x4 + 0 x5 = 38,
1 x1 + 1 x2 + 0 x3 + 1 x4 + 0 x5 = 7,
4 x1 - 5 x2 + 0 x3 + 0 x4 + 1 x5 = 5,
x1, . , x5 ³0...
Двойственная задача записывается так:
минимизировать (
)
при ограничениях
|
|
Выберем в качестве сопряженного базиса векторы {A1, A3, A5}.
Тогда решением системы линейных уравнений
|
|
|
является 
Подставив это решение в ограничения{A2} и {A4}, замечаем, что они также удовлетворяются, а потому {A1, A3, A5} - сопряженный базис двойственной задачи.
Находим псевдоплан X0 прямой задачи. Для этого решим систему уравнений
A0 = A1х10 + A3х30 + A5х50. Отсюда х10 = 7; х30 = 24; х50 = -23.
Вычисляем коэффициенты разложения { хij }
A2 = A1х12 + A3х32 + A5х52
и находим
х12 = 1; х32 = 9; х52 = -9.
Аналогично имеем
A4 = A1х14 + A3х34 + A5х54
Решение этой системы уравнений: х14 = 1; х34 = -2; х54 = -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 |
¼ |
||||||
Первая итерация.
Определяем направляющую строку. Это строка X5, так как X50 = -23 < 0. Находим направляющий столбец, для чего заполняем строку 
. Направляющая строка А2, так как 
. Следовательно, направляющий элемент Х52 = -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 ³ 0, "и Î Іб, то найден оптимальный план, причем 
Целевая функция Lmax = 7.
