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

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

Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений Х= (x ₁, x ₂,..., x_n) и Y = (у ₁ у ₂, ..., у_т) исходной и двойственной задач всегда справедливо неравенство

или . (6.7)

Достаточный признак оптимальности. Сформулируем теорему:

Если - допустимые решения взаимно двойственных задач, для которых выполняется равенство (6.10), то оптимальное решение исходной задачи I, а - двойственной задачи II.

Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны: . (6.11) Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

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

Рассмотрим примеры, подтверждающие справедливость первой теоремы двойственности.

Пример 6.2. Даны две взаимно двойственные задачи:

I. II.

при ограничениях при ограничениях

. .

Задача I об использовании ресурсов (см. § 1.2) и двойственная ей задача II были решены ранее (см. § 5.2-5.3) и получены оптимумы линейных функций F _max = 24для задачи I и Z _min = 24 для задачи II, т.е. заключение первой части основной теоремы двойственности (6.11) верно.

Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах с ₁, с ₂, ..., с_n равна затратам на ресурсы по "внутренним" (определяемым только из решения задачи) ценам у ₁, у ₂ ,..., у_т. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством (6.7) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

Так, в примере 6.2 оптимумы прибыли от продукции F _maxизатрат на ресурсы Z _minравны 24 руб., для всех остальных планов .

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану и получить максимальную прибыль (выручку) F _maxлибо продать ресурсы по оптимальным ценам и возместить от продажи равные ей минимальные затраты на ресурсы Z _min.

Пример 6.3. Даны две взаимно двойственные задачи:

I. II.

при ограничениях при ограничениях

. .

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

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

Пример 6.4. Даны две взаимно двойственные задачи:

I. II.

при ограничениях при ограничениях

. .

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