Двойственность в ЛП.
Каждой задаче ЛП с любым типом ограничений можно поставить в соответствие другую задачу, которая называется двойственной по отношению к первой. Совместное рассмотрение таких пар задач позволяет исследовать влияние изменения переменных системы на значение целевой функции, проводить экономический анализ результатов расчета. Правила построения двойственной задачи: 1. Если прямая задача была задачей максимума, то двойственная будет задачей минимума, и на оборот; 2. Число переменных двойственной задачи равно числу ограничений прямой, и наоборот; 3. Коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи; 4. Свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи; 5. Матрица ограничений двойственной задачи получается транспонированием матрицы ограничений прямой, и наоборот; 6. Взаимно однозначное соответствие между переменными исходной задачи и ограничениями двойственной удовлетворяет следующему положению: А) если J-ая переменная неотрицательна в прямой задаче, то J-ое ограничение в двойственной задаче это неравенство типа Б) если I-ое ограничение прямой задачи неравенство типа I-ая переменная двойственной задачи неотрицательна; ограничениям равенствам отвечает переменная без ограничений в знаке.
Пример: Построить задачу, двойственную к данной:
Перепишем задачу изменяя ограничения типа
Двойственная задача имеет вид:
|
; переменным не имеющих ограничений в знаке соответствует ограничение равенство;
, то
. Получим задачу:
