linkedin facebook linkedin facebook nod32

Maksimal oqim haqidagi masala

Muallif: Mengliyev Sh.

Qo`shilgan sana: 2015-02-21

Maksimal oqim haqidagi masala.

Maksimal oqim haqidagi masalaning qo`yilishi. Uchlar to`plami va dan olingan uchlar juftliklarini tutashtiruvchi yoylar to`plamidan tashkil topgan G=(,) tarmoq berilgan bo'lsin. Bu tarmoq simmetrik grafikdan iborat bo`lsin deb faraz qilamiz, ya’ni (i,j) yoy tarmokga karashli bo`lsa, (i,j) yoy xam unga karashli. Tarmoq uchlarini (a0,a1,a2......an)deb nomerlab chiqamiz ={a0,a1,a2......an} U vaqtda (i,j) yoy (ai,aj) kabi xam yoziladi.

Xar bir uch uning intensivligini ifodalovchi d(ai) son bilan xarakterlanadi. d(ai)>0 bo`lgan uchga manba (ai-ishlab chiqarish punkti) deb, d(ai)bo`lgan uchga yaqin ai - iste’mol punkti deb, d(ai)=0 bo`lgan uchlarga esa oralik uchlar deb aytiladi. Tarmoq yo`llari buylab manbalardan yig`inlarga biror bir jinsli moddaning (masalan, gaz, suyuqlik yoki boshqa biror resurs) oqimi kuzatilayotgan bo`lsin. Xar bir (ai,aj) yoyga bij

son mos kuyilgan bo`lib, bu songa yoyning okimni o`tkazish kobilyati deyiladi. YOyning utkazish kobilyati deganda uning vakt birligi ichida utkazishi mumkin bulgan modda mikdorini tushunamiz.

Faraz qilaylik, bo`lsin, ya’ni a0 -yagona manba, an yagona yechim, a1,a2......an-1 oraliq uchlardir. Xar bir yoydan vaqt birligida o`tgan modda mikdorini xij deb belgilaymiz va uni yoy bo`ylab okim deb ataymiz. Agar tarmokda (i,j) yo`l, ya’ni (ai,aj) yoy mavjud bo`lmasa, unga mos oqim xij=0.

Tarmoqdagi a0 mambadan an yiginga okim deb barcha (ai,aj) yoylar bo`ylab xij oqimlar yig`indisiga aytiladi. Bu oqim (1)
formula bo`yicha aniqlanadi. Masala tarmoqdagi maksimal oqimni topishdan iborat.
Agar simmetrik yoylarning utkazish qobilyatlari bir-biriga teng bo`lsalar bu yoylarni kirlarga almashtirish mumkin. Shunga asosan masalaning quyilishi aralash va orientirlanmagan graflar uchun xam o`rinlidir. Masalaning qo`yilishiga ko`ra xar bir oraliq

uchga boshqa uchlardan keladigan moddalar yigiindisi shu uchdan chiqadigan moddalar jamisiga teng, ya’ni

Bundan tashqari

Shunday qilib, qo'yilgan masalani matematik ko`rinishda (1) formula bilan aniqlangan v funksiyaning (2), (3) shartlarda maksimumini topishdan iborat deb qarash mumkin.
Maksimal oqim masalasini xal qilish algoritmini asoslashda kesim tushunchasi muxim rol o`ynaydi. Tarmoqning uchlar to`plami

ni shunday kesishmaydigan to`plamlarga ajratamizki  bo`lsin.

  a0 ni an dan ajratuvchi kesim deb barcha (ai, aj) yoylarning shunday to`plamiga aytiladiki, ular uchdan chiqib

uchga kirishadi.

Xar bir kesim b utkazish kobilyati bilan xarakterlanadi. Kesimning utkazish kobilyati.

 

formula yordamida xisoblanadi. Kesimning ta’rifidan kœrinib turibdiki, manbadan yiginga boruvchi istalgan yul kesimning xech bulmaganda bitta yoyini uz ichiga oladi. SHuning uchun kandaydir kesimning barcha yoylarini olib tashlasak manbadan yiginga boradigan birorta xam yul mavjud bulmaydi. Yulning utkazish kobilyati shu yulga kiruvchi yoylarning utkazish kobilyatlarining eng kichigiga teng bulgani uchun okimning v kattaligi, ya’ni a0 ni an bilan boglovchi barcha mumkin bulgan yullar buyicha olib utiladigan okim mikdori istalgan kesimning utkazish kobilyatidan oshmaydi: . Demak, agar shunday okim topilsaki uning v* kattaligi biror kesimning utkazish kobilyatiga teng bulsa, ya’ni tenglik bajarilsa, shu okim maksimal va minimal utkazish kobilyatli buladi.Maksimal okim xakidagi masalani echish algoritmi. Ford-Falkerson teoremasi.Teorema (Ford-Falkerson). Xar kanday tarmokda a0 mambadan an yiginga maksimal okim mikdori a0 ni an larni bir-biridan ajratuvchi kesimlarning minimal utkazish kobilyatiga teng.
Endi Fordning maksimal okimini topish algoritmining jadval kurinishni karaymiz. Dastlabki kadam.

ulchovli jadvalga yoylarning utkazish kobilyatlarini yozib chikamiz, bunda n+1 -karalayotgan G=(V,E) tarmokdagi uchlar soni.

 (ai,aj) yoyning utkazish kobilyati bij noldan katta bulsa va simmetrik yoy (aj,ai) ning utkazish kobilyati nolga teng bœlsa (i,j) katakka bij ni (j,i) katakka esa nolь yozamiz. Agarda bij=bji=0 bo`lsa (i,j) va (j,i) kataklarga xech narsa yozmaymiz.

