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

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

    Опираясь на взаимосвязь между исходной и двойственной моделями,
можно построить еще один метод решения задачи линейного программи-
рования. Рассмотрим такой алгоритм решения исходной задачи, для кото-
рого на каждой итерации, за исключением последней, решение оказывает-
ся недопустимым вследствие невыполнения условий неотрицательности
переменных; соответствующее же решение двойственной задачи при каж-
дой такой итерации является допустимым. Эта идея лежит в основе так на-
зываемого двойственного симплекс-метода.
    В общем случае ЗЛП имеет вид:
                                                c T x � max
                                                Ax � b
                                                x�0
     c T � (c1 ,..., cn ) , x T � ( x1 ,..., x n ) , b T � (b1 ,..., bm ) , A � (aij ) , где i � 1, m , j � 1, n .
    Для решения задачи двойственным симплексным методом необходи-
мо задачу привести к каноническому виду. В стандартной симплекс про-
цедуре осуществляется перебор базисов B (невырожденных подматриц
исходной матрицы A ) следующим образом:
                                                                         � x�
    1. на каждой итерации метода вектор x B � �� �� , где x � B �1b является
                                                0                        � �
допустимым в исходной задаче, то есть Ax B � b , x B � 0 .
    2. на заключительной итерации, когда получена оптимальная точка,
кроме того оценки всех векторов A j неотрицательны � j � C BT B �1 A j � c j � 0 ,
j � 1, n или C BT B �1 A � y T A � AT y � c , то есть вектор y � C BT B �1 является до-
пустимым в двойственной задаче. При этом, он является решением двой-
ственной задачи. Заметим, что часть ограничений двойственной задачи
выполняется в виде равенств ( AT y ) � c j , j � I , где I – множество базисных
индексов (так как оценки базисных векторов равны нулю � j � 0 , j � I ).
Такие точки y называются базисными в двойственной задаче.
    Перебор          базиса осуществляется по правилу Жордана–Гаусса
( B 1 � ... � B * ). Все изменения в методе связаны с правилом выбора на-
правляющего элемента.
                                                      18