Bob. Transport masalasi va uni echish usullari

2.1.1.Transport masalasining tayanch rejasini topish usullari


Transport jadvalini tuzish. Chiziqli programmalashtirish amaliyotga tadbiqlaridan biri transport masalasidir. Transport masalasining qoʻyilishi quyidagicha: m ta joʻnatish punkti mavjud boʻlib, ularga mos ravishda miqdorli bir jinsli tovar mavjud boʻlsin. Shuningdek n ta qabul qilish punkti mavjud boʻlib, ularga mos ravishda tovarga talablar boʻlsin. Bunda

shart bajarilsin. Shuningdek bir birlik tovarni joʻnatish harajati ma’lum boʻlsin . Talab qilinadi, 1-barcha talablar bajarilsin, 2-bunda tashish harajati minimal boʻlsin. Bu masalaga matematik koʻrinish beramiz. Buning uchun i dan j qabul qilish punktiga olib boriladigan yukning hajmini deb belgilaymiz. Bunda . Shu asosida tenglamalar sistemasi tuziladi: joʻnatish punktiga nisbatan:
,
qabul qilish punktiga nisbatan esa:
.
Maqsad funksiyani olamiz:

Chiziqli programmalashtirishdan bu masalaning farqi shundaki: 1-dan, chegaraviy shartlar tenglama sifatida beriladi. 2-dan, oʻzgaruvchilarning koeffitsientlari 1 ga teng.
Bu masalani echishda transport jadvali tuzib olinadi.

	B1		B2		... ... ...	Bn		Zahira
A1		C11		C12			C1n	a1
A2		C21		C22			C2n	a2
... ... ...								... ... ...
Am		Cm1		Cm2			Cmn	am
Talab	b1		b2		... ... ...	bn

Transport masalasini echish 3 bosqichdan iborat:

1. 
   Transport jadvalini tuzish.
   
2. 
   Tayanch rejani aniqlash.
   
3. 
   Optimal rejani aniqlash.
   

Tayanch rejani topishning 3 xil usuli mavjud:

1. 
   Shimoli-Gʻarbiy burchak usuli.
   
2. 
   Minimal elementlar usuli.
   
3. 
   Fogel usuli.
   

Shimoli-gʻarbiy burchak usuli. (Shgʻb). Shgʻb qoidasi moxiyati quyidagilardan iborat: TJ tuziladi, keyin chap yuqori (Shgʻ) burchakdan boshlab qator boʻyicha oʻnga yoki ustun boʻyicha pastga qarab (1,1) katakka a₁ va b₁ sonlardan kichigini kiritamiz, ya’ni (a₁b₁).
Agar a₁>b₁, boʻlsa x₁₁=b₁ va birinchi ustun yopildi. Qolgan kataklarni esa qilib olinadi. Bu esa birinchi talabgar (QQP) toʻliq ta’minlangan xisoblanadi. Va ikkinchi ustinnig birinchi katagiga (1,2) esa a₁-b₁ va b₂ sonlardan kichigini ya’ni ni kichigini kiritamiz.
Agar b₁=a₁, boʻlsa x₁₁=a₁ va birinchi qatorning birinchi kataklari x_1k=0 K=2, n qilib olinadi. Va keyingi qatorning birinchi katagiga (2,1) boʻladi. Ikkinchi katakni toʻldirgandan keyin (1,2) yoki (2,1) keyingi 3-katakka oʻtiladi yoki qator, yoki ustun boʻyicha jarayon to xamma yukni taqsimlanib tugaguncha davom etadi.

1. 
   Shimoli-Gʻarbiy usul
   

QQP JP	1		2		3		4			Zahira
1		100		300		200		70	70
		60		10
2		60		80		100		40	90
				60		30
3		30		200		100		30	90
						60		30
Talab	60		70		90		30			250

SHGʻB usulining kamchiligi shundaki, yoʻl narxi e’tiborga olinmaydi, shuning uchun optimaldan uzoq.

Kichik elementlar usuli. Bu usulning moxiyati quyidagicha: xar bir qadamda kataklar yoʻl narxlari e’tiborga olingan xolda eng oqilona toʻldiriladi. Tablitsaning kataklari butun ta’rif (narxlar) matritsasining eng kichik elementidan boshlab toʻldiriladi. Ustun (yoki qator) ning qoldigʻini shu ustun (yoki kator)ning qolgan eng kichik katagiga yoziladi va oxirigacha davom ettiriladi.

