Задача линейного программирования. Горячев Л.В. - 5 стр.

                                                                                                       5

мает вид:
                                             6y1 −4y2         +7y3 − max
                                               y1 −2y2         +y3 ≤ 1
                                            −2y1 −3y2              = −2
                                               y1 +2y2        +3y3 ≤ 1
                                             3y1 +y2               = −1
                                             2y1 −y2          −4y3 ≤ 1
                                              y2 ≥ 0          y3 ≥ 0
Условия неотрицательности y2 и y3 наложены так, как им отвечают в исходной задаче ограничения-
неравенства, а второе и четвертое ограничения имеют вид равенства, так как соответствующие им
переменные x2 , x3 не ограничены по знаку.
   Упражнения. Составить двойственные к следующим задачам:
                          1.   −x1 +x2 +x3 −max                    2.   2x1 +4x2 +x3 − min
                                x1 −3x2 +x3 ≥4                           x1 −2x2 +x3 ≤ 4
                               2x1 +x2 −2x3 ≥1                          2x1 +3x2 −x3 ≥ 2
                                x2 ≥ 0 x3 ≥ 0                            x1 ≥ 0 x3 ≥ 0
Каждая пара двойственных задач обладает рядом интересных свойств. В частности, если рассмот-
реть пару двойственных задач в симметричной форме, например, задачи (4)–(6), и (7)–(9), то от-
носительно их можно сформулировать следующие утверждения:

  1. Для любых допустимых планов x и y прямой и двойственной задач соответственно выполня-
     ется неравенство
                                         (c, x) ≤ (y, b)
     Доказательство: (c, x) ≤ (AT y, x) = (y, Ax) ≤ (y, b).

  2. Если x∗ и y ∗ — планы прямой и двойственной задачи соответственно и (c, x∗ ) = (y ∗ , b), то
     x∗ = y ∗ — оптимальные планы этих задач.
     Доказательство следует из предыдущего утверждения, так как (c, x) ≤ (c, x∗ ) = (y ∗ , b) ≤ (y, b).

  3. Если линейная форма одной пары двойственных задач неограничена, то множество планов
     других пусто.
     Доказательство: Пусть для определенности линейная форма задачи (7)–(9) неограниченна
     снизу, тогда существует последовательность планов {yi } такая, что lim(yk , b) = −∞. Учитывая
     утверждения, заключаем, что прямая задача не имеет ни одного конкретного плана.

  4. Если разрешима одна из пары двойственных задач, то разрешима и другая, при этом значения
     линейных форм задач на оптимальных планах совпадают.
     Доказательство: Опять рассмотрим пару двойственных задач в симметричной форме (4)–(6),
     и (7)–(9).
     Пусть x∗ — оптимальный план прямой задачи. Тогда в m x∗ согласно уже известной теореме
     Куна-Таккера, существуют такие вектора λ ≥ 0, v ≥ 0, что
                                    
                                    m                
                                                     n
                               c=         aTi λi −         vj ej    λ = (λ1 , λ2 , . . . , λm )T (∗)
                                    i=1              j=1
                                 (λ, b − Ax∗ ) = 0                  e = (e1 , e2 , . . . , en )T
                                    (v, x∗ ) = 0                    v = (v1 , v2 , . . . , vn )T
                                                                    ai = (ai1 , ai2 , . . . , ain )

     учитывая, что v ≥ 0, имеем AT λ ≥ 0, то есть вектор λ удовлетворяет условиям двойственной
     задачи. С другой стороны, умножая (∗) на x∗ скалярно, будем иметь (c, x∗ ) = (AT λ, x∗ ) =
     (v, x∗ ) = (λ, b). Таким образом, y ∗ ≡ λ есть оптимальный план двойственной задачи.
     Это утверждение вместе с пунктом 3 составляют первую теорему двойственности.