Математическое программирование (линейное программирование). Киселева Э.В - 50 стр.

  Прямая задача                Двойственная задача              то Х* и Y* являются оптимальными планами соответст-
  Z = сX → max ,                  W = Yb → min,                 вующей пары двойственных задач.
      AX ≤ b ,                         YA ≥ c ,         (7.5)        Пусть Х* и Y*– допустимые планы пары двойственных задач
       X ≥ 0.                           Y ≥ 0.                  (7.5). Необходимо доказать, что если для них выполняется усло-
                                                                вие (7.7), то эти планы оптимальны. (Напомним, что план Х* бу-
    Каждая из задач двойственной пары является самостоятель-    дет оптимальным тогда и только тогда, когда сХ ≤ сХ * для лю-
ной ЗЛП и может быть решена независимо одна от другой. В то     бого допустимого плана Х прямой задачи.)
же время, решив одну из задач симплекс-методом, мы легко мо-         Рассмотрим произвольный допустимый план Х прямой зада-
жем найти решение двойственной к ней задачи.                    чи. Тогда в соответствии с леммой 1 и условием (7.7) имеем:
    Существование зависимости между решениями прямой и                                    cХ ≤ Y * b = cХ * ,
двойственной задач характеризуется сформулированными ниже
                                                                откуда сХ ≤ сХ * , т.е. Х*– оптимальный план прямой задачи.
леммами и теоремами двойственности.
    Лемма 7.1. Для любых допустимых планов Х и Y пары               Аналогично доказывается оптимальность плана Y*. Лемма 2
двойственных ЗЛП справедливо соотношение:                       является критерием оптимальности для пары двойственных
                                                                ЗЛП. Согласно этой лемме, если среди допустимых планов пары
                         cX ≤ Yb.                       (7.6)
                                                                двойственных задач найдутся планы Х* и Y*, для которых
    Так как Х и Y– допустимые планы, то
                        AX ≤ b     и   Y ≥ 0,                                                сХ * = Y * b ,
                                                                    *   *
отсюда                                                          то Х и Y – оптимальные планы пары двойственных задач.
                           YAX ≤ Yb .                               Пример 7.4. Для пары двойственных задач:
    Аналогично из того, что YA≥ c и X ≥ 0, следует:             Z = 3 x1 + 2 x 2 → max ,       W = 4 y1 + 3 y2 + 3,5 y3 → min ,
                          YAX ≤ cХ .                            ⎧ x1 + x2 ≤ 4 ,
    Таким образом, имеем:                                       ⎪ x ≤ 3,                            ⎧ y1 + y2 ≥ 3,
                        cX ≤ YAX ≤ Yb ,                         ⎪ 1                                 ⎪
                                                                ⎨                                   ⎨ y1 + y3 ≥ 2 ,
что и требовалось доказать.                                     ⎪ 2x  ≤ 3 ,5 ,
     Доказательство для несимметричной пары двойственных за-                                        ⎪ y ≥ 0, y ≥ 0, y ≥ 0,
                                                                ⎪⎩ x1 ≥ 0 , x2 ≥ 0 ,                ⎩ 1          2   3
дач проводится аналогично.
                                                                 X = (3,1) и Y = (2 ,1,0 ) являются допустимыми планами, для ко-
                                                                            T
     Неравенство cX ≤ Yb называют основным неравенством
в теории двойственности. Его экономический смысл, например,     торых Z ( X ) = W (Y ) = 11 . Тогда согласно лемме 2 допустимые
для производственной задачи выпуска продукции, заключается в
                                                                планы X и Y являются оптимальными планами пары двойствен-
том, что при любом допустимом плане производства Х общая
                                                                ных задач.
стоимость продукции Z(X) не больше суммарной оценки ресурсов
                                                                    Экономическая интерпретация леммы 2: планы производст-
W(Y), отвечающей любому допустимому вектору оценок Y.
                                                                ва и оценки ресурсов являются оптимальными, если стоимость
     Лемма 7.2. Если для некоторых допустимых планов Х*
   *                                                            всей продукции и суммарная оценка ресурсов совпадают.
и Y пары двойственных задач выполняется условие:
                          cX * = Y * b ,                (7.7)

                                 101                                                                   102