QQP JP	B1	B2	B3	B4	Zaxiralar
A1	6	7 5	3 60	5 35	100
A2	1 75	2 75	5	6	150
A3	3	10	20	1 50	50
Talablar	75	80	60	85	300

Birinchi ustunda (2,1) katakda eng arzon narx . Ikkinchi ustunda eng arzon (2,2) va shu ustunda keyingi arzonroq katak (1,2) qoldiq esa 5 . Uchinchi ustunda eng arzon (1,3) va xakozo.

Fogel usuli. Bu usulning moxiyati shundaki, xar bir ustun va qatorlardagi narxlarning eng kichik ikkitasini farqi aniqlanadi. Va shu farqlardan eng kattasini tanlab shu tanlangan qator va ustunlardagi eng kichik narxlar boʻyicha oqilona tashish rejasi tuziladi. Va shu qator va ustunlarni keyingi etaplarda ishtirok ettiramiz.
Transport masalasiga doir misol. Quyidagi jadvalda berilgan transport masalasini eching

bk ai	40	25	20	50
60	5	4	1	2
40	4	2	6	3
35	7	3	5	4

Echish: Boshlangʻich tayanch planni «Shimoliy-gʻarb burchak» va «Kichik elementlar» usulida topamiz. «Shimoliy-gʻarb burchagi» usuli qoidasiga binoan jadvalning (1,1) katagiga X_1,1=min(60,40)=40 sonini joylashtiramiz, keyingi X₁₂=min(60-40,25)=20 sonini (1,2) katagiga joylaymiz. Shu bilan birinchi punktda yuk tugadi va keyingi kataklar (1,3) va (1,4) yopildi.
Keyingi punktdagi yuklarni taqsimlashni boshlaymiz. (2,2) katakga X₂₂=min(40,5)=5 sonini joylashtiramiz. Shu bilan 1-chi va 2-chi talabgorlar talabi qondirildi, ya’ni 1-chi va 2-chi ustun yopildi. (2,3) katakka X₂₃=min(35,20)=20 joylashtiriladi. 3-chi talabgor talabi bajarildi. qolgan yukni (2,4) katakka joylashtiramiz, ya’ni X₂₄=min(15,50)=15 va ikkinchi joʻnatish punktida yuk tugadi. 3-chi joʻnatish punktidagi yukni taqsimlashni boshlaymiz. (3,1),(3,2),(3,3) kataklar epilgan, ya’ni 1,2 va 3 talabgorlar talabi qondirilgan. (3,4) katakka X₃₄=min(35,35)=35 yozamiz. Shu bilan yuklar toʻliq taqsimlandi, ya’ni quyidagi planga ega boʻldik.

Maqsad funksiyasi qiymati Z=595 ni tashkil qiladi.
Qoʻyilgan masalaning tayanch planini endi «Eng kichik elementlar» usuli bilan topamiz.
Echish: Ustun yoki satr boʻyicha eng kichik xarajatni topamiz.
Satr boʻyicha bu element (1;3) katakda joylashgan, ya’ni c₁₃ =1. Shuning uchun bu katakga X₁₃=min(60,20)=20 yukni joylaymiz. Uchinchi talabgorning talabi qanoatlantirildi. Shu tufayli keyingi xisoblashlarda 3-chi ustun qaralmaydi. Keyingi eng kichik elementni topamiz. Bu element (1,4) va (2,2) kataklarda joylashgan, ya’ni s₁₄=2 va s₂₂=2. Yuklarni bu kataklarga joylaymiz. X₁₄=min(60-20,50)=40, X₂₂=min(40,25)=25. Ikkinchi talabgor talabi qanoatlantirildi, shu tufayli keyingi xisoblashlarda 2-chi ustun qaralmaydi.
Keyingi eng kichik elementlar (2,4) va (3,2) kataklarda joylashgan, ya’ni s₂₄=3 va s₃₂=3. Bu kataklarga yuklarni joylashtiramiz X₂₄=min(40-25,50-40)=10. (3,2) katak qaralmaydi, Chunki bu ustun xisobdan chiqarilgan. Keyingi eng kichik elementni izlaymiz, bu element s₂₁=4. YUkni bu katakga joylaymiz X₂₁=min(15-10, 40)=5. Eng oxirgi kichik element s₃₁=7. Bu katakga ham yukni joylaymiz X₃₁=min(35,40-5)=35. Natijada yuklarni taqsimlab, boshlangʻich tayanch planga ega boʻldik, ya’ni

Maqsad funksiyasini xisoblaymiz Z=415.

1. 
   Endi masalaning optimal planini topamiz. Optimal planni topish uchun potensiallar usulidan foydalanamiz. Taqsimlash usulida boʻsh kataklarga nisbatan berk sikl tuziladi.
   

