Применение теоремы 3.5 к решению ДЗ.

Пример 3.6. Рассмотрим задачу: (задача решена в главе 2 P -метод.)

Ее решение . Найдем решение двойственной к ней задачи, используя теорему 3.5. Запишем двойственную задачу:

Применяем соотношения (3.30). Так как х₁^* = 3/2 > 0, то 3у₁^* + 4у₂^* + у₃^* = 2. Далее, так как 3х₁^* + х₂^* = 9/2 + 0 > 3, то у₁^* = 0, и так как х₁^* + 2х₂^* = 3/2 + 0 < 3, то у₃^* = 0. В итоге имеем:

3у₁^* + 4у₂^* + у₃^* = 2, у₁^* = у₃^* = 0,

т.е. вектор является решением ДЗ на основании теоремы 3.5. Вычислим , что соответствует утверждению теоремы 3.7.

Пример 3.7. Найти решение прямой и двойственной задач.

Прямая задача	Двойственная задача
max = 5Х1 + 12Х2 + 4Х3 Х1 + 2Х2 +Х3 ≤ 10 2Х1 – Х2 + 3Х3 = 8 Х2, 3≥ 0   Х 1 не ограничена в знаке	min = 10Y1 + 8Y2 Y1 +2Y2 = 5 2Y1 – Y2 ≥ 12 Y1 + 3Y2 ≥ 4 Y1 ≥ 0 У 2 не ограничена в знаке	(а) (б) (в) (г)

Двойственная задача содержит две переменные, т.е. ее можно решать графически (рис. 3.1).

Рис. 3.1

Как видно из рис. 3.1, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y₁ + 2Y₂ = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10Y₁ + 8Y₂ = const в направлении, противоположном вектору = (10; 8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:

Y₁ + 2 Y₂ = 5,

2 Y₁ – Y₂ = 12,

откуда

= 29/5; = -2/5 и = 54 .

Ипользуя теорему 3.5, находим решение исходной задачи. Так как > 0 и < 0, то оба ограничения прямой задачи имеют вид строгих равенств:

Х₁ + 2Х₂ + 3Х₃ = 10;

2Х₁ – Х₂ + 3Х₃ = 8.

Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 – 6/5 = 24/5 > 4), то = 0. Решаем полученную систему, откуда

= 26/5; = 12/5; = 0; f() = 54, 8.