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

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

Пара двойственных ЗЛП в симметричной форме имеет следующий вид:

прямая задача

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

Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.

Прямая задача: сколько продукции j-го вида надо произвести, чтобы при заданных стоимостях единицы продукции, объемах имеющихся ресурсови нормах расходовмаксимизировать выпуск продукции в стоимостном выражении?

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

Чтобы из решения прямой задачи получить решение двойственной задачи нужно записать обе задачи в канонической форме:

прямая задача

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

Между переменными двойственных задач существует следующее соответствие:

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

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

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

Если прямая задача не имеет решения, то и двойственная ей тоже не имеет решения.

Пример 1.23

Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.3. Дать экономическую интерпретацию прямой и двойственной задач. Из решения прямой задачи (пример 1.6) найти решение двойственной задачи.

Решение

прямая задача ;

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

Экономическая интерпретация.

Прямая задача: сколько единиц продукции П_j надо произвести, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать прибыль от всей выпущенной продукции?

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

В примере 1.6 было получено решение прямой задачи графическим методом. Это ,.

Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:

прямая задача ;

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

Между переменными двойственных задач существует следующее соответствие:

Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так

,

,

,

,

.

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

Откуда . Таким образом,, или для двойственной задачи в симметричной форме. Причем.

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

Так как иотличны от нуля, то второй и третий ресурсы (сырье и электроэнергия) являются дефицитными. При этом, следовательно, наиболее дефицитным является второй ресурс (сырье). Поскольку, то ресурс первого вида (время работы оборудования) является избыточным. При увеличении сырья на 1 кг прибыль от всей выпущенной продукции увеличится на 3 руб., а при увеличении электроэнергии на 1 кВтч. прибыль от всей выпущенной продукции увеличится на 1 руб.