Линейное программирование (стр. 8 из 8)

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

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

· каждому ограничению прямой задачи соответствует переменная двойственной задачи;

· каждому переменной прямой задачи соответствует ограничение двойственной задачи;

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

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

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

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

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

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

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

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

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

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

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

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

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

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