Основные теоремы двойственности и их экономическое содержание

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

.

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

Первая теорема двойственности дает возможность в процессе решения одной задачи вместе с тем находить план второй.

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

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

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

(3.9)

.

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

(3.10)

Для решения задач симплексным методом необходимо свести их к канонической форме, для чего у системы ограничений задач (3.9) и (3.10) необходимо ввести соответственно m и n неотъемлемых переменных. Поставим ограничением каждой задачи в соответствие переменные ее двойственной задачи.

Аналогично:

Получили такое соответствие между переменными сопряженных задач:

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

Следующая теорема в литературе, как правило, имеет название теоремы о дополняющей нежесткость.

Теорема (вторая теорема двойственности для симметричных задач). Для того, чтобы планы X^* и Y^* соответствующих сопряженных задач были оптимальными, необходимо и достаточно, чтобы выполнялись условия дополняющей нежесткости:

(3.11)

. (3.12)

Очевиднее взаимосвязь между оптимальными планами прямой и двойственной задач устанавливает следствие второй теоремы двойственности.

Следствие. Если в результате подстановки оптимального плана одной из задач (прямой или двойственной) в систему ограничений этой задачи i -тое ограничение выполняется как строгая неравенство, то соответствующая i -тая компонента оптимального плана сопряженной задачи равняется нулю.

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

Экономическое содержание второй теоремы двойственности относительно оптимального плана Х^* прямой задачи. Если для изготовления всей продукции в объеме, который определяется оптимальным планом Х^*, затраты одного i -того ресурса строго меньши его общего объем , то соответствующая оценка такого ресурса (компонента оптимального плана двойственной задачи) будет равнять нулю, т.е. такой ресурс при данных условиях для производства не является «ценным».

Если же затраты ресурса равняются его имеющемуся объему , т.е. его использовано полностью, то он есть «ценным» для производства, и его оценка будет строго больше нуля.

Экономическое толкование второй теоремы двойственности относительно оптимального плана Y^* двойственной задачи: в случае, если некоторое j- тое ограничение выполняется как неравенство, т.е. все затраты на производство единицы j- го вида продукции превышают его цену с_j, производство такого вида продукции есть нецелесообразным, и в оптимальном плане прямой задачи объем такой продукции равняется нулю.

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

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

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

(3.13)

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

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

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

(3.14)

(3.15)

(3.16)

имеем новую задачу, где заменено на . Обозначим через оптимальный план новой задачи. Для определения не нужно решать новую задачу линейного программирования, а достаточно воспользоваться формулой , где – оптимальный план задачи (3.14-3.16).