Umumiy kadam. 1) a0 dan an ga utkazish kobilyati noldan katta bulgan yulni topamiz. Buning uchun a0 ga mos ustunga * belgisi kuyamiz. a0 katorda b0j>0 bulgan ustunlarni topib karalayotgan kator tepasiga 0 (nolь) rakami bilan belgi kuyamiz. Natijada musbat utkazish kobilyatiga ega bulgan barcha (a0,aj) yoylar ajratiladi. Ular a0 dan an ga boruvchi yulning dastlabki yoylari bulishadi. Keyin ustunlari belgilangan nomerli katorlarni karaymiz. Xar bir, masalan ai katorda, belgilangan ustunlar uchun bij>0 bo`lgan elementlarni topamiz va ularni karalayotgan kator nomeri bilan nomerlaymiz. SHunday kilib, a0 dan an ga boruvchi yulning keyingi yoylarini topgan bulamiz. Katorlarni karashni shu vaktgacha davom ettiramizki: a) yo an ustun belgilangan xolga kelamiz (bu xol a0 dan an ga boruvchi musbat o‘tkazish kobilyati yo‘l topilganligi bildiradi); b) yoki yangi ustunlarni belgilash mumkin emasligi xakida xulosa kilamiz. (karalayotgan katorlar uchun belgilanmagan ustunlarda musbat elementlar mavjud emas). Bu xolda musbat utkazish kobliyatiga ega bo‘lgan a0 dan an ga boruvchi yo‘l mavjud emas.

«a)» xolda ustunlar belgilaridan foydalanib izlangan a0 dan an ga μ yulni topamiz. Faraz kilaylik yo‘lning oxirgi uchi an k bilan bilan belgilangan bo‘lsin. SHu belgi yordamida an oldingi ak uchni topamiz ( ak katorni karaganda an ustun bilan yo‘ldagi eng oxirgi (ak, an) yoy belgilangan edi). ak qator an ustun kesishish nuktasidagi bkn elementni minus belgi bilan belgilaymiz. Mos simmetrik element bnk ni esa plyus belgisi bilan belgilaymiz. Natijada va sonlarni xosil kilamiz.

 ak kator karalgani uchun undan oldin, aytaylik r nomer bilan, ak ustun belgilangan edi. SHuning uchun elementdan ak ustun bo‘ylab r katorgacha xarakat kilamiz va brk ni minus belgisi bilan, brk ni esa minus belgisi bilan belgilaymiz. Bu jarayonni a0 katorga kelguncha va shu kator elementini minus ishorasi bilan va simmetrik elementni plyus ishorasi bilan belgilaguncha davom ettiramiz. Sungra 2-punktga o‘tamiz. «b)» xolda yiginga mos an ustunni belgilash mumkin emas. SHu sababli noldan katta o‘tkazish kobilyatiga ega bo‘lgan a0 dan an ga boshka yo‘l mavjud emas, demak umumiy kadam tugaydi. Jadvalning belgilangan ustunlarida joylashgan uchlar R to‘plamni tashkil etadi (a0 manbadan bu uchlarga boradigan kandaydir yo‘l mavjud). Kolgan uchlar to‘plamga karashli. uchdan chikib uchga kiruvchi yoylar minimal o‘tkazish kobilyatiga ega bo‘lgan kesim tashkil kilishadi va bu erda bij berilgan tarmoq (i,j)

yoyning o‘tkazish kobilyatini ifodalaydi.

2) Topilgan μ yo‘lning o‘tkazish kobilyati θ ni topamiz. Yo‘lning o‘tkazish kobiliyati deganda vakt birligi ichida a0 dan an ga μ yo‘l buyicha utkazish mumkin bulgan moddaning maksimal mikdorini tushunamiz. Yo‘lning o‘tkazish kobilyati shu yo‘lga kiruvchi yoylarning utkazish kobilyatlarining eng kichigiga teng:

3) Topilgan yul yoylarining va ularga simmetrik yoylarning kolgan o‘tkazish kobilyatlarini aniklaymiz. Buning uchun jadvalning

  bij- elementlaridan θ ni ayiramiz, bij+ elementlarga esa θ

ni kushamiz. Bu amallarni bajargandan sung utkazish kobiliyatlari uzgargan dastlabki jadvalga uxshash yangi jadvalni xosil kilamiz. YAngi jadvalni xosil kilgandan sung umumiy kadamning 1-punktiga kaytamiz va uni a0 dan an ga utkazish kobilyati noldan katta bulgan yo‘l mavjud bulmagan jadval xosil bulguncha davom ettiramiz. Xal qiluvchi kadam. Dastlabki jadvalning elementlaridan oxirgi kadamda xosil bulgan jadvalning mos elementlarini ayiramiz. Natijada musbat elementlari (ai, aj) yoyning mos xij okim miqdorlariga teng bulgan jadvalni xosil qilamiz. Tarmokdagi maksimal oqim esa a0 qator an ustunning elementlari yigindisiga teng bo`ladi, ya’ni

