Линейное программирование. Азарнова Т.В - 31 стр.

                                                             Линейное программирование


      2. На заключительной итерации, кроме того, когда получена оптималь-
ная точка, оценки всех векторов A j неотрицательны
                            ∆ j =c TB B −1 A j −c j ≥0,     j =1, n
или
                            c TB B −1 A = y T A =AT y ≥c,
т.е. вектор y =c TB B −1 является допустимым в двойственной задаче, кроме то-
го, он является решением двойственной задачи. При этом заметим, что часть
ограничений двойственной задачи выполняется в виде равенств
(     )
 AT y j =c j , j ∈I , где I - множество базисных индексов (так как оценки ба-
зисных векторов всегда равны нулю ∆ j =0, j ∈I ). Такие точки y называют-
ся базисными в двойственной задаче.
      Рассмотрим примеры применения изложенной теории двойственности
к решению задач линейного программирования.

     Пример 3. На основании графического анализа двойственной задачи
исследовать разрешимость следующих задач и в случае разрешимости найти
оптимальное значение целевой функции.

      а) 6 x1 +9 x 2 +3 x 3 → min              б) 2 x1 + x 2 +2 x 3 → min
        −x1 +2 x 2 +x 3 ≥3                       −x1 +x2 +x3 =2
         3x1 +x 2 −x 3 ≥1                           x1 −3x 2 −2 x3 =1
            x1 ≥0, x 2 ≥0, x 3 ≥0                   x1 ≥0, x 2 ≥0, x 3 ≥0

                                 Решение.
     Двойственные к предложенным задачам относятся к задачам линейно-
го программирования в R 2 и поэтому их можно решать описанным в §1
графическим методом. Двойственная к задаче а) имеет вид:

                                     3 y1 +y 2 → max
                                      − y1 +3 y 2 ≤6
                                        2 y1 +y 2 ≤9
                                         y1 −y 2 ≤3
                                         y1, y2≥0




                                        33