Линейное программирование. Филькин Г.В. - 20 стр.

      Если одна из пар двойственных задач обладает оптимальным планом,
то и другая задача имеет оптимальный план (решение) причём значение их
целевых функций в точках оптимума равны, т.е. Zmin=Wmax или Zmax=Wmin.
      Если целевая функция одной из двойственных задач не ограничена на
множестве допустимых решений, то у другой задачи множество допустимых
решений пусто.
      Рассмотрим пару двойственных задач
      Пример.
      Z=2X1+7X2 → max
       ⎧− 2 X 1 + 3 X 2 ≤ 14
       ⎪
       ⎨ X1 + X 2 ≤ 8
       ⎪ X ,X ≥0
       ⎩      1    2

       Двойственная:
       W = 14 y1 + 24 y 2 + 12 y 3 → min
         ⎧− 2 y1 + y2 ≥ 2
         ⎪
         ⎨ 3 y1 + y2 ≥ 7
         ⎪ y ,y ≥0
         ⎩ 1 2


        Нахождение решений двойственных задач симплекс-методом.

      При решении какой либо задачи ЛП симплекс методом в симплексной
таблице находится информация, позволяющая сразу получить решение зада-
чи двойственной первоначальной.
      Для нахождения решения двойственной задачи необходимо сравнить
первоначальную и последнюю симплексные таблицы (в предположении, что
мы получили оптимальное решение). Оптимальное решение двойственной
задачи находится в строке ZJ-CJ, в тех клетках, где первоначально находи-
лись единичные (базисные вектора).
      Компоненты yi оптимального решения находятся как yi=Zj-Cj+Cj . По-
кажем решение двойственной задачи.
      Пример:
      Решить прямую и двойственную задачи симплекс методом.
      Z=X1+2X1-X3 – max
       ⎧− X 1 + 4 X 2 − 2 X 3 ≤ 12
       ⎪
       ⎨ X 1 + X 2 + 2 X 3 ≤ 17
       ⎪ 2X − X + 2X = 4
       ⎩     1     2       3

       X1, X2, X3 ≥0
                                      1    2    -1   0       0       -11
Базис        Сб             А0
                                     А1    А2   А3   А4      А5      А6
  А4          0             12       -1    4    -2   1       0        0
  А5          0             17       1     1    2    0       1        0
  А6         -14            4         2    -1    2   0       0        1

                                           19