Основные теоремы двойственности

Теорема 1. Для любых допустимых решений и прямой и двойственной задач линейного программирования справедливо неравенство

.

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

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

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

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

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

Кроме того, справедливы также следующие утверждения:

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

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

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

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

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

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

.

При имеем . Отсюда величина двойственной оценки численно равна изменению целевой функции при изменении соответствующего свободного члена ограничений на единицу.

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

Для любой итерации симплекс-таблицы прямой или двойственной задачи

Дата добавления: 2014-12-29