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

Пусть имеется симметричная пара двойственных задач

Теорема 5.2. Для того чтобы допустимые решения Х= (х ₁, х ₂ ,..., х_п), Y= (y ₁, y ₂,..., y_т) являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:

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

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

F (X) = -2 x ₁+ 2 х ₂ + 10 х ₃ + 4 х ₄ + 2 х ₅→ min,

Решение. Составим двойственную задачу: Z (Y) = 2 у ₁ + 3 у ₂→ max,

Решим эту задачу графическим методом. На рис. 5.1 изображены область допустимых решений задачи, нормаль п = (2, 3) линий уровня, линии уровня 2 у ₁ + 3 у ₂= с и оптимальное решение задачи Y* = (3, 4).

Рис. 5.1.

2 у ₁=6 у ₁^*=3, у ₂^*=4.

Y ^*= (3,4).

Z (Y ^*)=2·3+3·4=18.

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

По второй теореме двойственности следует, что соответствующие координаты оптимального решения двойственной задачи, т.е. исходной задачи, равны нулю: х ₁^* = х ₂^* = х ₅^*=0. Учитывая это, из системы ограничений исходной задачи получим

Отсюда находим х ₃*= 1, х ₄* = 2. Окончательно записываем X *=(0,0,1,2,0).

Ответ: min F (X) = 18 при X* = (0, 0, 1, 2, 0).

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

F (X) = 5 x ₁+ 3 х ₂ + 4 х ₃ - х ₄ → max,

Решение. Составляем двойственную задачу Z (Y) = 3 y ₁ + 3 у ₂→min,

Решаем ее графическим методом (рис. 5.2). Для этого строим область допустимых решений (ОДР), нормаль п = (3, 3), линии уровня 3 у ₁ + 3 у ₂= с. Перемещаем линии уровня до опорной прямой. Оптимальное решение (точку Y*) найдем, решая совместно уравнения прямых L ₁ и L ₂ соответствующих первому

и третьему неравенствам. Таким образом, оптимальное решение Y*= (1,2), при котором min Z (Y)= 9.

Рис. 5.2.

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

Второе и четвертое ограничения выполняются как строгие неравенства, следовательно, вторая и четвертая координаты оптимального решения исходной задачи равны нулю: х ₂* = 0, х ₄* = 0. Учитывая это, первую и третью координаты оптимального решения X* находим при совместном решении уравнений-ограничений:

3 х ₁ = 3 => х ₁* = 1, х ₃* = 1.

Ответ: max F (X)= 9 при X* = (1, 0, 1, 0). •