2. Связь между решениями прямой и двойственной задач

Если основная задача линейного программирования имеет оптимальный план Х*, то Y*= C_δ ^.является оптимальным планом двойственной задачи. ЗдесьC_δ - вектор-строка коэффициентов целевой функции при базисных переменных оптимальной симплекс-таблицы прямой задачи, а - матрица обратная матрице, составленной из компонентов векторов, входящих в последний базис, при котором получен оптимальный план. Если прямая задача приведена к единичному базису при неотрицательных свободных членах уравнений, вычисление обратной матрицы не требуется, так какбудет состоять из столбцов оптимальной симлекс-таблицы, полученных на месте единичных столбцов исходной таблицы.

Пример 1.

Задана прямая задача:

х₁, х₂≥0

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

Решение:

Прежде всего третье ограничение умножим на "-1", так как оно имеет знак «≥». Это ограничение примет вид

-5х₁+3х₂-6х₃≤-19

Матрица из коэффициентов при неизвестных в ограничениях будет:

Запишем транспонированную к ней матрицу:

Тогда двойственная задача запишется:

у₁, у₃≥0

Так как в прямой задаче второе ограничение имеет знак "=", то переменная y₂ не имеет ограничения на знак. Третье ограничение двойственной задачи имеет знак "=" так как переменная х₃ не имеет ограничения на знак.

Пример 2.

Прямая задача

х₁, х₄≥0

Двойственная задача

	Баз. вект	Сбаз	А0	3	4	1	6	0
				А1	А2	А3	А4	А5
	А3	1	3	3	-1	1	3	0
←	А5	0	5	1	3	0	-1	1
			3	-1	-5	0	-3	0
					↑

	Баз. вект	Сбаз	А0	3	4	1	6	0
				А1	А2	А3	А4	А5
←	А3	1	14/3	10/3	0	1	8/3	1/3
	А2	4	5/3	1/3	1	0	-1/3	1/3
			34/3	5/3	0	0	-14/3	5/3
							↑

↑

Баз. вект	Сбаз	А0	3	4	1	6	0
			А1	А2	А3	А4	А5
А4	6	7/4	5/4	0	3/8	1	1/8
А2	4	9/4	3/4	1	1/8	0	3/8
		78/4	15/2	0	7/4	0	9/4

Из последней таблицы получим оптимальный план:

Х^опт=(0, 9/4, 0, 7/4);

Данные этой же таблицы используются для определения оптимального решения двойственной задачи.

Вектор С^опт=(С₄, С₂)=(6,4). Матрица А_х состоит из векторов А₄ А₂ , взятых из ограничений по которым составляется двойственная задача:

А_х=( А₄ А₂₎₌

Обратная матрица будет:

Тогда:

F_min=

Примечание:Так как исходная задача приведена к единичному базису при неотрицательных свободных членах уравнений, то обратная матрица

А_х^-1состоит из компонентов векторовА₃иА₅ последней симплекс- таблицы.