Amaliy matematika va informatika ta’lim yo’nalishi 2-oliy ta’lim 4-bosqish talabasi

L =15x₁ +12x₂ + 20x₃ +18x₄ → min

1 ₋ 4 shartlar orasidan chiziqli erklilari tanlanadi. Bevosita tekshirish yo'li bilan 1 ₋ 3 shartlardan 4 shart kelib chiqishini ko'rishimiz mumkin. Sxematik tarzda tengliklar ustida amallar bajarish qoidasiga ko'ra 1 ₊ 2 ₋ 3 ₌ 4 ekanligini ko'ramiz. Demak, bu yerda ChPMni x₁ + x₂ = 30

x3 + x4 = 50 x₁ + x₃ = 35

L =15x₁ +12x₂ + 20x₃ +18x₄ → min
ko'rinishda ifodalash mumkin. Bu masalaga simpleks usulni tatbiq qilish uchun ChPM shartlaridan bazislarni ajratish (ustunlari orasida birlik vektorlarni hosil qilish) jarayonini namoyish etamiz. Sistemadagi x₁, x₂ , x₃ , x₄ ga mos koeffitsientlar A₁, A₂ , A₃ , A₄ vektorlarni hosil qiladi. Ulardan tuzilgan matritsa ozod hadlar ustuni bilan to'ldirilsa
1 1 0 0 30_
 

B =_0 0 1 1 50_
 1 0 1 0 35 (−1)
matritsa hosil bo'ladi. Bu matritsaning 2-,4-ustunlari bazis holatida A₂^T ₌ (1;0; 0;
0)ekanligini ko'ramiz. Agar 3 – qatorini -1 ga ko'paytirib 2 – qatorga qo'shsak 3 – ustun ham bazis ko'rinishini oladi.
 

^ 1 1 0 0 30^
 

B =_−1 0 0 1 15_
 1 010 35 
 bazis 
Bu matritsa berilgan shartlarning shakl almashtirilib
x₁ + x₂ = 30

− x₁ + x₄ =15


^ x₁ + x₃ = 35
ko'rinishga keltirilganligini aks ettiradi. Bu ko'rinishdan simpleks jadvalga o'tamiz va bu jadvalga mos planni optimallikka tekshiramiz.

C j C			15	12	20	18
	baz	A0	A1	A2	A3	A4	Өi
12	A2	30	1	1	0	0
18	A4	15	-1	0	0	1
20	A3	35	1	0	1	0
	∆ j		-1	0	0	0

Bu yerda ∆₁ =C_baz × A₁ −C₁ =12×1+18×(−1) + 20×1−15 =−1formula bo'yicha hisoblangan. Qolganlari ham shunga o'xshash hisoblanadi. Masala minimumini topishga mo'ljallangan bo'lsa, ∆ _j lar orasida musbatlari yo'q bo'lsa, jadvalga mos plan optimal plan bo'ladi. Bizda ana shunday hol kuzatilyapti. Demak bu masalada optimal plan x₁ = 0; x₂ = 30; x₃ = 35; x₄ =15 bo'lar ekan. Bu holda harajatlar minimal bo'lib, L ₌12_×30 ₊18_×15 ₊ 20_×35 ₌1330 ming so'm bo'lar ekan. Masala shartlari va yechimini ifodalovchi jadval

Zav
	1	2	Σ
1	15 0	12 30	30
2	20 35	13 15	50
Σ	35	45	80

ko'rinishda bo'ladi.
Tahlil to'laqonli ko'rinishni olishini namoyish qilish uchun yuqoridagi masalada faqat bitta narx 1 – zavoddan 2 – qurilishga 1 mashina g'isht olib borish narxi 30ming so'mga o'zgargan bo'lsin deb faraz qilamiz. Bunda faqat maqsad funksiyasi ko'rinishi o'zgaradi, ya'ni


L =15x₁ +12x₂ + 30x₃ +18x₄ → min ko'rinishni oladi. Simpleks jadvalda ham faqat narxlar C_i ga mos qator va ustunlargina o'zgaradi va quyidagi ko'rinishni oladi
←

C
			15	12	30	18
	Baz	A0	A1	A2	A3	A4	Өi
12	A2	30	1	1	0	0	30
18	A4	15	-1	0	0	1
30	A3	35	1	0	1	0	35
			9	0	0	0

_↑
Bu jadvalga mos plan x₁ = 0; x₂ = 30; x₃ = 35; x₄ =15 optimal emas, chunki ∆₁ = 9  0.
Bu planga ko'ra L ₌12_×30 ₊18_×15 ₊ 30_×35 ₌1680ming. Planni yaxshilash uchun jadvaldan _i a ⁱ⁰ larni hisoblaymiz (faqat a_i1  0lar uchun). minθ_i ga mos 1 – qatorni hal θ =

