Элементы теории двойственности. Чернышова Г.Д - 20 стр.

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

                                             �c
                                              j �1
                                                         j    x j � min                (1)

при условиях
                                              n

                                             �a
                                              j �1
                                                         ij   x j � bi , i � 1, m ,    (2)

                                             x j � 0,                                  (3)
                                             где c j � 0 , j � 1, n .                  (4)
    Для решения задачи такого вида найти сразу начальную базисную до-
пустимую точку невозможно, и поэтому необходимо применить метод ис-
кусственного базиса и выполнить значительный объем вычислений. Пока-
жем, что в этом случае удобно использовать двойственный симплекс-метод.
    Действительно перейдем от (1) – (3) к эквивалентной задаче в расши-
ренной форме, введя дополнительные переменные x n �1 , x n� 2 ,..., xn � m .
                                                     n
                                             � � c j x j � max                         (5)
                                                  j �1

при условиях
                     n

                    �a
                     j �1
                            ij   x j � x n �i � bi , i � 1, m , x j � 0 , j � 1, n .   (6)

                                                         20