Amaliy ish mavzu: Transport masalasini yechishning potensiallar usuli Ishdan maqsad

AMALIY ISH

Mavzu: Transport masalasini yechishning potensiallar usuli

Ishdan maqsad: Transport masalasini yechishning potensiallar usuli haqida ma'lumotlar olish va amaliy misol yechish.

Transport masalasi quyidagi, 9.1-jadval, ko'rinishda berilgan bo'lib,

9.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

yopiq turdagi transport masalasi, ya'ni

=
bo'lsin, bu yerda X_ij - yuk miqdorlari, C_ij - yuklarni o'tkazishga ketgan xarajat miqdorlari.

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:

9.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

Yechish:

Qo'yilgan masalani yechish uchun 9.2-jadval ko'rsatkichlarini 9.1-jadval ko'rinishida ifodalab, 9.3-jadvalni hosil qilamiz. 9.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.

9.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:

9.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
U1q0	Makka-jo’xori	- 50 1000	+ 40	20	15	1000
U2q19	Bug’doy	20	- 12 1800	11 3500	+7 700	6000
U3q16	Arpa	22	15 1200	10	9	1200
U4q22	Tariq	+ 28 1000	10	6	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₄ =28 v₄ –22 = 4 26 – u₂ = 7

v₁ = 50 u₄ = 28 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, 9.4-jadval hosil qilinadi. 9.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.

9.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

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
2-shart to'liq bajarildi, demak 9.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 = ?

	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	95	90	80	350
A	45	30	50	40	55	200
A	10	25	35	15	30	200
	300	200	300	100	100	1000