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

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

                                    �a
                                    i �1
                                            ij   y j � �c j , j � 1, n ,     (7)

                                           � y i � 0 , i � 1, m .            (8)
     Из неравенств (7) – (8) видим, что поскольку решение yi � 0 при
i � 1, m удовлетворяет всем ограничениям (7), то базис двойственной зада-
чи образуют векторы An �1 , An � 2 ,..., An � m . При этом начальное решение систе-
мы имеет вид
                                           x n �i � �bi , i � 1, m .
    Итак, для задачи (1) – (3) при условии (4) применение двойственного
симплекс-метода оказывается предпочтительнее в сравнении с прямым.
    Двойственный симплекс-метод позволяет в процессе поиска добав-
лять новые дополнительные ограничения к уже найденному некоторому
промежуточному решению. Это важное его свойство широко использу-
ется при решении задач условной оптимизации (методы секущих плос-
костей).
    Пример:
    Пусть ЗЛП имеет вид:
                              2 x1 � x3 � min
                              x1 � x2 � x3 � 5
                              x1 � 2 x 2 � 4 x3 � 8
                              xi � 0 , i � 1,3 .
     Двойственная к ней задача имеет вид:
                              5 y1 � 8 y 2 � max
                              y1 � y 2 � 2
                              y1 � 2 y 2 � 0
                              � y1 � 4 y 2 � 1
                              y j � 0 , j � 1,2 .
    Перепишем исходную задачу, как задачу на максимум и приведем к
каноническому виду. А затем решим задачу двойственным симплекс-
методом.
                              � 2 x1 � x3 � max
                              � x1 � x 2 � x3 � u 4 � �5

                                                 21