T. I. Umarov s. I. Xudoyberdiyev iqtisodiy matematik usullar va

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 (X₀) va Z_t - C_} baholarni hisoblaymiz:

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

Z₁ = С_бХ₁ = 0 46 + 0 • 8 + 0 • 9 = 0, Z ₂ = С_бХ ₂ = 0, Z₃ = С_бХ₃ = 0, Z₄ = С_бХ₄ = 0, z₅ = С_бХ₅ = 0, Z₁ -C₁ = 0-4 = -4, Z₂ -C₂ = 0-6 = -6, Z₃ -C₃ = 0-0 = 0, z₄ -C₄ = 0-0 = 0, Z₅ -C₅ = 0-0 = 0.

Olingan baholar ichida ikkita, z ₁ - C₁ = -4 < 0, z₂ - C₂ = -6 < 0 manfiy baholar mavjud bo’lib, ular boshlang’ich tayanch yechim optimal emasligini bildiradi. Bazisga min( C_}) = -6 bo’lgan vektor A₂ 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 A₂ vektorni kiritib A₅ 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.

2. simpleks jadvalda

   
   

X₍⁽¹⁾ = (x₁ = 0, x₂ = 63, x₃ = 532, x₄ = 111, x₅ = 0)

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

   
   

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

min^{f 532} ; ¹¹¹ ;-⁶^l = ¹¹¹ = 27bo’lib, 37/9 ochuvchi (kalit) element bo’ladi.

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

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

27. 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, X0²⁾ =(27,48,160,0,0) optimal yechim bo’ladi. Z_max(X0²⁾) = 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.

4. 
   
   Sun’iy bazis usuli. Yuqorida qaralgan chiziqli dasturlash masalasida cheklash shartlarida m tartibli birlik matritsa mavjud edi, ya’ni cheklash shartlari AX < A₀, A₀ > 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].
   

2. misol. z = 5x₁ + 3x₂ + 4x₃ - x₄ chiziqli funksiyaning f x₁ + 3x₂ + 2 x₃ + 2 x₄ = 3,

   
   

|2x₁ + 2x₂ + x₃ + x₄ = 3, x_j > 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 x₅ > 0, x₆ > 0 sun’iy o’zgaruvchilarni kiritamiz. Endi berilgan masalaga nisbatan kengaytirilgan masala deb ataluvchi ushbu masalaga o’tamiz: z = 5 x₁ + 3x₂ + 4x₃ - x₄ - Mx₅ - Mx₆ chiziqli funksiyaning f x₁ + 3x₂ + 2 x₃ + 2 x ₄ + x₅ = 3,

|2x₁ + 2x₂ + x₃ + x₄ + x₆ = 3, x_j > 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 А₅, А₆ birlik vektorlarni olamiz. Bu sun’iy bazisni tashqil etadi. Erkin o’zgaruvchilar х₁, х₂, х₃, х₄ larni 0 ga tenglab, birinchi tayanch X₀ = (0, 0, 0, 0,3,3) yechimni olamiz.

1. simpleks jadvalni tuzamiz:

   
   

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

Z₁ - С = С_бХ ₁ - С₁ =-М 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