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

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

(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;

.

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

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

=

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

				–3			–1		–1/2	–
	= 230		–2
							–3/2 11/4 1/4	–1/2 3/4 1/4	5/4 29/8 –1/8
	= 242					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.