Transport masalasining matematik modeli

"Kichik elementlar" usuli.
"Kichik elementlar" usuli yordamida tayanch planni topish quyidagicha amalga oshiriladi:
1.Yuklar qabul qiluvchilarga tarif jadvalidagi eng kichik cij tashish narxiga mos katakni to‘ldirishdan boshlanadi.
2.Eng kichik tarif c_ij katagiga a_i yoki b_j ning eng kichigi joylashtriladi.
3.Keyin to‘lig‘icha yuk zapaslari sarf qilingan satr yoki qabul qilish punkti talabi qondirilgach mos ustun yo‘qotiladi.
4.Agar jo‘natish punktidagi yuk zapaslari to‘liq taqsimlangan bo‘lsa va qabul qiluvchi talabi to‘liq qanotlantirilsa ularga mos satr va ustun yo‘qotiladi.
5.Qolgan satr va ustunlardan yana kichik ta'rif olinadi. Yuk zapaslarini taqsimlash jarayoni, toki yuk zapasi tugaguncha va talablar qanoatlantirilguncha davom etadi.


Potensiallar usuli.
Agar yuqoridagi usullar yordamida boshlang‘ich tayanch plan topilgan bo‘lsa optimal planni topish potensiallar usulida bajariladi.
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.Bo‘sh kataklarda potensiallar yig‘indisi hisoblanadi сў_ij = u_i+v_j.
4.Bo‘sh kataklarda c_ij va сў_ij tariflar farqi hisoblanadi.
S_ij = c_ij +сў_ij= c_ij -( u_i+v_j ).
5.Agar hamma bo‘sh kataklardagi fark S_ij>0 bo‘lsa olingan plan optimal bo‘ladi.
6.Agar bo‘sh kataklardan birortasida S_ij<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.


Misol.
Quyidagi jadvalda berilgan transport masalasini yeching

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

Yechish: 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, yani 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 yopilgan, 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.
Yechish: 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 hisoblashlarda 3-chi ustun qaralmaydi. Keyingi eng kichik elementni topamiz. Bu element (1,4) va (2,2) kataklarda joylashgan, ya'ni с₁₄=2 va с₂₂=2. Yuklarni bu kataklarga joylaymiz. X₁₄=min(60-20,50)=40, X₂₂=min(40,25)=25. Ikkinchi talabgor talabi qanoatlantirildi, shu tufayli keyingi hisoblashlarda 2-chi ustun qaralmaydi.
Keyingi eng kichik elementlar (2,4) va (3,2) kataklarda joylashgan, ya'ni с₂₄=3 va с₃₂=3. Bu kataklarga yuklarni joylashtiramiz X₂₄=min(40-25,50-40)=10. (3,2) katak qaralmaydi, chunki bu ustun hisobdan chiqarilgan. Keyingi eng kichik elementni izlaymiz, bu element с₂₁=4. Yukni bu katakga joylaymiz X₂₁=min(15-10, 40)=5. Eng oxirgi kichik element с₃₁=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 hisoblaymiz Z=415.
Endi masalaning optimal planini topamiz. Optimal planni topish uchun potensiallar usulidan foydalanamiz. 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 qanoanlantiradi.

r=3+4-1=6
Yukni jo‘natuvchi va talabgorlar potensialini aniqlaymiz 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 holda qolgan potensiallar quyidagicha aniqlanadi
u₁=0, v₃=1, v₄=2, u₂=1, v₂=1, v₁=3, u₃=4.

Bo‘sh kataklarda s_ij qiymatini quyidagi 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 bo‘yicha yoki unga teskari yo‘nalishda (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
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.