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

Download 388 Kb.

bet	2/4
Sana	25.02.2022
Hajmi	388 Kb.
	#259251
Turi	Программа

1 2 3 4

Bog'liq
2-лаб иккинчи бўлим ЧПМ 2 topshiriq 22

x	1 ^ ^x2		 x₆  0, x₄  84,1; x₅ 							89,86;		x₃  22, 38.

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

Базис		С_i	15		20		24		0		0	0	b_i	_i
			A₁		A₂		A₃		A₄		A₅	A₆
A2		20	0,341		1		0		0,195		0	-0,122	16,41	48,1
A₅		0	4,27++		0		0		-0,561		1	-0,024	42,681	9,996
A₃		24	0,122		0		1		-0,073		0	0,171	16,226	133
		 _j	-5,252		0		0		2,148		0	14,6	717,624

			-------------
	x₁  x₄  x₆  0, x₂  16, 41; x₃  16, 226; x₅  42, 681.
4- Симплекс жадвал

Базис		С_i	15	20		24		0		0		0	b_i	_i
			A₁	A₂		A₃		A₄		A₅		A₆
A₂		20	0	1		0		0,24		-0,08		-0,12	13,001
A₁		15	1	0		0		-0,132		0,234		-0,006	9,936
A₃		24	0	0		1		-0,057		-0,028		0,172	15,006
		 _j	0	0		0		1,452		1,238		1,638	770,111


Бу жадвалда барча  _j						 0	бўлгани учун унга мос ечим

x₄  x₅  x₆  0, x₁  9, 936; x₂  13, 001; x₃ 15, 006.

Оптимал ечим бўлади. Мақсад функцияси қиймати бу холда ўз максимал қиймати L_max =770,111 га эришади.

4- Симплекс жадвал қийматларини (3) масала коэффицентлари билан солиштирсак улар бир хил эканлигини кўрамиз (фарқ ҳисоблашдаги яхлитлаш хатолиги ҳисобига).

Бундан албатта 1- усул маъқул экан деган хулосага бориш керак эмас. Тескари матрица топиш жараёни анча меҳнат талаб қилади. Ундан ташқари

танланган базис оптимал бўлмай қолса барчасини башқатдан бажаришга тўғри келади.

Агар масала

n
^aij ^x j	 b_i ; i 1, 2, 3,..., m
j 1
x _j  0	j 1, 2, 3,..., n	(4)

n
L ( x )  c _j x _j  max

1

Кўринишда берилган бўлса, мумкин бўлган базислар сони

N  Cnm

формула бўйича ҳисобланади. Хаттоки биз кўрган (2) масалада

ҳам n=6;

m=3

N C63 20

та вариант бор. Симплекс усул эса хар қадамда

аввалгисидан самаралироқ базисни танлаш йўлидан боради. Шунинг учун бу усулда барча базисларни кўриб чиқишга зарурат қолмайди.

Симплекс усули афзалликларидан яна бири, бу усулда бир йўла эгизак масала ечимлари ҳам хосил бўлар экан. Берилган (1) масала учун эгизак масала тузамиз:

3 y  6 y				 2 y 15
	1		2	3
7 y₁  4 y ₂				 3 y₃  20	(5)
		 3 y ₂		 8 y₃  24
⁵ ^y1

y₁ , y ₂ , y₃  0

 196 y₁  157 y₂  179 y₃  min

Чизиқли программалаш масалалар учун иккиланганлик теоремасига кўра (1) масала ечими мавжуд бўлса эгизак масала (5) нинг ҳам ечими мавжуд бўлади ва L_max = Q_min бўлади. Агар масала симплекс усулида ишланса сўнгги жадвал охирги қаторга сунъий базис усулларида эгизак масала ечимлари келиб чиқар экан. Бизнинг мисолда

y₁  1, 452; y₂	 1, 238; y₃ 1, 638	эканини кўрамиз.
Бу қийматларда	Q ни ҳисоблансин. Q_min	 772,16 келиб чиқади, яъни

L_max = Q_min орадаги фарқ, яна яхлитлаш хатоликлари ҳисобига пайдо бўлган дейиш мумкин.

Яна бир турдаги чизиқли программалаш масалаларини ечиш жараёнини таҳлил қиламиз. Бунда барча шартлар тенглик кўринишда берилган бўлиб, бошланғич базис танлаш ва масала шартларини ана шу танланган базисга

мослаштириш жараёнини ҳам киритишга тўғри келади. Буни қуйидаги масалада намойиш қиламиз.

5 x  3 x			 9 x	 7 x	 208
	1	2	3	4
⁸ ^x1		 4 x₂	 3 x₃	 6 x₄	184	(2)
		 9 x₂	 4 x₃  9 x₄		 216	(2)
³ ^x1		 9 x₂	 4 x₃  9 x₄		 216

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

 25 x₁  22 x₂  24 x₃  10 x₄  max

Бу масалада n=4; m=3 бўлиб базис ўзгарувчилар сони 3 га тенг бўлади.

Базис танлаш вариантлар сони эса N  С_nm  C₄3  4 га тенг. Базис танлашда

тавсиялардан бири нисбатан арзонроқ махсулотга мос ўзгарувчини базисга киритмаслик йўлидан борган маъқул. Бизда С₄ = 10 энг арзони, демак х₄ ни базисга киритмаганлик маъқул. Демак базис сифатида x₁ ; x₂ ; x₃ ларни олиш мумкин. Масала шартларини шу танланган базисга мослаштириш учун нормативлар матрицасидан ана шу ўзгарувчиларга мос қисмини базис матрица сифатида олиб унга тескари матрицани топамиз.

	5 3		9	
	8	4 3			; det B  416.

Download 388 Kb.

Do'stlaringiz bilan baham: