5.8. Зіставлення методу потенціалів I симплекс-методу

Проiлюструємо зв’язок мiж методом потенцiалiв i симплекс-методом на прикладi розв’язання такої задачi:

	5		10		7
						5
	6		4		12
						10
3		7		5

Будемо розв’язувати її паралельно методом потенцiалiв i симплекс-методом. Знайдемо початковий розв’язок методом північно-західного кута.

	v1=5		v2=10		v3=18
		5		10		7
u1=0	3		2				5	2	–
					11
		6		4		12
u2=-6			5		5		10	5	–
	-7
	3		7		5
	–		5		–
			–

Записуємо задачу у вигляді системи:

min z=5x₁₁+10x₁₂+7x₁₃+6x₂₁+4x₂₂+12x₂₃ ;

x₁₁+ x₁₂+ x₁₃ =5; (5.21)

x₂₁ + x₂₂+ x₂₃=10; (5.22)

x₁₁ + x₂₁ =3; (5.23)

x₁₂ + x₂₂ =7; (5.24)

x₁₃ + x₂₃=5; (5.25)

x₁₁,x₁₂,x₁₃,x₂₁,x₂₂,x₂₃ 0.

Вилучимо перше рівняння й зведемо систему до діагонального вигляду відносно змінних x₁₁, x₁₂, x₂₂, x₂₃ :

min z=5x₁₁+10x₁₂+7x₁₃+6x₂₁+4x₂₂+12x₂₃;

x₁₁+ x₂₁ =3; (5.21a)

x₁₃ + x₂₃ =5; (5.22a)

-x₁₃ + x₂₁+ x₂₂ =5; (5.23a)

x₁₂+ x₁₃ - x₂₁ =2; (5.24a)

x₁₁,x₁₂,x₁₃,x₂₁,x₂₂,x₂₃ 0.

Примітка:

(5.21a)=(5.23)

(5.22a)=(5.25)

(5.23a)=(5.22)—(5.25)

(5.24a)=(5.24)+(5.25)—(5.22)

Далi наводимо транспортну таблицю i симплекс-таблицю для вiдповiдного кроку:

	v1=5		v2=10		v3=18
		5		10		7				БП	x11	x12	x13	x21	x22	x23	Р
u1=0	3		2		x13		5			z	0	0	11	-7	0	0	115
				–	11					x11	1	0	0	1	0	0	3
		6		4		12				x12	0	1	1	-1	0	0	2
u2=-6			5		5		10			x22	0	0	-1	1	1	0	5
	-7					–				x23	0	0	1	0	0	1	5
	3		7		5			Z=115
	v1=5		v2=-1		v3=7
		5		10		7				БП	x11	x12	x13	x21	x22	x23	Р
u1=0	3				2		5			z	0	-11	0	4	0	0	93
		–	-11							x11	1	0	0	1	0	0	3
		6		4		12				x13	0	1	1	-1	0	0	2
u2=5	x21		7		3		10			x22	0	1	0	0	1	0	7
	4					–				x23	0	-1	0	1	0	1	3
	3		7		5 			Z=93
	v1=5		V2=3		v3=7
		5		10		7				БП	x11	x12	x13	x21	x22	x23	Р
u1=0	0				5		5			z	0	-7	0	0	0	-4	81
			-7							x11	1	1	0	0	0	-1	0
		6		4		12				x13	0	0	1	0	0	1	5
u2=1	3		7				10			x22	0	1	0	0	1	0	7
					-4					x21	0	-1	0	1	0	1	3
	3		7		5			Z=81

Як бачимо, між методом потенціалів та симплекс-методом існує взаємо­однозначний зв’язок.