a i1
qiluvchi qator deb belgilaymiz. Uning yordamida 1 – ustunni bazis ustunga aylantiramiz. Buning uchun 1 – qatorni 2 – qatorga qo'shamiz, hamda (-1) ga ko'paytirib 3 – qatorga qo'shamiz. Natijada yangi simpleks jadvalni hosil qilamiz

C
			15	12	30	18
	Bazis	A0	A1	A2	A3	A4	Ө
15	A1	30	1	1	0	0
18	A4	45	0	1	0	1
30	A3	5	0	-1	1	0
			0	-17	0	0

Bu jadvalda ∆ _j  0 lari yo'q bo'lgani uchun bu jadvalga mos tayanch yechim x₁ = 30; x₂ = 0; x₃ = 5; x₄ 45 optimal plan bo'ladi. Bu plan bo'yicha ketadigan transport

harajatlari

L ₌15_×30 ₊18_× 45 ₊ 30_×5 ₌ 450 ₊ 810 ₊150 ₌1410ming so'm bo'lib avvalgisidan 270ming so'mga kam bo'lar ekan.
Bu usul bilan ixtiyoriy transport masalasini ham odatdagi ChPM ko'rinishiga keltirish mumkin ekan. Faqat shartli ravishda
n ta ishlab chiqaruvchi va ularga bog'langan m ta iste'molchi bo'lgan transport masalasini tasavvur qilsak, bu unchalik oson ish emas ekanligini to'la tasavvur qilishimiz mumkin. Transport masalasini ba'zi kichik hajmdagi hollarda mantiqiy muhokamalar asosida ham yechish mumkin ekan. Bunga misol

T
	1	2	Σ
1	15 x1	20 x2	20
2	18 x3	13 x4	60
3	14 x5	18 x6	40
Σ	70	50	12

sifatida jadvalda keltirilgan 2 ta ta'minotchi va 3ta iste'molchi bilan bog'liq transport masalasi namunasi keltirilgan. Unda bo'sh qolgan yarim kataklar aynan topilishi kerak bo'lgan ta'minot rejasini aks ettiruvchi 6 ta noma'lum x₁, x₂ , x₃ , x₄ , x₅ , x₆ larga mos keladi. Mantiqan dastlab eng arzon yo'nalish tanlanishi kerak. Demak avvalo yo'l harajati 13 bo'lgan katakka iloji boricha ko'proq jo'natish miqdorini qo'ygan ma'qul. Bu qiymat 50 ekanligi ko'rinib turibdi. U holda shu qatorning birinchi katagiga 10 qo'yishimiz kerak bo'ladi. Shuningdek ikkinchi ustun qolgan ikki katagi 0 bo'lishi kerakligi ko'rinib turibdi. Qolgan kataklar ham o'z - o'zidan bir qiymatli to'ldirilishi mumkin bo'lib qoladi. Xulosa qilib aytganda x₁ = 20; x₂ = 0; x₃ =10; x₄ = 50; x₅ = 40; x₆ = 0 ekanligini topamiz. Bunda transport

harajatlari L =15× 20 + 20× 0 +18×10 +13×50 +14× 40 +18×0 =1770
bo'lishini ko'ramiz. Natijada masala shartlari va yechimini ifodalovchi jadvalni hosil qilamiz

T
	1	2	Σ
1	15 20	20 0	20
2	18 10	13 50	60
3	14 40	18 0	40
Σ	70	50	120

Yuqorida keltirilgan masalani planni bosqichma – bosqich yaxshilash usuli bo'yicha simpleks jadvallar asosida ishlab ko'ramiz. Unga mos ChPM quyidagicha ifodalanadi.
x₁ + x₂ = 20

^ x₃ + x₄ = 60
x₅ + x₆ = 40


^ x₁ + x₃ + x₅ = 70
x₂ + x₄ + x₆ = 50


L(x₁, x₂ , x₃ , x₄ , x₅ , x₆ ) =15x₁ + 20x₂ +18x₃ +13x₄ +14x₅ +18x₆ → min
Bu masala shartlaridan beshinchisi chiziqli bog'liq. Qolgan qismi uchun kengaytirilgan matritsasini yozamiz va bu matritsada rangi to'rt bo'lganligi uchun to'rtta bazis ustun hosil qilamiz. Masalan qulaylik uchun 1-,3-,4-,6- ustunlarni bazis ustunlarga aylantirish holini ko'ramiz.
1 1 0 0 0 0 20_^×(−1) _1 1 0 0 0 0 20_
  

B ₌_00 00 10 10 10 10 6040 _ ⇔ _00 00 10 10 10 10 6040_ ⇔
   

1 0 1 0 1 0 70 0 −1 1 0 1 0 50×(−1)


