Transport masalasini yechishning potensiallar usuli Ishdan maqsad

Transport masalasini yechishning potensiallar usuli
Ishdan maqsad: transport masalasini yechishning potensiallar usuli haqida ma’lumotlar olish va amaliy misol yechish.
Transport masalasi quyidagi, 1-jadval, ko‘rinishda berilgan bo‘lib,

yopiq turdagi transport masalasi, ya’ni

=

bo‘lsin, bu yerda X_ij – yuk miqdorlari, C_ij – yuklarni o‘tkazishga ketgan xarajat miqdorlari.

1-jadval

Jo‘na-tish punkt lari	Qabul qilish punktlari				Yuk zahirasi
	V1	V2	...	Vn
A1	C11 X11	C12 X12	...	C1n X1n	a1
A2	C21 X21	C22 X22	...	C2n X2n	a2
: .	: .	: .	: .	: .	: .
Am	C m1 X m1	C m2 X m2	...	C mn X mn	am
Yukka bo‘gan talab	b1	b2	...	bn

Masalaning sharti bo’yicha, berilgan funksiyaning

Z = S_ij*X_ij
maksimum yoki minimum qiymati topilsin.

Masala. Har xil hosildorlikka ega bo‘lgan maydonlarga g‘alla ekish kerak. Bunda ekin ekiladigan maydonlarni shunday taqsimlash kerakki, natijada maksimum g‘alla hosili olishga erishilsin. Har bir gektar yerdan olinadigan hosil 9.2-jadvalda keltirilgan.
Yechish.

Qo‘yilgan masalani yechish uchun 2-jadval ko‘rsatkichlarini 1-jadval ko‘rinishida ifodalab, 3-jadvalni hosil qilamiz. 3-jadvalda qo‘shimcha ustun va qatorlar qo‘shildi, ularga v_j , u_i potensiallarni joy-lashtiramiz, chunki bu potensiallar masala yechilishining asosini tashkil qiladi.

2-jadval

Ekin turlari	Har bir uchastkada 1 gektardan olinadi-gan hosil (sentner hisobida)					Ekiladi-gan maydon-lar (gektar hisobida)
	1	2	3	4
Makka-jo‘xori	50	40	20	15	1000
Bug‘doy	20	12	11	7	6000
Arpa	22	15	10	9	1200
Tariq	28	10	6	4	1800
Uchastkalar maydoni (gektar hisobida)	2000	3000	3500	1500	10000

3-jadvalda uchastkalar bo‘yicha ekin maydonlari eng katta hosil-dorlikka nisbatan taqsimlab chiqildi. Hisoblash natijalari bo‘yicha maqsad funksiyasi qiymati quyidagiga teng bo‘ladi:
Z_max = 1000*50+1800*12+3500*11+700*7+1200*15+1000*28+
+800*4 q 50000+21000+38000+4900+18000+
+28000+3200 = 163100 s.
Topilgan funksiyaning (Z_max = 163100 s.) maksimum hosildorlik ekan-ligiga ishonch hosil qilish uchun topilgan yechimni tekshiramiz. Buning uchun funksiyaning erkin o‘zgaruvchilari hisoblangan potensial birlik v_j va u_i larni quyidagi ikki shart bajaralishini tekshirish lozim:
1. v_j – u_i = c_ij (to‘ldirilgan katakchalar uchun);
2. v_j – u_i c_ij (to‘ldirilmagan katakchalar uchun).
Potensiallarni to‘ldirilgan katakchalar orqali topamiz, to‘ldirilmagan katakchalar uchun esa ikkinchi shartning bajarilishini tekshiramiz. Buning uchun u₁ ga nol qiymatni beramiz, qolgan potensiallarni esa v_j – u_i = c_ij formula yordamida aniqlaymiz:

3-jadval

	Vj		V1 = 50	V2 = 31		V3 = 30		V4 = 26
Ui	Ekin turlari		Har bir uchastkaga gektaridan olinadigan hosil							E M
			1	2		3		4
U1 = 0	Makka-jo‘xori		– 50 1000	+ 40		20		15		1000
U2 =19	Bug‘doy		20	– 12 1800		11 3500		+ 7 700		6000
U3 =16	Arpa		22	15 1200		10		9		1200
U4 =22	Tariq		28 + 1000	10				4 – 800		1800
Uchastkalar maydoni		2000		3000	3500		1500		10000

v₁ – u₁ = 50 v₁ – u₄ = 28 v₄ – u₄ = 4 v₄ – u₂ = 7

v₁ – 0 = 50 50 – u₄ =22 v₄ –22 = 4 26 – u₂ = 7

v₁ = 50 u₄ = 22 v₄ = 26 u₂ =19

v₂ – u₂ = 12 v₃ – u₂ = 11 v₂ – u₃ = 15

v₂ – 19 = 12 v₃ –19 = 11 31– u₃ = 15

v₂ = 31 v₃ = 30 u₃ = 16
Endi to‘ldirilmagan katakchalarda ikkinchi shart bajarilishini tekshi-ramiz (v_j – u_i c_ij):
V₂ – U₁= 31 – 0 = 31 < 40 *

