Maksimal oqim haqidagi masalaning qo`yilishi. Uchlar to`plami va dan olingan uchlar juftliklarini tutashtiruvchi



Download 137,98 Kb.
bet1/2
Sana17.04.2022
Hajmi137,98 Kb.
#558411
  1   2
Bog'liq
Maksimal oqim haqidagi masalaning q1


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 (R,R) kesim 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. 

o’lchovli 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) yo’lni 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.

Download 137,98 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish