Chiziqli dasturlash masalasini echishning simpleks usuli

A3, A4, A5 birlik vektorlarni boshlang’ich tayanch yechim uchun qabul qilib, х1, X2 noma’lumlarni 0 ga teng deymiz. Natijada X0 =(xj = 0, x2 = 0, x3 = 784, x4 = 552, x5 = 567) tayanch yechimni olmiz, bunga

X3 А3 + X4 А4 + X5 А5 = Aq

yoyilma mos keladi.

X 0 yechimning optimalligini tekshirish uchun birinchi simpleks jadvalni tuzamiz:

1-simpleks jadval.

i	Bazis-lar	Bazis koeffi- siyent- lar Sb	Ao		4		6		0		0		0
					Ai		A2		A3		A4		A5
1	A3	0	784		16		4		1		0		0
2	A4	0	552		8		7		0		1		0
3	a5	0	567		5		9		0		0		1
m+1	zj - Cj			0		-4		-6		0		0		0

Z (X0) va Zt - C} baholarni hisoblaymiz:

Z(X0) = 4 • 0 + 6 • 0 + 0 • 784 + 0 • 552 + 0 • 567 = 0 ,

Z1 = СбХ1 = 0 46 + 0 • 8 + 0 • 9 = 0, Z 2 = СбХ 2 = 0, Z3 = СбХ3 = 0, Z4 = СбХ4 = 0, z5 = СбХ5 = 0, Z1 -C1 = 0-4 = -4, Z2 -C2 = 0-6 = -6, Z3 -C3 = 0-0 = 0, z4 -C4 = 0-0 = 0, Z5 -C5 = 0-0 = 0.

Olingan baholar ichida ikkita, z 1 - C1 = -4 < 0, z2 - C2 = -6 < 0 manfiy baholar mavjud bo’lib, ular boshlang’ich tayanch yechim optimal emasligini bildiradi. Bazisga min( C}) = -6 bo’lgan vektor A2 ni kiritamiz.

min I 1 = 63 bo’lganligi uchun ochuvchi (kalit) element 9 bo’lib, u

joylashgan ustun va satrlar yo’naltiruvchi bo’ladi. Demak, bazisga A2 vektorni kiritib A5 vektorni bazisdan chiqaramiz. 2-simpleks jadvalni tuzamiz:

2-simpleks jadval.

i	Bazis-lar	Bazis koeffi- siyent- lar Sb	Ao	4	6	0	0	0
				Aj	A2	A3	A4	A5
1	A3	0	532	124/9	0	1	0	-4/9
2	A4	0	111	37/9	0	0	1	-7/9
3	A2	6	63	5/9	1	0	0	1/9
m+1	zJ - с		378	-6/9	0	0	0	6/9

Birinchi simpleks jadvaldagi yo’naltiruvchi (kalit) satrga mos ikkinchi simpleks jadvaldagi satrga bosh satr deb ataymiz va uning elementlarini hisoblashdan boshlaymiz: 3-satr ya’ni yo’naltiruvchi (kalit) satr elementlarini ochuvchi (kalit) elementga bo’lib, 63, 5/9, 1, 0, 0, 1/9 larni topamiz. Bu satrni 4 ga ko’paytirib 1-satr mos elementlaridan ayirib 532, 124/9, 0, 1, 0, -4/9, 2- simpleks jadval birinchi satr elementlarini, 7 ga ko’paytirib 2-satr elementlaridan ayirib, 111, 37-9, 0, 0, -7/9, 2-jadvalning 2-satr elementlarini hisobladik. Endi 6 ga ko’paytirib (m+1) satr mos elementlariga qo’shib 378, - 6/9, 0, 0, 0, 6/9 2-jadvalning (m+1) satr elementlarini olamiz.

simpleks jadvalda

X((1) = (x1 = 0, x2 = 63, x3 = 532, x4 = 111, x5 = 0)

tayanch yechim olindi. Bu yechimga chiziqli funksiyaning Z (X 01)) = 4 • 0 + 6 • 63 + 0 • 532 + 0-111 + 0 • 0 = 372 qiymati mos keladi.

(m+1) - satrda Zj -с1 = -6/9 manfiy baho mavjud bo’lganligi uchun X((1) yechim optimal emas. A1 vektor bazisga kiritilishi kerak.

minf 532 ; 111 ;-6^l = 111 = 27bo’lib, 37/9 ochuvchi (kalit) element bo’ladi.

^ 124/9 37/9 5/9) 37/9

Bazisdan A4 vektor chiqariladi, 3-simpleks jadvalda bosh satr 2-satr bo’lib uning elementlari mos ravishda

1, 0, 0, 9/37, -7/37 bo’ladi. Oldingi jadvaldagidek, Jordan-Gauss to’la yo’qotish usulidan foydalanib, boshqa satrlar elementlarni hisoblab, 3-simpleks jadvalni tuzamiz:

3-simpleks jadval.

i	Bazis-lar	Bazis koeffi- siyent- lar Sb	A0	4	6	0	0	0
				A1	A2	A3	A4	A5
1	A3	0	160	0	0	1	-124/37	80/37
2	A1	4	27	1	0	0	9/37	-7/37

3	A2	6	48	0	1	0	-5/37	8/37
m+1	zj - C		396	0	0	0	6/37	20/37

(m+1) satrda, 3-iteratsiyada manfiy baholar yo’q, demak, olingan reja optimal bo’lib, X02) =(27,48,160,0,0) optimal yechim bo’ladi. Zmax(X02)) = 4• 27 + + 6 • 48 + 0 460 + 0 • 0 + 0 • 0 = 396. (m+1) - satr baholaridan kelib chiqadiki, optimal yechim yagonadir, chunki 0 baholar faqat bazis o’zgaruvchilariga mos keladi.

Sun’iy bazis usuli. Yuqorida qaralgan chiziqli dasturlash masalasida cheklash shartlarida m tartibli birlik matritsa mavjud edi, ya’ni cheklash shartlari AX < A0, A0 > 0 edi, bunday sistema hamisha birlik matritsaga ega bo’ladi. Chiziqli dasturlash ko’p masalalarida cheklash shartlari yuqoridagidek bo’lmay va birlik matritsa mavjud bo’lmaydi. Bunday hollarda sun’iy bazis usulidan foydalaniladi. Sun’iy bazis usulini quyidagi misolda qaraymiz [3, 68-bet].

misol. z = 5x1 + 3x2 + 4x3 - x4 chiziqli funksiyaning f x1 + 3x2 + 2 x3 + 2 x4 = 3,

|2x1 + 2x2 + x3 + x4 = 3, xj > 0 (j = 1,2,3,4)

shartlar sistemasini qanoatlantiruvchi maksimal qiymatini toping.

Yechish. Ma’lumki, cheklash shartlari sistemasida birlik matritsa mavjud emas. Har bir tenglamaga bittadan manfiy bo’lmagan, mos ravishda x5 > 0, x6 > 0 sun’iy o’zgaruvchilarni kiritamiz. Endi berilgan masalaga nisbatan kengaytirilgan masala deb ataluvchi ushbu masalaga o’tamiz: z = 5 x1 + 3x2 + 4x3 - x4 - Mx5 - Mx6 chiziqli funksiyaning f x1 + 3x2 + 2 x3 + 2 x 4 + x5 = 3,

|2x1 + 2x2 + x3 + x4 + x6 = 3, xj > 0 (j = 1,2,3,4,5,6)

shartlar sistemasini qanoatlantiruvchi maksimal qiymatini toping (bunda M yetarlicha kichik manfiy son, masala minimumga yechilayotgan bo’lsa yetarlicha katta musbat son deb olinadi). Vektor shaklida

A1 Xj + A2 X2 + A3 x^ + A4 X4 + A5 X5 + A6 X6 = A0

ko’rinishda bo’ladi. Bazis uchun А5, А6 birlik vektorlarni olamiz. Bu sun’iy bazisni tashqil etadi. Erkin o’zgaruvchilar х1, х2, х3, х4 larni 0 ga tenglab, birinchi tayanch X0 = (0, 0, 0, 0,3,3) yechimni olamiz.

simpleks jadvalni tuzamiz:

Jadvalning (m+1) va (m+2) satrlarini to’ldirishda z(X0) = СбХ0 =-М • 3 -М • 3 + 0 = 0 - 6М;

Z1 - С = СбХ 1 - С1 =-М 4 - М • 2 - 5 = -5 - 3М;

1-simpleks jadval

	Bazis-lar	Bazis
i		koeffi-	A0	5	3	4	1	-M	-M

		siyent- lar Sb		Aj	A2	A3	A4	A5	A6
1	A5	-M	3	1	3	2	2	1	0
2	A6	-M	3	2	2	1	1	0	1
m+1	N, - С		0	-5	-3	-4	1	0	0
m+2	N, - С		-6	-3	-5	-3	-3	0	0

N 2	- С 2	= C6X 2	2 0 -
N 3	- С 3	= C6X 3	- 0 3
N 4	-С4	= OX 4	- 0 4 :
N 5	- C5	= QX5 -	- 05 :
N 6	1 С Os	= c6x 6	- 06