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

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

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

или . (7.7)

Доказательство. Умножив неравенства системы ограничений (7.2) прямой задачи соответственно на переменные y₁, ¼, y_m и сложив правые и левые части полученных неравенств, имеем

. (7.8)

Аналогично преобразовав систему ограничений (7.5) двойственной задачи путем умножения обеих частей неравенства на переменные х₁, ¼, х_n и последующего их сложения, получим

. (7.9)

Так как левые и правые части неравенств (7.8) и (7.9) представляют одно и то же выражение , то в силу свойства транзитивности неравенств получим доказываемое неравенство (7.7).À

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

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

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

, (7.10)

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

Доказательство. Пусть - любое допустимое решение прямой задачи I. Тогда на основании основного неравенства (7.7) получим . Однако - произвольное решение задачи I, отсюда в силу равенства (7.10) следует, что , т.е. - оптимальное решение прямой задачи I. Аналогично доказывается, что решение оптимально для задачи II.À

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

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

, f_max = g_min. (7.11)

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

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

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

Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах с₁, с₂, ¼, с_n, равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам y₁, ¼, y_m. Для всех же других планов и обеих задач в соответствии с основным неравенством (7.7) теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

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

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

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

При приведении каждой из взаимодвойственных задач к каноническому виду в систему ограничений прямой задачи I (7.2) вводят m неотрицательных переменных x_n₊₁, x_n₊₂, ¼ x_n₊_m, а в систему ограничений двойственной задачи II – n неотрицательных переменных y_m₊₁, y_m₊₂, ¼ y_m₊_n.

Системы ограничений каждой из взаимодвойственных задач примут вид:

(7.12)

(7.13)

Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (табл. 7.2).

Таблица 7.2

Переменные прямой задачи I
Первоначальные	Дополнительные
	(7.14)
Дополнительные	Первоначальные
Переменные двойственной задачи II

Теорема 2 (примем без доказательства). Положительным (ненулевым) компонентам оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1, 2, ¼, m и j = 1, 2, ¼, n:

если > 0, то = 0;

если > 0, то = 0,

и аналогично,

если > 0, то = 0;

если > 0, то = 0.

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

Рассмотренная теорема является следствием следующей теоремы.

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

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

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

. (7.15)

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