Для задачи, состоящей в максимизации функции
при условиях
сформулировать двойственную задачу.
Решение. Для данной задачи
,
В соответствии с общими правилами задача, двойственная по отношению к данной, формулируется следующим образом: найти минимум функции при условиях
Связь между решениями прямой и двойственной задач. Рассмотрим пару двойственных задач, образованную основной задачей линейного программирования и двойственной к ней. Исходная задача: найти максимум функции
(43)
при условиях
(44)
(45)
Двойственная задача: найти минимум функции
(46)
при условиях
(47)
Каждая из задач двойственной пары (43) – (45) и (46), (47) фактически является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.
Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.
|
|