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

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

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

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

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

Для построения двойственной задачи необходимо пользоваться следующими правилами:

Если прямая задача решается на максимум, то двойственная — на минимум, и наоборот. В задаче на максимум ограничения-неравенства имеют смысл ≤, а в задаче минимизации - смысл ≥. Каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи. Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием. Свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот. Если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство. Если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Основное неравенство теории двойственности

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

Критерий оптимальности Канторовича (достаточный признак оптимальности)

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

Теорема существования оптимальных планов пары двойственных задач

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

Первая теорема двойственности

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

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

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

		…	…		…	…
|	|	|	|	|	|	|	|
		…	…		…	…	…
		…	…		…	…

Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на максимум, то пользуясь соответствием переменных:

и так далее.

Если прямая задача решается на минимум, то:

и так далее.

Вторая теорема двойственности (о дополняющей нежесткости)

Для того, чтобы планы  и  пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Эти условия называются условиями дополняющей нежесткости. Из них следует: если какое-либо неравенство системы ограничений одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю. Если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.

Экономически это означает, что если по некоторому оптимальному плану производства расход i-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а избыточный ресурс (используемый не полностью) имеет нулевую оценку.

Третья теорема двойственности

Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения ЗЛП, то есть:

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

При  имеем 

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