Eng | Rus | Ukr
Исследование операций
24.12.2008

<< prev | ^up^ | next >>

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 = , А= . При этом в зависимости от знаков {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, "и Î Іб, то найден оптимальный план, причем                                               

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

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004