3.4.Применение теории двойственности к решению задач. Применение теоремы 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.

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

Пусть прямая задача имеет вид основной ЗЛП:

(3.31)

Двойственная к ней ЗЛП имеет вид:

; (3.32)

.

Предположим, что ЗЛП (3.31) имеет решение. Решения обеих задач могут быть записаны в виде (смотри доказательство теоремы 3.4):

= ; = ,

где = = ( , …, )

матрица, обратная для базисной подматрицы . Матрица подматрицы .

Из следствия 1 к теореме 3.4 :

, , (3.33)

откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы ( ) равна разности между левой и правой частями ограничений двойственной ЗЛП:

= . (3.34)

Пример 3.8. Решить следующую ЗЛП:

max (4Х₁ + Х₂ + 2Х₃ + 3Х₄);

Х₁ +2Х₂ + 3Х₃ – Х₅ + Х₇ = 50;

–3Х₂ +Х₃ + Х₄ +2Х₅ + 4Х₇ = 10;

4Х₂ + Х₅ + Х₆ – 1/2 Х₇ = 24;

.

Найти решение двойственной задачи.

Так как расширенная матрица

=

системы линейных уравнений ИЗ является К-матрицей, то ИЗ можно решить симплекс-методом. Результаты решения приведены в таблице:

			4		1		2	3		0		0		0
1 4 6	4 3 0	50 10 24	1 0 0		2 –3 4		3 1 0	0 1 0		–1 2 1		0 0 1		1 4 –1/2		25 – 6
	= 230			0		–2	13		0		2		0		16
1 4 2	4 3 1	38 28 6	1 0 0		0 0 1		3 1 0	0 1 0		–3/2 11/4 1/4		–1/2 3/4 1/4		5/4 29/8 –1/8
	= 242			0		0	13		0		5/2		1/2		63/4

На первой итерации получен оптимальный план ЗЛП (4.24).

= (1, 4, 2); = (38, 28, 6),

= (38, 6, 0, 28, 0, 0, 0); f( ) = 242.

Запишем ДЗ:

min(50Y1 + 10Y2 +24Y3); Y1 ≥ 4; 2Y1 – 3Y2 + 4Y3 ≥ 1; 3Y1 + Y2 ≥ 2.
Y2 ≥ 3; –Y1 +2Y2 + Y3 ≥ 0; Y3 ≥ 0; Y1 + 4Y2 – 1/2 Y3 ≥ 0.
не ограничены в знаке.

Последняя запись в формулировке ДЗ является избыточной, следовательно, ее можно отбросить.

Находим решение ДЗ по формуле 3.21.

= = (4, 3, 1) = (4, 3, 1/2)

или (3.33):

= (0 + 4, 0 + 3, + 0) = (4, 3, );

= 504 + 103 + 24  = 242.