Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду (1.12). Для этого второе неравенство следует умножить на -1.

Двойственная задача. Найти максимум линейной функции f = 2y₁ + 3y₂ + 6y₃ + 3y₄ при ограничениях

2y₁ - y₂ + y₃ + 2y₄ £ 1,

2y₁ + y₂ + y₃ + y₄ ³ 2,

-y₁ + 4y₂ - 2y₃ - 2y₄ ³ 3,

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

Для решения двойственной задачи необходимо ввести три допол­нительные переменные. Система ограничений не требует предваритель­ных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов.

Двойственную задачу решаем симплексным методом (табл. 1.3).

Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), f _max =21/2.

Оптимальный план исходной задачи находим, используя оценки ( m + 1)-й строки последней итерации, стоящие в столбцах A₅ , A₆ , A₇ : x₁ = 3/2 + 0 = 3/2; x₂ = 9/2 + 0 = 9/2; x₃ = 0+ 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функ­ция достигает наименьшего значения: Z_min =21/2.

Т а б л и ц а 1.3

i	Базис	С базиса	A0	2				3		6			3		0		0		0
				A1				A2		A3			A4		A5		A6		A7
1 2 3	A5 A3 A7	0 0 0	1 2 3	2 2 -1				-1 1 4		1 1 -2			2 -1 -2		1 0 0		0 1 0		0 0 1
m + 1	Zi - Cj		0	-2				-3		-6			-3		0		0		0
1 2 3	A3 A6 A7	6 0 0	1 1 5	2 0 3				-1 2 6		1 0 0			2 -1 2		1 -1 2		0 1 0		0 0 1
m + 1	Zi - Cj		6		10		-9				0		9		6		0		0
1 2 3	A3 A2 A7	6 3 0	3/2 ½ 2			2 0 3			0 1 0			1 0 0		3/2 -1/2 4		½ -1/2 5		½ ½ 3	0 0 1
m + 1	Zi - Cj		21/2			10			0			0		9/2		3/2		9/2	0

4. Виды математических моделей двойственных задач

На основании рассмотренных несимметричных и симметричных двойственных задач можно заключить, что математические модели пары двойственных задач могут иметь один из следующих видов.

Несимметричные задачи

(1) Исходная задача Двойственная задача

Z_min = CX; f _max = YA₀ ;

AX = A₀ ; YA £ С .

X ³ 0.

(2) Исходная задача Двойственная задача

Z_max = CX; f _min = YA₀ ;

AX = A₀ ; YA ³ С .

X ³ 0.

Симметричные задачи

(3) Исходная задача Двойственная задача

Z_min = CX; f _max = YA₀ ;

AX ³A₀ ; YA £ С .

X ³ 0. Y ³ 0.

(4) Исходная задача Двойственная задача

Z_max = CX; f _min = YA₀ ;

AX £A₀ ; YA ³ С .

X ³ 0. Y ³ 0.

Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений исходной задачи необходимо привести к соответствующему виду. Запишем, например, математиче­скую модель двойственной задачи для следующей исходной.