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

Двойственная задача — вспомогательная задача ЛП, формулируемая с помощью определённых правил непосредственно из исходной, или прямой задачи.

Прямая задача ЛП в стандартной форме:

максимизировать (минимизировать).

при ограничениях.

В состав включаются избыточные и остаточные переменные.

Для формулировки двойственной задачи расположим коэффициенты прямой задачи согласно схеме:

• · каждому ограничению прямой задачи соответствует переменная двойственной задачи;
• · каждому переменной прямой задачи соответствует ограничение двойственной задачи;
• · коэффициенты при некоторой переменной, фигурирующие в ограничения прямой задачи, становятся коэффициентами левой части соответствующего ограничения двойственной задачи, а коэффициент, фигурирующий при той же переменной в выражении для целевой функции прямой задачи, становится постоянной правой части этого же ограничения двойственной задачи.

Информация о других условиях двойственной задачи (направление оптимизации, ограничения и знаки двойственных переменных) представлена в таблице:

Прямая задача в стандартной форме.	Двойственная задача.
Целевая функция.	Целевая функция.	Ограничения.	Переменные.
Максимизация.	Минимизация.	Не ограничены в знаке.
Минимизация.	Максимизация.	Не ограничены в знаке.

Рассмотрим пример:

Прямая задача:

максимизировать.

при ограничениях.

Прямая задача в стандартной форме: максимизировать.

при ограничениях.

Двойственная задача:

Минимизировать.

при ограничениях:

(означает, что y1>0). y1, y2 не ограничены в знаке.