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

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

К контрольной работе

К началу К следующей лекции

К содержанию К титулу

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

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

,

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

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

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

или .

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

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

Экономический смысл первой теоремы двойственно­сти.

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

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