Двойственная задача – вспомогательная задача ЛП, формулируемая с помощью определённых правил непосредственно из исходной, или прямой задачи.
Прямая задача ЛП в стандартной форме:
максимизировать (минимизировать)
при ограничениях
В состав включаются избыточные и остаточные переменные.
Для формулировки двойственной задачи расположим коэффициенты прямой задачи согласно схеме:
· каждому ограничению прямой задачи соответствует переменная двойственной задачи;
· каждому переменной прямой задачи соответствует ограничение двойственной задачи;
· коэффициенты при некоторой переменной, фигурирующие в ограничения прямой задачи, становятся коэффициентами левой части соответствующего ограничения двойственной задачи, а коэффициент, фигурирующий при той же переменной в выражении для целевой функции прямой задачи, становится постоянной правой части этого же ограничения двойственной задачи.
Информация о других условиях двойственной задачи (направление оптимизации, ограничения и знаки двойственных переменных) представлена в таблице:
Прямая задача в стандартной форме.
Двойственная задача
Целевая функция
Целевая функция
Ограничения
Переменные
Максимизация
Минимизация
Не ограничены в знаке
Минимизация
Максимизация
Не ограничены в знаке
Рассмотрим пример:
Прямая задача:
максимизировать
при ограничениях
Прямая задача в стандартной форме:
максимизировать
при ограничениях
Двойственная задача:
минимизировать
при ограничениях:
(означает, что y1>0). y1, y2 не ограничены в знаке.
