_Rus_rgr_v8

6.4. Решение задачи симплекс-методом

Приведём задачу к канонической форме:

max z =	15 x₁	+10 x₂	+8 x₃	+2 x₄	+0 s₁	+0 s₂	+0 s₃	+0 s₄
	x₁	+ 4 x₂	+ x₃	+5 x₄	+ s₁				=70
	3 x₁	+ 2 x₂	+ 3 x₃	+ 5 x₄		+ s₂			=80
	2 x₁	+ 3 x₂		+ 4 x₄			- s₃		=25
	x₁		+ x₃	+ x ₄				- s₄	=10
	2 x₁	- x₂	+ x₃						=0
	x₁,	x₂,	x₃,	x₄,	s₁,	s₂,	s₃,	s₄	0

В таблицах 6.2 – 6.9 приведены результаты итераций решения задачи табличным двухэтапным симплекс-методом. В табл. 6.2 – 6.7 представлены результаты реализации этапа I, а в табл. 6.8 -.6.9 - результаты реализации этапа II.

Таблица 6.2

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	5	2	2	5	0	0	-1	-1	0	0	0	35
z (max)	-15	-10	-8	-2	0	0	0	0	0	0	0	0
s₁	1	4	1	5	1	0	0	0	0	0	0	70
s₂	3	2	3	5	0	1	0	0	0	0	0	80
R₁	2	3	0	4	0	0	-1	0	1	0	0	25
R₂	1	0	1	1	0	0	0	-1	0	1	0	10
R₃	2	-1	1	0	0	0	0	0	0	0	1	0

Таблица 6.3

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	0	9/2	-1/2	5	0	0	-1	-1	0	0	-5/2	35
z (max)	0	-35/2	-1/2	-2	0	0	0	0	0	0	15/2	0
s₁	0	9/2	1/2	5	1	0	0	0	0	0	-1/2	70
s₂	0	7/2	3/2	5	0	1	0	0	0	0	-3/2	80
R₁	0	4	-1	4	0	0	-1	0	1	0	-1	25
R₂	0	1/2	1/2	1	0	0	0	-1	0	1	-1/2	10
x₁	1	-1/2	1/2	0	0	0	0	0	0	0	1/2	0

Таблица 6.4

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	0	-1/2	3/4	0	0	0	1/4	-1	-5/4	0	-5/4	15/4
z (max)	0	-31/2	-1	0	0	0	-1/2	0	1/2	0	7	25/2
s₁	0	-1/2	7/4	0	1	0	5/4	0	-5/4	0	3/4	155/4
s₂	0	-3/2	11/4	0	0	1	5/4	0	-5/4	0	-1/4	195/4
x₄	0	1	-1/4	1	0	0	-1/4	0	1/4	0	-1/4	25/4
R₂	0	-1/2	3/4	0	0	0	1/4	-1	-1/4	1	-1/4	15/4
x₁	1	-1/2	1/2	0	0	0	0	0	0	0	1/2	0

Таблица 6.5

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	-3/2	1/4	0	0	0	0	1/4	-1	-5/4	0	-2	15/4
z (max)	2	-33/2	0	0	0	0	-1/2	0	1/2	0	8	25/2
s₁	-7/2	5/4	0	0	1	0	5/4	0	-5/4	0	-1	155/4
s₂	-11/2	5/4	0	0	0	1	5/4	0	-5/4	0	-3	195/4
x₄	1/2	3/4	0	1	0	0	-1/4	0	1/4	0	0	25/4
R₂	-3/2	1/4	0	0	0	0	1/4	-1	-1/4	1	-1	15/4
x₃	2	-1	1	0	0	0	0	0	0	0	1	0

Таблица 6.6

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	-5/3	0	0	-1/3	0	0	1/3	-1	-4/3	0	-2	5/3
z (max)	13	0	0	22	0	0	-6	0	6	0	8	150
s₁	-13/3	0	0	-5/3	1	0	5/3	0	-5/3	0	-1	85/3
s₂	-19/3	0	0	-5/3	0	1	5/3	0	-5/3	0	-3	115/3
x₂	2/3	1	0	4/3	0	0	-1/3	0	1/3	0	0	25/3
R₂	-5/3	0	0	-1/3	0	0	1/3	-1	-1/3	1	-1	5/3
x₃	8/3	0	1	4/3	0	0	-1/3	0	1/3	0	1	25/3

Таблица 6.7

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
r (min)	0	0	0	0	0	0	0	0	-1	-1	-1	0
z (max)	-17	0	0	16	0	0	0	-18	0	18	-10	180
s₁	4	0	0	0	1	0	0	5	0	-5	4	20
s₂	2	0	0	0	0	1	0	5	0	-5	2	30
x₂	-1	1	0	1	0	0	0	-1	0	1	-1	10
s₃	-5	0	0	-1	0	0	1	-3	-1	3	-3	5
x₃	1	0	1	1	0	0	0	-1	0	1	0	10

Так как нашей целью является проведение постоптимального анализа модели, то искусственные переменные, вышедшие из базиса, из модели исключать не надо – в дальнейшем нам понадобятся все столбцы оптимальной симплекс-таблицы. В таблицах следующих итераций коэффициенты z-строки при искусственных переменных не считаем, так как при использовании двухэтапного метода (в отличие от М-метода) на втором этапе эти коэффициенты не имеют смысла.

Таблица 6.8

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
z (max)	-13/5	0	0	16	18/5	0	0	0				252
s₄	4/5	0	0	0	1/5	0	0	1	0	-1	4/5	4
s₂	-2	0	0	0	-1	1	0	0	0	0	-2	10
x₂	-1/5	1	0	1	1/5	0	0	0	0	0	-1/5	14
s₃	-13/5	0	0	-1	3/5	0	1	0	-1	0	-3/5	17
x₃	9/5	0	1	1	1/5	0	0	0	0	0	4/5	14

Таблица 6.9

Б.п.	x₁	x₂	x₃	x₄	s₁	s₂	s₃	s₄	R₁	R₂	R₃	Реш.
z (max)	0	0	0	16	17/4	0	0	13/4				265
x₁	1	0	0	0	1/4	0	0	5/4	0	-5/4	1	5
s₂	0	0	0	0	-1/2	1	0	5/2	0	-5/2	0	20
x₂	0	1	0	1	1/4	0	0	1/4	0	-1/4	0	15
s₃	0	0	0	-1	5/4	0	1	13/4	-1	-13/4	2	30
x₃	0	0	1	1	-1/4	0	0	-9/4	0	9/4	-1	5

Итак: z=265, x₁=5, x₂=15, x₃=5, x₄=0.

Содержание