Transport masalasining matematik modeli


"Kichik elementlar" usuli



Yüklə 89,79 Kb.
səhifə3/4
tarix12.12.2022
ölçüsü89,79 Kb.
#74048
1   2   3   4
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 cij katagiga ai yoki bj 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 ui va vj potensiallari aniqlanadi.
3.Bo‘sh kataklarda potensiallar yig‘indisi hisoblanadi сўij = ui+vj.
4.Bo‘sh kataklarda cij va сўij tariflar farqi hisoblanadi.
Sij = cij +сўij= cij -( ui+vj ).
5.Agar hamma 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 xij 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 Sij>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 X1,1=min(60,40)=40 sonini joylashtiramiz, keyingi X12=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 X22=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 X23=min(35,20)=20 joylashtiriladi. 3-chi talabgor talabi bajarildi. qolgan yukni (2,4) katakka joylashtiramiz, ya'ni X24=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 X34=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 c13 =1. Shuning uchun bu katakga X13=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 с14=2 va с22=2. Yuklarni bu kataklarga joylaymiz. X14=min(60-20,50)=40, X22=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 с24=3 va с32=3. Bu kataklarga yuklarni joylashtiramiz X24=min(40-25,50-40)=10. (3,2) katak qaralmaydi, chunki bu ustun hisobdan chiqarilgan. Keyingi eng kichik elementni izlaymiz, bu element с21=4. Yukni bu katakga joylaymiz X21=min(15-10, 40)=5. Eng oxirgi kichik element с31=7. Bu katakga ham yukni joylaymiz X31=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.
u1+v3=1; u1+v4=2 ; u2+v1=4; u2+v2=2; u2+v4=3 ; u3+v1=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 u1=0. U holda qolgan potensiallar quyidagicha aniqlanadi
u1=0, v3=1, v4=2, u2=1, v2=1, v1=3, u3=4.

Bo‘sh kataklarda sij qiymatini quyidagi formula bilan aniqlaymiz Sij=cij-(ui+vj). U holda


S11=5-(0+3)=2; S12=4-(0+1)=3; S23=6-(1+1)=4;
S32=3-(4+1)=-2; S11=5-(4+1)=0; S34=4-(4-+2)=-2.
Olingan plan optimal bo‘la olmaydi, chunki sij lar ichida manfiylari ham mavjud S32=S34==-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 x22=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 sij larni hisoblaymiz:
S11=5-(0+3)=2; S12=4-(0+1)=3; S23=6-(1+1)=4;
S22=2-(2+1)=0; S33=5-(4+1)=0; S34=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 S34=-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 Sij lar musbat. Demak, optimal plan quyidagicha bo‘ladi.

Maqsad funksiyasining qiymati zmin=375.

Yüklə 89,79 Kb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin