Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз

2- лабаратория. Чизиқли программалаш масалалари (ЧПМ) ларни ечишда Симплекс усул моҳияти ва чизиқли программалаш масалалар бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар.

Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз.

3 x  7 x			 5 x	196
	1	2	3
^6 ^x1		 4 x2	 3 x3	157	(1)
^2 x  3 x			 8 x	179
	1	2	3

x₁ , x₂ , x₃  0

12. 
     15 x₁  20 x₂  24 x₃  max
    

Сунъий базис киритиш ёрдамида масала шартиларни тенглик кўринишига келтирамиз.

Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз.

3 x  7 x			 5 x	 x	196
	1	2	3	4
^6 ^x1		 4 x2	 3 x3	 x5	157	(2)
^2 x  3 x			 8 x	 x	179
	1	2	3	6

x₁ , x₂ , x₃ , x₄ , x₅ , x₆  0

12. 
     15 x₁  20 x₂  24 x₃  0 x₄  0 x₅  0 x₆  max
    

2. 
   масала ечими (1) масала учун ҳам ечим бўлиши кўриниб турибди.
   

Бунда x₄ , x₅ , x₆ лар қандай бўлишидан қатъий назар, улар мақсад функциясига хеч қандай таъсир ўтказмайди.

Симплекс усулнинг моҳияти-базисни шундай танлаш керакки, бунда базис ўзгарувчилар қийматларини берсин. (2) масалада базис ўзгарувчилар

x4 , x5 , x6


x1  x2  x3

бўлиб, бу базисда ўзгарувчилар қийматлари

 0, x4  196, x5  157, x6 179 , бўлади.

Бу қийматлар (2) масала шартларини тўла қаноатлантиради, лекин мақсад функцияси эса бунда L=0 бўлади. Бу эса (1) масала ечими сифатида қабул қилиниши мумкин эмас. Симплекс усул (2) масала базисини қадамба қадам ўзгартириб айнан оптимал базис ва оптимал ечимга бориш алгоритмидан иборат.

Албатта бу йўлни бир йўла, мураккаб бўлсада, тескари матрица ёрдамида амалга ошириш мумкин. Мантиқан ўйлаганда базис сифатида асосий (1) масала ўзгарувчиларини олган маъқуллиги кўриниб турибди.

Аксарият холларда шундай бўлади ҳам. Буни берилган мисол намунасида текшириб кўрамиз.

1. 
   Масала нормативлар матрицаси
   

	3	7 5		
	6	4	3		det A  175.
A  				
	2	3	8	
				

Учун тескари матрицани топамиз

		1		 23		 41	1	
1	 				42			
A						14	21	 ^.
		175
						5	30	
				 10				

(2) Масалани матрица кўринишида ифодалаб кўпайтириб юборамиз. Бу холда
x₁  0,1314 x₄  0, 2343 x₅  0, 0057 x₆ 10
^x₂  0, 24 x₄  0, 08 x₅  0,12 x₆ 13
^_x₃  0, 0571x₄  0, 0286 x₅  0,1714 x₆ 15


L  15 x₁  20 x₂  24 x₃  0 x₄  0 x₅  0 x₆  max

икки тарафдан А^1 га

(3)

кўринишни олади. (3) Масала ҳам (1), (2) масалага эквивалент бўлиб унинг ечимлари

x₁  10; x₂  13; x₃  15, x₄  0, x₅  0, x₆  0 бўлади.

Бунда мақсад функцияси максимал қиймати L_max=15*10+20*13+24*15=770 эканлигини кўрамиз.

Айнан шу масалани Симплекс усулида ечиш жараёнини кўриб чиқайлик. Биринчи Симплекс жадвал (2) масала асосида тузилади:

Базис		Сi	15	20		24	0	0		0	bi	i
			A1	A2		A3	A4	A5		A6
A4		0	3	7		5	1	0		0	196	39,2
A5		0	6	4		3	0	1		0	157	52,3
A6		0	2	3		8++	0	0		1	179	22,38
		 j	-15	-20		-24	0	0		0	0
						---------
	x	1 ^ ^x2	 x3 	0, x4	 196, x5  157, x6				179

2- Симплекс жадвал

Базис		Сi		15			20				24			0				0		0		bi	i
				A1			A2				A3			A4				A5		A6
A4		0		1,75			5,125++				0			1				0		-0,625		84,1	16,41
A5		0		5,25			2,875				0			0				1		-0,375		89,86	31,25
A3		24		0,25			0,375				1			0				0		0,125		22,38	59,68
		 j		-9			-11				0			0				0		3		537,12
							----------