4.2. Первая теорема двойственности

Теорема. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Пример 1. Для данной задачи составить двойственную, решить ее , симплексным методом и, используя первую теорему двойственности, найти решение исходной задачи: F(X) = 6х₁ +7х₂+9 х₃ →min,

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

Z(Y) =5у₁ + 2у₂ +4у₃ → max,

Вводим неотрицательные дополнительные переменные у₄, у₅, у₆ для приведения задачи к каноническому виду:

Z(Y) =5у₁ + 2у₂ +4у₃+0у₄+0у₅ +0у₆→ max,

Находим начальное опорное решение У₁ = (0, 0, 0, 6, 7, 9) с базисом Б₁= (А₄, А₅, А₆). Решение задачи симплексным методом приведено в таблице.

↓5 ↓2 4 0 0 0

Б	Сб		А0	А1	А2	А3	А4	А5	А6	θ1	θ2	θ3
А4	0		6	1	1	1	1	0	0	6	6	6
А5	0		7	2	1	2	0	1	0	7/2	7	7/2
←А6	0		9	3	1	6	0	0	1	3	9	3/2
Δ j			0	-5	-2	-4	0	0	0	θ2
А4		0	3	0	2/3	-1	1	0	-1/3	9/2
←А5		0	1	0	1/3	-2	0	1	-2/3	3
А1		5	3	1	1/3	2	0	0	1/3	9
Δ j			15	0	-1/3	6	0	0	5/3
А4		0	1	0	0	3	1	-2	1	max Z(Y)=16, Y*=(2,3,0), Б*=( А4, А2, А1)
А2		2	3	0	1	-6	0	3	-2
А1		5	2	1	0	4	0	-1	1
Δ j			16	0	0	4	0	1	1

Оптимальное решение двойственной задачи Y^*=(2,3,0), его базис Б^*=( А₄, А₂, А₁), значение целевой функции max Z(Y)= Z(Y^* )= 16. Оптимальное решение исходной задачи, двойственной к решенной, находим по формуле:

X* = C*D ^-1.

Матрица D ^-1 находится в последней симплексной таблице. Ее столбцы расположены под столбцами единичной матрицы, т.е. под единичными векторами А₄, А₅, А₆, образующими базис начального опорного решения:

.

Координатами вектора С* являются коэффициенты целевой функции при базисных неизвестных оптимального решения у₄, y₂, y₁. Данные коэффициенты записываются в том же порядке, в каком векторы-условия входят в базис оптимального решения, т.е. С* = (0, 2, 5).

Вычисляем

X* = C*D ^-1= .

Оптимальное решение исходной задачи проще найти по формуле:

х_i*=Δ_i* + с_i*, i=l, 2,3.

Для этого необходимо к оценкам разложений векторов А₄, А₅, А₆, входящих в базис начального опорного решения, по базису оптимального решения, т.е. к оценкам этих векторов в последней симплексной таблице, прибавить соответствующие коэффициенты целевой функции (в таблице они расположены в верхней строке над оценками)

х₁*=0+0=0, х₂*=1+0=1, х₃*= 1+0=1.

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

Пример 2. Найти решение данной задачи и двойственной к ней:

F(X) =х₁-6х₂+2х₃ -x₄+3x₅→max,

Решение. Задача, двойственная к данной, имеет вид

Z(Y) =у₁ + 11у₂ +2у₃ → min,

В данной паре двойственных задач легче решить исходную задачу, так как она имеет начальное опорное решение Х₁= (0, 0, 1, 11, 2) с базисом Б₁ = (A₃, A₄, A₅) и ее без дополнительных преобразований можно решить симплексным методом. Решение исходной задачи приведено в таблице:

↓ 1 ↓-6 2 -1 3

Б	Сб		А0	А1	А2	А3	А4	А5	θ1	θ2	ΔF1=8, ΔF2=1.
А3	2		1	-2	1	1	0	0	-	1
А4	-1		11	2	3	0	1	0	11/2	11/3
←А5	3		2	1	-2	0	0	1	2	-
Δ j			-3	-4	-1	0	0	0
А3		2	5	0	-3	1	0	2
←А4		-1	7	0	7	0	1	-2
А1		1	2	1	-2	0	0	1
Δ j			5	0	-9	0	0	4
А3		2	8	0	0	1	3/7	8/7	max F(Y)=14, Y*=(4,1,8), Б*=( А3, А2, А1)
А2		-6	1	0	1	0	1/7	-2/7
А1		1	4	1	0	0	2/7	3/7
Δ j			14	0	0	0	9/7	10/7

Оптимальным решением исходной задачи является вектор X*=(4, 1, 8), базис оптимального решения Б* =( А₃, А₂, А₁) значение целевой функции max F(Y)= F(X*)= 14. Находим оптимальное решение двойственной задачи

Y* = C*D ^-1= .

Данное решение можно найти у_i* = Δ_i *+c_i*,

у₁* = 0+2 = 2, у₂* =9/7 - 1 = 2/7, у*₃ =10/7+3=31/7.

Таким образом, оптимальным решением двойственной задачи является вектор Y*= (2, 2/7,31/7), min Z(Y) = Z(Y*) = 14.

Ответ: F_max(X)=14 при X*=(4, 1, 8); Z _min(Y)=14 при Y*=(2, 2/7, 31/7).