Berk sikl deb, transport jadvalining qatori va ustunidagi 2 ta katakni oʻzaro birlashtirib turuvchi va oxiri boshlanish kataliga mos tushadigan chiziqqa aytiladi. Taqsimot usuli Simpleks usuliga oʻxshash boʻlib, barcha boʻsh kataklarga yuk tashlash imkoniyati tekshirib chiqiladi. Bu jarayon anchagina murakkabdir. Shuning uchun potensiallar usuli keng qoʻllaniladi.
Potensiallar usulining mohiyati quyidagichadir: tayanch reja topilgandan soʻng joʻnatuvchi punktlarga U_i, qabul qiluvchi punktlara V_j belgisini kiritamiz. Bu belgilashlar potensiallar deyiladi. potensiallar yigʻindisi kataklarning tariflariga teng boʻladi. Agarda tayanch reja bazis yechim boʻlsa, ya’ni band kataklar soni r = m+n-1 ga teng boʻlsa, hamda band kataklar uchun berk siklni topish imkoni boʻlmasa, band va boʻsh kataklar uchun tenglamalar sistemasi tuziladi. Tenglamalar sistemasidagi oʻzgaruvchilar soni m+n ga teng boʻladi va tenglamalar soni r ga teng boʻladi. Shuning uchun band kataklarga nisbatan tuzilgan tenglamalar sistemasining ixtiyoriy oʻzgaruvchisiga 0 qiymati berilib, U_i va V_j ning qiymatlari aniqlanadi. Bu qiymatlar boʻsh kataklar uchun tuzilgan tenglamalar sistemasiga qoʻyiladi.
Agarda bu sistemada shart bajarilsa, optimal yechim topilgan hisoblanadi. Aks holda bajarilgan boʻsh katakka yuk tashlanadi. Qaysi band katakka yuk tashlash boʻsh katakka nisbatan tuzilgan berk sikl orqali aniqlanadi. Berk siklda faqatgina uning bitta tuguni boʻsh katakda yotadi, qolganlari esa band katakda yotishlari zarur. Toq sonli kataklar “+”, juft katakdagi sonlar esa “-” deb belgilanadi. “-” ishorali eng kichik yuk hajmi topilib, unga nisbatan oʻzgartirish amalgam oshiriladi.
Transport masalasi optimal planni topishning potensiallar usuli quyidagilardan iborat:

1. 
   Yuqoridagi keltirilgan usullar yordamida yuklarni tashishning tayanch plani aniqlanadi.
   
2. 
   Mos ravishda yuklarni qabul qiluvchi va joʻnatuvchi punktlar uchun u_i va v_j potensiallari aniqlanadi.
   
3. 
   Bush kataklarda potensiallar yigʻindisi hisoblanadi sў_ij = u_i+v_j.
   
4. 
   Boʻsh kataklarda c_ij va sў_ij ta’riflar farqi hisoblanadi.
   

S_ij = c_ij +sў_ij= c_ij -( u_i+v_j).

5. 
   Agar, xamma boʻsh kataklardagi fark Sij>0 boʻlsa olingan plan optimal boʻladi.
   
6. 
   Agar, boʻsh kataklardan birortasida Sij<0 boʻlib qolsa, boʻsh boʻlmagan kataklarga x_ij oʻzgaruvchi qiymati kiritiladi, ya’ni yuqoridagi farq minimal boʻlsin. SHu katak uchun boʻsh boʻlmagan kataklar yordamida yopiq kontur xosil qilinadi va yuklar shu konturda qayta taqsimlanadi. Natijada yangi tashish planga ega boʻlamiz.
   

Bu jarayon toki farq S_ij>0 boʻlmaguncha davom etadi va oxirgi olingan yuklarni tashish plani optimal boʻladi.
Boshlangʻich tayanch plan «Eng kichik elementlar» usulida topilgan deylik. Uni quyidagi jadval koʻrinishida yozamiz.

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
40	+ 4 5	- 2 25	6	3 10	1
35	- 7 35	+ 3	5	4	4
v	3	1	1	2

