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

            ПЕРВАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ                            Пример 7.5. Имеем пару двойственных задач:
                                                                         Прямая задача             Двойственная задача
      Если одна из пары двойственных задач имеет опти-           Z = 3 x1 + 5 x 2 → max ,       W = 5 y1 + 2 y2 → min ,
мальный план, то и другая имеет оптимальный план,
причем экстремальные значения целевых функций равны:             ⎧ x1 + 2 x2 ≤ 5,                ⎧ y1 − y2 ≥ 3,
                                                                 ⎪                               ⎪
                            Z max = Wmin .                       ⎨− x1 + 3 x2 ≤ 2,               ⎨2 y1 + 3 y2 ≥ 5,
      Если одна из двойственных задач неразрешима вслед-         ⎪ x ≥ 0 , x ≥ 0.                ⎪ y ≥ 0 , y ≥ 0.
                                                                 ⎩ 1          2                  ⎩ 1          2
ствие неограниченности целевой функции на множестве                    Допустимое решение             Допустимое решение
допустимых планов, то система ограничений другой за-
дачи противоречива.
                                                                           X = (3,1) .
                                                                                     T
                                                                                                               (
                                                                                                           Y = 16 ,0 .
                                                                                                                 5
                                                                                                                      )
                                                                                                                      T


      Если совокупность ограничений одной из двойствен-                     Значение                         Значение
ных задач противоречива, то либо функция цели другой                      Z=3·3+5·1=14.                   W=5· 16 +2·0=16.
задачи не ограничена на множестве допустимых реше-                                                               5
ний, либо система ограничений другой задачи также про-                Этот пример показывает, что для рассматриваемых допусти-
тиворечива.                                                      мых решений значение целевой функции задачи на отыскание
      Экономическое содержание первой теоремы двойственно-       максимума меньше значения целевой функции двойственной за-
сти: если задача определения оптимального плана, максимизи-      дачи на отыскание минимума, что соответствует утверждению
рующего выпуск продукции, разрешима, то разрешима и задача       леммы 1:
определения оценок ресурсов. Причем стоимость выпущенной                                  Z ( X ) ≤ W (Y ) .              (7.8)
продукции, полученной при реализации оптимального плана,              Следует помнить, что здесь приведены допустимые решения,
совпадает с суммарной оценкой ресурсов. Совпадение значений      найденные методом проб. А лемма утверждает, что условие (7.8)
целевых функций для соответствующих планов пары двойствен-       справедливо для любых соответствующих допустимых решений
ных задач достаточно, чтобы эти планы были оптимальными.         Х и Y пары двойственных задач.
Оценки в этом случае выступают как инструмент балансирования          Обобщение материала данной главы приводит к практиче-
затрат и результатов. Двойственные оценки обладают тем свой-     скому выводу:
ством, что они гарантируют рентабельность оптимального плана,         Продуманный выбор допустимых планов прямой и двойст-
т.е. равенство общей оценки продукции и ресурсов, и обусловли-   венной задач позволяет оценить оптимальное значение целевой
вают убыточность всякого другого плана, отличного от опти-       функции ЗЛП. Эти планы определяют интервал, в котором за-
мального.                                                        ключено оптимальное значение целевой функции. Действитель-
      Двойственные оценки позволяют сопоставить и сбалансиро-    но, если выбранным допустимым планам пары двойственных за-
вать затраты и результаты производства.                          дач соответствуют одинаковые значения целевых функций, то
      На следующем примере покажем практическую ценность         (как мы говорили раньше) эти планы являются оптимальными со-
теоретических утверждений, приведенных в этой главе.             гласно лемме 2.
                                                                      В рассмотренном примере значения целевых функций за-
                                                                 ключены в пределах:
                                                                                       14 ≤ ( Z max = Wmin ) ≤ 16 .
                              103                                                                   104