Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 32 стр.

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


      2. На заключительной итерации, кроме того, когда получена оптималь-
ная точка, оценки всех векторов A j неотрицательны
                            ∆ j =c TB B −1 A j −c j ≥0,       j =1, n
или
                            c TB B −1 A = y T A = A T 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 x3 → min                б) 2 x1 +x 2 +2 x3 → min
        −x1 +2 x 2 +x 3 ≥3                        −x1 +x2 +x3 =2
         3x1 +x 2 −x 3 ≥1                            x1 −3 x 2 −2 x 3 =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




                                        34