Jadvalda boʻsh boʻlmagan kataklar quyidagi shartni qanoanlantiriadi.
r=3+4-1=6
Yukni joʻnatuvchi va talabgorlar potensialini aniqaymiz va quyidagi tenglamalarga ega boʻlamiz.
u₁+v₃=1; u₁+v₄=2 ; u₂+v₁=4
u₂+v₂=2; u₂+v₄=3 ; u₃+v₁=7
Ma’lumki, tenglamalar soni noma’lumlar sonidan 1 ta kam, ya’ni noma’lumlar 1 tasi ozod va u istalgan qiymat olishi mumkin. Misol uchun aytaylik, u₁=0. U xolda qolgan potensiallar quyidagicha aniqlanadi:
u₁=0, v₃=1, v₄=2, u₂=1, v₂=1, v₁=3, u₃=4.
Boʻsh kataklarda s_ij qiymatini qoʻyidagi formula bilan aniqlaymiz S_ij=c_ij-(u_i+v_j). U holda
S₁₁=5-(0+3)=2; S₁₂=4-(0+1)=3; S₂₃=6-(1+1)=4;
S₃₂=3-(4+1)=-2; S₁₁=5-(4+1)=0; S₃₄=4-(4-+2)=-2.
Olingan plan optimal boʻla olmaydi, chunki s_ij lar ichida manfiylari ham mavjud S₃₂=S₃₄==-2. Bu kataklar uchun yopiq kontur (sikl) hosil qilamiz. (3,2) katak uchun kontur (3,2),(3,1),(2,1),(2,2). Konturni soat strelkasi yoki unga teskari boʻyicha (3,2) katakdan boshlab ketma-ket + va - ishoralarini qoʻyib chiqamiz. Manfiy kataklardan eng kichigini tanlaymiz min(25;35)=25, ya’ni x₂₂=25. Kataklarda yuklarni qayta taqsimlaymiz. Taqsimlanishda umumiy balans bu kataklarda buzilmasin va xarajatlar minimal boʻlsin. Minusli katak (2,2) dagi yukni keyingi musbat katakdagi yukga qoʻshamiz. U holda (2,1) katakda yuk 5+25=30 boʻladi. Balans buzilmaslik uchun (3,1) katakdagi yukdan 25 birligini (3,2) katakga yuklaymiz. Shunday qilib, yangi planga ega boʻldik. Bu jadval uchun potensiallarni aniqlaymiz va boʻsh kataklarda s_ij larni hisoblaymiz:
S₁₁=5-(0+3)=2; S₁₂=4-(0+1)=3; S₂₃=6-(1+1)=4;
S₂₂=2-(2+1)=0; S₃₃=5-(4+1)=0; S₃₄=4-(4-+2)=-2;

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
40	+ 4 30	2 0	6	- 3 10	1
35	- 7 10	3 25	5	+ 4	4
v	3	1	1	2

Yangi olingan plan ham optimal emas, chunki S₃₄=-2. Yopiq kontur tuzamiz va yuklarni bu kontur ichida qayta taqsimlaymiz va natijada quyidagi planga ega boʻlamiz

bk ai	40	25	20	50	u
60	5	4	1 20	2 40	0
40	4 40	2 0	6	3	1
35	7	3 25	5	4 10	2
V	3	1	1	2

Olingan plan optimal plan, chunki barcha boʻsh kataklarda S_ij lar musbat. Demak, optimal plan quyidagicha boʻladi.

Maqsad funksiyasining qiymati z_min=375.
Ochiq modelli transport masalasi. Ba’zi transport masalalarida yuk zapaslari talablar yigʻindisidan kichik yoki katta boʻlishi mumkin. Bunday masalalar ochiq turdagi transport masalasi deyiladi. Bunday hollarda soxta (fiktiv) m+1 joʻnatish yoki n+1 qabul (is’temol) qiluvchi punktlari kiritiladi, ya’ni
yoki
.
Bu punktlarda transport xarajatlari nulga teng qilib olinadi, ya’ni c_m+1,_j=0 yoki c_i,n+1=0.
Misol. Quyidagi ochiq modelli transport masalasini eching.

bk ai	3	3	3	2	2
4	3	2	1	2	3
5	5	4	3	1	1
7	0	2	3	4	5

Bu masalada

Shuning uchun oltinchi soxta talabgorni kiritamiz, uning talabi b₆=16-13=3 boʻladi. Bu soxta punktni kiritib, masalani quyidagicha yozamiz.

bk ai	3	3	3	2	2	3
4	3	2	1	2	3	0
5	5	4	3	1	1	0
7	0	2	3	4	5	0

Bu masalani echib 7-siklda optimal echimni topamiz, ya’ni

x₁₂=1, x₁₃=3,
x₂₄=2, x₂₅=2, x₂₆=1,
x₃₁=3, x₃₂=2, x₃₆=2,
y_min=1·2+1·3+1·2+1·2+1·0+0·3+2·2+2·0=13