V₃ – U₁= 30 – 0 = 30 > 20

V₄ – U₁= 26 – 0 = 26 > 15

V₁ – U₂= 50 – 19 = 31 > 20

V₁ – U₃= 50 – 16 = 34 > 22

V₃ – U₃= 30 – 16 = 14 > 10

V₄ – U₃= 26 – 16 = 10 > 9

V₂ – U₄= 31 – 22 = 9 < 10 *

V₃ – U₄= 30 – 22 = 8 > 6
Potensiallar jadvaldagi A_1,2 va A_2,4 katakchalarida buziladi. Shuning uchun, rejani yanada yaxshilash variantini tuzamiz va taqsimlashni davom ettiramiz.

Taqsimlashni shunday tashkil etish kerakki, bunda taqsimlash yopiq zanjir ko‘rinishida bo‘lishi kerak. Zanjir tuzish boshlangan katakcha burchagiga plyus (+) ishorasini, keyingi katakchaga esa unga qarama-qarshi bo‘lgan minus (–) ishorasini, qolganlariga esa almashlab keluvchi plyus (+), minus (–), plyus (+) va hokazo ishoralarni qo‘yib chiqamiz. Optimal yechimni topish uchun tuzilgan yangi rejadan yopiq zanjirdagi manfiy katakdagi maydonlar orasidan eng kichik qiymatligini olib, uning qiymatini o‘zgartirmasdan musbat katakchalardagi miqdoriga qo‘shamiz va manfiy qiymatliklari miqdoridan ayiramiz. Shu yo‘l bilan yangi rejaga ega bo‘lamiz. Bu jarayon optimal yechimga ega bo‘lmaguncha davom ettiriladi.

Shunday qilib, 4-jadval hosil qilinadi. 4-jadval ko‘rsatkichlari bo‘yicha maqsad funksiyasi qiymati quyidagicha bo‘ladi:

Z_max = 200*50+800*40+1500*7+1200*15+1800*28+1000*12+

+3500*11= 10000+32000+10500+18000+50400+
+12000+38500 = 171400 s.
Optimal taqsimlash ekanligini bilish uchun 1-shart bo‘yicha poten-siallarni aniqlaymiz:
u₁ = 0; v₁ – u₁ = 50 v₂ – u₁ = 40 v₂ – u₂ = 12 v₃ – u₂ = 11

v₁ – 0 = 50 v₂ – 0 = 40 40 – u₂ = 12 v₃ – 28 = 11

v₁ = 50 v₂ = 40 u₂ = 28 v₃ = 39
v₄ – u₂ = 7 v₂ – u₃ = 15 v₁ – u₄ = 28

v₄ –28 = 7 40 – u₃ = 15 50 – u₄ = 28

v₄ = 35 u₃ = 25 u₄ = 22

Bo‘sh katakchalar uchun 2-shart bajarilishini tekshiramiz:

v₃ – u₁ = 39 – 0 = 39 > 20

v₄ – u₁ = 35 – 0 = 30 > 15

v₁ – u₂ = 50 – 28 = 22 >20

v₁ – u₃ = 50 –25 = 25 >22

v₃ – u₃ = 39 –25 = 14 >10

v₄ – u₃ = 35 –25 = 10 >9

v₂ – u₄ = 40 – 22 = 18 >10

v₃ – u₄ = 39 – 22 = 17 > 6

v₄ – u₄ = 35 –22 = 13 > 4
4-jadval

Ekin turlari	Har bir uchastkadan olinadigan hosil				E M
	1	2	3	4
Mak-kajo‘-xori	50 200	40 800	20	15		1000
Bug‘doy	20	12 1000	11 3500	7 1500		6000
Arpa	22	15 1200	10	9		1200
Tariq	28 1800	10	6	4		1800
Uchast-kalar maydoni	2000	3000	3500	1500		10000

2-shart to‘liq bajarildi, demak 4-jadval taqsimoti optimal taqsimot hisoblanib, Zmax = 171400 s. ekanligi ma’lum bo‘ldi.

Natija:

x₁₁ = 200 x₁₂ = 800 x₁₃ = 0 x₁₄ = 0

x₂₁ = 0 x₂₂ = 1000 x₂₃ = 3500 x₂₄ =1500

x₃₁ = 0 x₃₂ =1200 x₃₃ = 0 x₃₄ = 0

x₄₁ = 1800 x₄₂ = 0 x₄₃ = 0 x₄₄ = 0

O‘zlashtirish uchun topshiriqlar
1. f_min = ?

	V	V	V	V
A	40	50	30	45	200
A	80	55	70	75	300
A	25	10	15	20	400
A	50	35	55	45	300
	350	450	300	100	1200

2. f = ?

	V	V	V	V	V
A	70	50	60	55	75	250
A	100	85	90	90	80	350
A	45	30	50	40	55	200
A	10	25	35	15	50	200
	300	200	300	100	100	1000