1.4. Двойственные задачи линейного программирования

Любой задаче линейного программирования можно поставить в соответствие другую задачу, сформулированную по стандартным правилам таким образом, что в ходе решения одной из них решается и другая задача. Эта пара названа двойственной (сопряженной) парой задач. В каждой такой паре имеется прямая и двойственная задачи, причем, если прямой считать двойственную, то ей соответствует первая.

1.4.1. Построение двойственной задачи

Рассмотрим обобщенную формулировку двойственной задачи линейного программирования, которая применима к любой форме представления прямой задачи и основывается на следующих правилах.

1. Число переменных в двойственной задаче равно числу основных ограничений в прямой задаче.

2. Матрица коэффициентов системы ограничений двойственной задачи получается из матрицы коэффициентов основной системы ограничений прямой задачи путем транспонирования.

3. Система основных ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы основных ограничений прямой задачи.

4. Свободными членами системы ограничений двойственной задачи являются коэффициенты функции цели прямой задачи.

5. Двойственная задача решается на минимум, если целевая функция прямой задачи задается на максимум, и наоборот.

6. Коэффициентами функции цели двойственной задачи служат свободные члены системы ограничений прямой задачи.

7. Если переменная прямой задачи , то ое условие системы ограничений двойственной задачи является неравенством, если любое число, то ое условие двойственной задачи представляет собой уравнение.

8. Если ое соотношение прямой задачи является неравенством, то соответствующая оценка ого ресурса – переменная , если ое соотношение представляет собой уравнение, то переменная двойственной задачи любое число.

В качестве примера построения двойственной задачи для данной прямой задачи рассмотрим задачу рационального использования ресурсов, которая имеет вид:

,

Необходимо найти план выпуска продукции из имеющихся в наличии ресурсов и нормативов затрат сырья на изготовление продукции, реализовав которую предприятие получит максимальную прибыль.

Выпишем теперь для этой задачи двойственную согласно рассмотренных выше правил составления двойственных задач.

,

Здесь необходимо определить двойственную оценку единицы каждого вида ресурсов , чтобы при заданных объемах ресурсов , прибыли , нормах расхода ресурсов минимизировать оценку всех ресурсов предприятия, затраченных на выпуск произведенной продукции.

Система ограничений двойственной задачи показывает, что двойственная оценка всех ресурсов, затраченных на выпуск единицы продукции ого вида, должна быть не меньше прибыли, получаемой при реализации единицы продукции ого вида.

Решение прямой задачи дает оптимальные объемы выпуска продукции предприятием, а решение двойственной – оптимальную систему двойственных оценок ресурсов, используемых для изготовления производимой продукции.