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

Пусть взаимно двойственные задачи представлены в симметричной форме

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

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

Условия (7)-(8) не означают ничего другого, как только то, что или переменная обращается в ноль, или ограничение выполняется как равенство.

Доказательство:

· Достаточность:

Пусть имеются , и для них выполняются условия (7)-(8). Покажем, что это оптимальные решения своих задач.

Для этого просуммируем (7) и (8) по j и по i соответственно:

Левые части соотношений (9) и (10) равны, значит, равны и правые, а это критерии целевых функций

, – оптимальные решения.

· Необходимость:

Продолжая неравенство (11) с учетом (12), получим

Так как , то каждое неравенство в (13) выполняется как равенство. Рассмотрим первое из них

Преобразуем

В левой части (14) – сумма неотрицательных слагаемых. Такая сумма равна нулю только тогда, когда каждое слагаемое равно нулю

А это и есть соотношения (7).

Аналогично доказываются и соотношения (8).

Теорема доказана.

Экономическая интерпретация второй теоремы двойственности:

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

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

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

4. Если на оптимальном плане ресурс расходуется не полностью (), то его оценка равна нулю (), то есть изменение этого ресурса (малое) не влияет на критерий.

Соотношения (7) и (8) позволяют по оптимальному решению одной задачи найти оптимальное решение другой.

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

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

Решение системы уравнений (15) и удовлетворяют соотношениям (7) и (8). И если среди решений (15) есть допустимое решение двойственной задачи, то тогда выполняются все условия второй теоремы двойственности и оба эти решения будут оптимальные.

Пример:

Предприятие может работать по двум технологиям. При этом используются два типа ресурсов. Запасы ресурсов составляют 12 тонн и 4 литра соответственно. За 1 час работы по первой технологии расходуется 2 тонны первого ресурса и 1 литр второго, а за 1 час работы по второй технологии – 1 тонна первого ресурса. 1 час работы по первой технологии приносит доход 8 тыс. руб., а по второй – 3 тыс. руб. Суммарное время работы по технологиям должно составлять 6-часовую смену. Определить время работы по каждой технологии так, чтобы суммарный доход был наибольшим.

· Математическая модель

[час] – время работы по каждой технологии

· Построим двойственную задачу.

· Проверим, является ли оптимальным решение .

Для этого запишем соотношения дополняющей нежесткости (7). Подставим в эти соотношения компоненты решения

Решая данную систему уравнений, получим . Подставим в ограничения двойственной задачи. Первое ограничение не выполняется:

Мы получили, что найденное нами решение не является допустимым для двойственной задачи. Поэтому можно сделать вывод, что решение не является оптимальным решением исходной задачи.

· Предположим, что нам известно оптимальное решение прямой задачи , тогда найдем :

Таким образом, мы получили оптимальное решение двойственной задачи .