1 1 0 0 0 0 20_

 
⇔ _00 10 00 10 −11 10 1040_

 

^ 0 −1 1 0 1 0 50^ _
Hosil bo'lgan matritsa ko'rsatilgan tartibda 1 – qatorni (-1)ga ko'paytirib 4 – qatorga qo'shish, so'ngra 4 – qatorni (-1) ga ko'paytirib 2 – qatorga qo'shish yordamida masala shartlarini ekvivalent tarzda o'zgartirishni aks ettiradi. Matritsa ko'rinishidan yana sistema ko'rinishiga o'tilsa u
x₁ + x₂ = 20
   x2 + x4 − x5 =10


_ x 5 + x₆ = 40
 − x₂ + x₃ + x₅ = 50
ko'rinishini oladi. Bevosita tekshirish bilan bazis o'zgaruvchilar

x₁ = 20, x₃ = 50, x₄ =10, x₆ = 40 qolganlari x₂ = 0; x₅ = 0 ekanligini ko'rishimiz
mumkin. Masalaning bu ko'rinishidan dastlabki simpleks jadvalni tuzib, bu jadvalga mos tayanch yechimni optimallikka tekshirishimiz mumkin. Agar yechim optimal bo'lmasa, keyingi bosqichga o'tamiz, ya'ni ∆ _j lar orasida manfiysi bo'lsa, hal qiluvchi qator va ustunlarini topib bazisni almashtiramiz. Bizning misol uchun simpleks jadval



optimal emasligini bildiradi. ∆ _j = 9 _ 0ga mos 5 – ustun hal qiluvchu ustun, shu
= a³⁰ ₌ 40 va Ө4 = a ⁴⁰ ₌ 50 lar ustun elementlari yordamida hisoblangan Ө3

a35 a 45
orasidan kichigiga mos keluvchi 3 – qator hal qiluvchi qator deb belgilandi va bazisdagi A₆ ustun A₅ ustunga almashtirilishi kerak. Buning uchun jadvalning 3 – qatorini 2 – qatorga qo'shamiz, hamda 3 – qatorni (-1)ga ko'pytirib 4 – qatorga qo'shamiz. Shunda 5 – ustun ham bazis ustun ko'rinishini oladi va quyidagi simpleks jadval hosil bo'ladi.

C C
	Bazis	A0	A1	A2	A3	A4	A5	A6	Өi
15	A1	20	1	1	0	0	0	0
13	A4	50	0	1	0	1	0	1
14	A5	40	0	0	0	0	1	-1
18	A3	10	0	-1	1	0	0	-1
	∆ j		0	-10	0	0	0	-9

Bu jadvalga ko'ra ∆ _j lar orasida musbatlari yo'q bo'lganligi uchun bu jadvalga mos tayanch yechim x₁ = 20; x₂ = 0; x₃ =10; x₄ = 50; x₅ = 40; x₆ = 0optimal yechim bo'ladi. Shu masala uchun mantiqiy mulohazalarga ko'ra tanlangan dastlabki yechim ham xuddi shunday bo'lgan edi. Bu natijadan ikki muhim xulosani keltirib chiqarishimiz mumkin ekan. Birinchisi – transport masalasini yechishda mantiqiy mulohazalarga asoslanishimiz mumkin ekan. Bunday usulda tanlangan yechim optimal yechim bo'lib qolishi ham mumkin, bo'lmagan taqdirda ham optimal yechimga yaqin yechim bo'lib simpleks usul yordamida yaxshilash bosqichlari soni kam bo'ladi. Ikkinchidan – transport masalasi ham odatdagi ChPMga keltirilishi mumkin bo'lib, unga ham an'anviy usullarni tatbiq qilish mumkin ekan. Bunda faqat bir narsani unutmasligimiz kerak. Yuqorida ta'kidlanganidek, ta'minotchilar soni n va iste'molchilar soni m ortgan sari noma'lumlar soni n×m keskin ortib odatdagi usullarni tatbiq qilish mushkullashib boraveradi. Bunday hollarda masalani yechish uchun iteratsion usullardan foydalanish ma'qulroq bo'ladi.

Masalalar
5. Keltirilgan jadval qiymatlarga mos tansport masalasini tuzing. Masala tayanch yechimini minimal harajatlar usuli bo’yicha aniqlang va uni optimallikka tekshiring.

5.1

	1	2	3	∑
1				200
2				300
∑	150	250	100	500

5.2

	1	2	3	∑
1				400
2				500
∑	200	400	300	900

5.3

	1	2	3	∑
1
2
∑	250	350	200

5.4

	1	2	3	∑
1
2
∑	250	150	300

5.5

	1	2	3	∑
1				600
2				400
∑	300	500	200