Сущность первой теоремы двойственности

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

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

• 1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max f (X) = ming (Y).
• 2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
• 3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
• 4. Обе из рассматриваемых задач имеют пустые допустимые множества.

Экономический смысл первой (основной) теоремы двойственности. План производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах с1, с2, …, сn равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам у1, у2, …, ут. Для всех же других планов X и Y обеих задач в соответствии с основным неравенством теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

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

Обратимся к паре задач.

Минимизировать Максимизировать.

L (X) = CTX L (Y)=BTY.

при.

AX=B ATYЈ C.

Xі 0.

Установим ряд частных выводов.

1. Пусть X и Y — некоторые планы задач. Тогда

L (X) = CTX Ј (ATY)TX = YTAX = YTB =BTY =(Y),.

двойственный экономический линейный т. е. для любых планов L (X)Ј (Y).

2. Пусть для планов X* и Y* имеет место равенство:

CTX*= BTY*.

Тогда:

CTX Ј BTY* = CTX*,.

т.е. при X=X* достигается максимум L (X). C учетом:

BTY і CTX* = BTY*.

делаем вывод об оптимальности планов X* и Y*.

3. Пусть линейная форма сопряженной задачи не ограничена снизу. Тогда существует план Y такой, что:

BTY < -M,.

где M > 0 сколь угодно велико. Если существует хотя бы один план X исходной задачи, то:

CTX Ј BTY < -M,.

чего при конечных значениях X не может быть.

Отсюда можно получить следующее утверждение:

Если одна из двойственных задач разрешима, то разрешима и сопряженная задача. При этом для оптимальных планов X* и Y* этих задач имеет место равенство значений целевых линейных форм:

CTX*= BTY*.

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

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