Identifikatsiyalash

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.