Одновременное решение прямой и двойственной задач

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

- обе задачи из пары двойственных имеют оптимальные решения;

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

Теорема 2.1 (1-я теорема двойственности). Если одна из задач взаимно двойственной пары разрешима, то разрешима и другая задача, при этом оптимальные значения целевых функций совпадают. Если целевая функция одной из задач не ограничена (сверху – для задачи максимизации, снизу – для задачи минимизации), то множество допустимых планов другой задачи пусто.

Из этой теоремы вытекает следующее

Следствие. Для того, чтобы допустимые решения и двойственной пары задач были оптимальны, необходимо и достаточно, чтобы значения целевых функций на этих планах совпадали: .

Теорема 2.2 (2-я теорема двойственности). Пусть имеется симметричная пара двойственных задач

, , (2.3)

, ; , .

Для того чтобы допустимые решения , являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:

, ; (2.4)

, . (2.5)

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

Пример 2.1.Для данной задачи составить двойственную, решить ее графическим методом и, используя вторую теорему двойственности, найти решение исходной задачи:

, .

Решение. Составим двойственную задачу

Решим эту задачу графическим методом. На рис. 6 изображены область допустимых решений задачи, нормаль линий уровня, линии уровня и оптимальное решение задачи .

Рис. 2.1.

,

_____________________

, ;

.

Подставим оптимальное решение в систему ограничений. Получим, что ограничения (1) и (4) выполняются как строгие неравенства:

Согласно второй теореме двойственности соответствующие координаты оптимального решения двойственной, т.е. исходной задачи, равны нулю: . Учитывая это, из системы ограничений исходной задачи получим

__________________

;

=7, =1; .

Ответ: 102 при .