Двойственность в Линейном Программировании

Неравенства, соединенные стрелочками, будем называть сопряженными.
Содержательная постановка двойственной задачи: найти такой набор цен (оценок) ресурсов Y = (y1, у2 ..., уm), при котором общие затраты на ресурсы будут минимальны при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Цены ресурсов у1, у2 ..., уm в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен с1, с2 ..., сn на продукцию, известных, как правило, до начала производства цены ресурсов у1, у2 ..., уm являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.
Связь прямой и двойственной задач состоит, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.

Двойственность является фундаментальным понятием в теории линейного программирования. Основные результаты теории двойственности заключены в двух теоремах, называемых теоремами двойственности.

Первая теорема двойственности.

Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, (*) = (*), где х*, у* - оптимальные решения задач I и II

Вторая теорема двойственности.

Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Это основная теорема двойственности. Другими словами, если х* и у* - допустимые решения прямой и двойственной задач и если cTx*=bTy*, то х* и у* – оптимальные решения пары двойственных задач.

Третья теорема двойственности. Значения переменных yi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений - неравенств прямой задачи на величину целевой функции этой задачи:

• Линейное и Нелинейное Программирование
• Целочисленное Линейное Программирование
• Решение Задачи Линейного Программирования
• Двойственная Задача Линейного Программирования
• Решение Задач Нелинейного Программирования