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

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

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

Пусть имеется пара двойственных задач I и II. Покажем, что для любых допустимых решений X = ху хТ ..., хп и Y = yv у2,..., ут исходной и двойственной задач справедливо неравенство

(6.7)

□ Умножив неравенства системы ограничений (6.2) исходной задачисоответственно на переменныеи сложив правые и левые части полученных неравенств, имеем

(6.8)

Аналогично преобразовав систему ограничений (6.5) двойственной задачипутем

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

(6.9)

Так как левые части неравенств (6.8) и (6.9) представляют одно и то же выражение, то в силу свойства

транзитивности неравенств получим доказываемое неравенство (6.7). ■

Теперь можно перейти к признакам оптимальности решений.

Достаточный признак оптимальности

Сформулируем теорему.

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

(6.10)

то– оптимальное решение исходной задачи I, а–оптимальное решение двойственной задачи II.

□ Пусть Х{ – любое допустимое решение исходной задачи I. Тогда применяя основное неравенство (6.7), получим i. Однако X, – произвольное решение задачи I, отсюда в силу равенства (6.10) следует, что т.е. X* – оптимальное решение задачи I. Аналогично доказывается, что решение оптимально для задачи II. ■

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

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

(6.11)

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

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

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

в силу основного неравенства теории двойственности (6.7) I, что противоречит условию неограниченности Г(Х). Следовательно, прив исходной задаче допустимых решений в двойственной задаче быть не может. ■

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

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

I.II.

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

При ограничениях:

Задача I об использовании ресурсов (см. параграф 1.2) и двойственная ей задача II были решены ранее (см. параграфы 5.2, 5.3) и получены оптимумы линейных функций 24 для задачи I и для задачи И, т.е. заключение первой части основной теоремы двойственности (6.11) верно. ► Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсовоказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах, равна затратам на ресурсы по "внутренним" (определяемым только из решения задачи) ценам. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством (6.7) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

Так, в задаче 6.2 оптимумы прибыли от продукции F и затрат на ресурсы Z ■ равны 24 руб.^[1], для всех остальных планов F(X)≤ 24, 7(У)>24.

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X" = (Хр х'2, ..., .г*) и получить максимальную прибыль (выручку) F либо продавать ресурсы по оптимальным ценам У* = {у, у, ..., у*т) и возместить от продажи равные ей минимальные затраты на ресурсы Zmjn.

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

I.II.

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

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

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

I.II.

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

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

• [1] Напоминаем, что в рассматриваемой задаче все цифры условные.