Misol. quyida chizmada berilgan tarmoq uchun a0 uchdan aμ maksimal oqimni toping. YOy va qirralarga yozilgan sonlar ularning utkazish qobilyatlarini bildiradi.

Dastlabki qadam. 1-jadvalni tuzamiz.
1-jadval.

 

 

(*)

 

(0)

 

(0)

 

(1)

 

(2)


ai aj

 

a0 

a1 

 

a2 

 

a3 

 

a4 

 

a0 

 

 

 

17

 

19-

 

 

a1 

 

 

0

 

 

4

 

12

 

a2  

 

 

0+

 

4

 

 

8

 

9-

 

a3 

 

 

12

 

6

 

 

24

 

a4 

 

 

 

0+

 

0

 

Birinchi qadam. μ 1=(a0-a2-a4)

yulni xosil qilamiz.
2) topilgan yo`lning o`tkazish qobilyatini aniklaymiz:

) Topilgan yo`l yoylari o`tkazish qobilyatlarini θ 1=9 ga kamaytirib, simmetrik yoylarning utkazish qobilyatlarini esa 9 ga oshiramiz. Natijada 2-jadvalga ega bo`lamiz.

2-jadval.

 

 

 

(*)

 

(0)

 

(0)

 

(1)

 

(2)

ai aj  

 

a0 

 

a1  

 

a2

 

a3 

 

a4 

 

a0 

 

 

17-

 

10

 

 

a1 

 

0+

 

 

4

 

12-

 

a2 

 

 

9

 

4

 

 

8

 

0

 

a3 

 

 

12+

 

6

 

 

24-

a4 

 

 

 

 

9

 

0+

 

Ikkinchi qadam. 1) μ2=(a0-a1-a3-a4) yo`lni topamiz.

2) μ2 yo`lning o`tkazish qobilyati

buladi.
3) Yangi 3-jadvalni xosil qilamiz.

 

 

(*)

 

(0)

 

(0)

 

(2)

 

(3)

ai aj

a0 

 

a1 

 

a2 

 

a3 

 

a4 

 

 

a0 

 

 

5

 

10-

 

 

 

a1 

 

12

 

 

4

 

0

 

a2 

 

 

9+

 

4

 

 

8-

 

0

a3 

 

 

 

24

 

6+

 

 

12-

a4 

 

 

 

 

9

 

12+

 

Uchinchi qadam. 1) μ3=(a0-a2-a3-a4) 2)

3) Navbatdagi jadvalni tuzamiz.
4-javal.

 

 

(*)

 

(0)

 

(0)

 

 

ai aj

 

a0 

 

a1 

 

a2 

 

a3 

 

a4 

a0

 

 

5

 

2

 

 

a1 

 

 

12

 

 

4

 

0

 

a2 

 

 

17

 

4

 

 

0

 

0

 

a3 

 

 

24

 

14

 

 

4

 

a4;

 

 

 

9

 

20

 

 

To`rtinchi qadam. 1) 4-jadvalda a<3 va a4

ustunlarni nomerlash mumkin emas

.

Xal qiluvchi qadam. 4-jadval elementlaridan 1-jadvalning mos elementlarini ayirib, 5-jadvalni xosil qilamiz.
5-jadval.

ai aj

 

a0 

 

a1 

 

a2 

a3 

 

 

a4 

 

a0 

 

 

12

 

17

 

 

a1

 

-12

 

 

0

 

12

 

a2 

 

 

-17

 

 

 

8

 

9

a3 

 

 

 

-12

 

-8

 

 

20

a4 

 

 

 

 

-9

 

-20

 

 

Bu oxirgi jadvaldagi musbat elementlar yoylardagi oqimlar kattaliklarini bildiradi:

778 marta o`qildi.

Parol:
Eslab qolish.


Ro`yhatdan o`tish

testing

+998915878681

Siz o`z maxsulotingizni 3D reklama ko`rinishda bo`lishini xohlaysizmi? Unda xamkorlik qilamiz.

3D Reklama


Рейтинг@Mail.ru
Рейтинг@Mail.ru

Besucherzahler
счетчик посещений