11. Двойственная задача. Взаимодвойственность.

В силу всеобщности рассмотрим каноническую задачу в виде:

(1)

все выводы справедливы в силу теоремы 4 для произвольной линейной задачи. По параметрам задачи (1) построим некоторую другую линейную задачу:

(2)

Предположим, что у задачи (1) существует – оптимальный базисный план. Построим вектор (3)

Вектор называется вектором потенциалов для плана . Докажем, что он является оптимальным планом задачи (2)……

Задача (2) называется двойственной к задаче (1), а вектора – двойственными планами. Задачи (1) и (2) тесно связаны между собой.

Докажем, что если рассмотреть задачу (2), как прямую и построить для неё двойственную, то двойственная с точностью до эквивалентности совпадает с задачей (1). Это означает взаимодвойственность задач в линейном программировании.

Доказательство. Приведём задачу (2) к каноническому виду:

.

Совершим замену: . Следовательно, получаем: , (8)

Задача (8) является канонической задачей эквивалентной задаче (2). У неё вектор неизвестных , .

Её можно записать в виде:

(8*)

Построим для (8 ) двойственную, типа (2) . Имеем:

(9)

Из основных ограничений получаем:

Совершаем в задаче (9) замену: . Умножим целевую функцию на (-1), получим:

Как мы видим, двойственная задача возникает естественно из (1) и в силу всеобщности канонической формы можно сделать вывод: любой задаче линейного программирования можно поставить в соответствие некоторую другую задачу линейного программирования, двойственную к ней. Двойственность взаимнооднозначна с точностью до эквивалентности. Причём, эти задача тесно связаны между собой (одинаковые параметры ; одинаковое оптимальное значение и так далее).

Нетрудно показать (проделайте), что для задачи в нормальной форме (1.2.10 (20)) двойственной будет (симметрический вид) .

12. Соотношения двойственности 1,2.

(1)

(2)

Условия, которые будут доказываться ниже, справедливы для любой пары двойственных задач, но мы будем рассматривать пару (1), (2).

Соотношение 1 (основное неравенство). Пусть – множество прямых планов, – множество двойственных планов. Для любого справедливо неравенство:

(10)

Доказательство. Возьмём произвольную пару и умножим основные ограничения задачи (1) слева на , а основные ограничения задачи (2) слева на имеем (учитывая, что ):

, .

Вычитая из неравенства равенство, получим:

Таким образом,

Ч.т.д.

Соотношение 2 (теорема двойственности). Для существования оптимального плана прямой задачи необходимо и достаточно существование оптимального плана двойственной задачи, причём оптимальные значения целевой функции одинаковы:

(11)

Доказательство. Достаточность. Пусть оптимальный план задачи (1). Можно считать, не ограничивая общности, его оптимальным базисным планом (выводы двухфазного метода), тогда оптимальный план задачи (2).

Необходимость. Пусть существует оптимальный план задачи (2). Считая эту задачу прямой и используя достаточность, можно сделать вывод, что у прямой задачи существует оптимальный план.