Соотношения двойственности 1,2.
Соотношение 1 (основное неравенство). Пусть 
– множество прямых планов, 
– множество двойственных планов. Для любого 
справедливо неравенство:
(10)
Доказательство. Возьмём произвольную пару 
и умножим основные ограничения задачи (1) слева на 
, а основные ограничения задачи (2) слева на 
имеем (учитывая, что 
):
, 
.
Вычитая из неравенства равенство, получим:
Таким образом, 
Ч.т.д.
Соотношение 2 (теорема двойственности). Для существования оптимального плана 
прямой задачи необходимо и достаточно существование 
оптимального плана двойственной задачи, причём оптимальные значения целевой функции одинаковы:
(11)
Доказательство. Достаточность. Пусть оптимальный план задачи (1). Можно считать, не ограничивая общности, его оптимальным базисным планом (выводы двухфазного метода), тогда 
оптимальный план задачи (2).
Необходимость. Пусть существует оптимальный план задачи (2). Считая эту задачу прямой и используя достаточность, можно сделать вывод, что у прямой задачи существует оптимальный план.
|
|
|
Ч.т.д.
Дата добавления: 2018-10-27; просмотров: 178; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!