O’zbekiston respublikasi oliy va o’rta maxsus ta`lim vazirligi fag’ona davlat universiteti matematika va informatika fakulteti amaliy matematika va informatika yo’nlishi



Download 145,04 Kb.
bet1/2
Sana20.06.2022
Hajmi145,04 Kb.
#684822
  1   2
Bog'liq
Ra\'no Maxmutaliyeva 18.08 Word


O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA`LIM VAZIRLIGI
FAG’ONA DAVLAT UNIVERSITETI MATEMATIKA VA INFORMATIKA FAKULTETI


Amaliy matematika va informatika yo’nlishi
18.08 guruh talabasi Maxmutaliyeva Ra’noxonning


O’yinlar nazaysi va jarayonlar tadqiqoti fanidan “Maksimal oqim masalasini chiziqli dasturlashtirish masalasiga keltirib yechish” mavzusidagi


Mustaqil ishi

Qabul qildi: Z. Mamatova
Farg’ona-2021

Reja:
1. Maksimal oqim haqidagi masala.


2. Chiziqli dasturlashtirish masalasiga keltirib yechish.

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 tarmoqga qarashli bo`lsa, (i,j) yoy ham unga qarashli. Tarmoq uchlarini (a0,a1,a2......an) deb nomerlab chiqamiz  ={a0,a1,a2......an} U vaqtda (i,j) yoy (ai,aj) kabi ham 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 oraliq uchlar deb aytiladi. Tarmoq yo`llari bo’ylab 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 qo’yilgan bo`lib, bu songa yoyning oqimni o`tkazish qobilyati deyiladi. Yoyning o’tkazish qobilyati deganda uning vaqt birligi ichida o’tkazishi mumkin bo’lgan modda miqdorini 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 miqdorini xij deb belgilaymiz va uni yoy bo`ylab oqim deb ataymiz. Agar tarmoqda (i,j) yo`l, ya’ni (ai,aj) yoy mavjud bo`lmasa, unga mos oqim xij=0.
Tarmoqdagi a0 manbadan an yiginga oqim 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 o’tkazish qobilyatlari bir-biriga teng bo`lsalar bu yoylarni almashtirish mumkin. Shunga asosan masalaning qo’yilishi aralash va orientirlanmagan graflar uchun ham o`rinlidir. Masalaning qo`yilishiga ko`ra xar bir oraliq
uchga boshqa uchlardan keladigan moddalar yig’indisi 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 muhim 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 o’tkazish qobilyati bilan xarakterlanadi. Kesimning o'tkazish qobilyati.

formula yordamida hisoblanadi. Kesimning ta’rifidan ko'rinib turibdiki, manbadan yig’inga boruvchi istalgan yo'l  kesimning hech bo'lmaganda bitta yoyini o’z ichiga oladi. Shuning uchun qandaydir kesimning barcha yoylarini olib tashlasak manbadan yig’inga boradigan birorta ham yo’l mavjud b’lmaydi. Yo’lning o’tkazish qobilyati shu yo’lga kiruvchi yoylarning o’tkazish qobilyatlarining eng kichigiga teng bo’lgani uchun oqimning v kattaligi, ya’ni a0 ni an bilan bog’lovchi barcha mumkin bo’lgan yo’llar bo’yicha olib o’tiladigan oqim miqdori istalgan kesimning o’tkazish qobilyatidan oshmaydi:  . Demak, agar shunday oqim topilsaki uning v* kattaligi biror  kesimning o’tkazish qobilyatiga teng bo’lsa, ya’ni  tenglik bajarilsa, shu oqim maksimal va  minimal o’tkazish qobilyatli bo’ladi. Maksimal oqim haqidagi masalani yechish algoritmi. Ford-Falkerson teoremasi.
Teorema (Ford-Falkerson). Xar qanday tarmoqda a0 manbadan an yig’inga maksimal oqim miqdori a0 ni an larni bir-biridan ajratuvchi kesimlarning minimal o’tkazish qobilyatiga teng. Endi Fordning maksimal oqimini topish algoritmining jadval kurinishni qaraymiz. Dastlabki qadam.
o’lchovli jadvalga yoylarning o’tkazish qobilyatlarini yozib chiqamiz, bunda n+1 -qaralayotgan G=(V,E) tarmoqdagi uchlar soni.
(ai,aj) yoyning o’tkazish qobilyati bij noldan katta bo’lsa va simmetrik yoy (aj,ai) ning o’tkazish qobilyati nolga teng bo’lsa (i,j) katakka bij ni (j,i) katakka esa nol yozamiz. Agarda bij=bji=0 bo`lsa (i,j) va (j,i) kataklarga hech narsa yozmaymiz.
Umumiy qadam:
1) a0 dan an ga o’tkazish qobilyati noldan katta bo’lgan yo’lni topamiz. Buning uchun a0 ga mos ustunga * belgisi kuyamiz. a0 qatorda b0j>0 bulgan ustunlarni topib qaralayotgan qator tepasiga 0 (nol) raqami bilan belgi qo’yamiz. Natijada musbat o’tkazish qobilyatiga ega bo’lgan barcha (a0,aj) yoylar ajratiladi. Ular a0 dan an ga boruvchi yo’lning dastlabki yoylari bo’lishadi. Keyin ustunlari belgilangan nomerli qatorlarni qaraymiz. Xar bir, masalan ai qatorda, belgilangan ustunlar uchun bij>0 bo`lgan elementlarni topamiz va ularni qaralayotgan qator nomeri bilan nomerlaymiz. Shunday qilib, a0 dan an ga boruvchi yo’lning keyingi yoylarini topgan bo’lamiz. Qatorlarni qarashni shu vaqtgacha davom ettiramizki: a) yo an ustun belgilangan holga kelamiz (bu hol a0 dan an ga boruvchi musbat o‘tkazish qobilyati yo‘l topilganligi bildiradi); b) yoki yangi ustunlarni belgilash mumkin emasligi haqida xulosa qilamiz. (qaralayotgan qatorlar uchun belgilanmagan ustunlarda musbat elementlar mavjud emas). Bu holda musbat o’tkazish qobliyatiga ega bo‘lgan a0 dan an ga boruvchi yo‘l mavjud emas.U holda ustunlar belgilaridan foydalanib izlangan a0 dan an ga μ yo’lni topamiz. Faraz qilaylik yo‘lning oxirgi uchi an k bilan bilan belgilangan bo‘lsin. Shu belgi yordamida an oldingi ak uchni topamiz (ak qatorni qaraganda an ustun bilan yo‘ldagi eng oxirgi (ak, an) yoy belgilangan edi). ak qator an ustun kesishish nuqtasidagi bkn elementni minus belgi bilan belgilaymiz. Mos simmetrik element bnk ni esa plyus belgisi bilan belgilaymiz. Natijada  va  sonlarni hosil qilamiz.
ak qator qaralgani uchun undan oldin, aytaylik r nomer bilan, ak ustun belgilangan edi. SHuning uchun  elementdan ak ustun bo‘ylab r qatorgacha harakat qilamiz va brk ni minus belgisi bilan, brk ni esa minus belgisi bilan belgilaymiz. Bu jarayonni a0 qatorga kelguncha va shu kator elementini minus ishorasi bilan va simmetrik elementni plyus ishorasi bilan belgilaguncha davom ettiramiz. Sungra 2-punktga o‘tamiz. “b” holda yig’inga mos an ustunni belgilash mumkin emas. Shu sababli noldan katta o‘tkazish qobilyatiga ega bo‘lgan a0 dan an ga boshqa yo‘l mavjud emas, demak umumiy qadam tugaydi. Jadvalning belgilangan ustunlarida joylashgan uchlar R to‘plamni tashkil etadi (a0 manbadan bu uchlarga boradigan qandaydir yo‘l mavjud). Qolgan uchlar  to‘plamga qarashli.  uchdan chiqib  uchga kiruvchi yoylar minimal o‘tkazish qobilyatiga ega bo‘lgan kesim tashkil kilishadi va  bu erda bij berilgan tarmoq (i,j)
yoyning o‘tkazish qobilyatini ifodalaydi.
2) Topilgan μ yo‘lning o‘tkazish qobilyati θ ni topamiz. Yo‘lning o‘tkazish qobiliyati deganda vaqt birligi ichida a0 dan an ga μ yo‘l bo’yicha o’tkazish mumkin bo’lgan moddaning maksimal miqdorini tushunamiz. Yo‘lning o‘tkazish qobilyati shu yo‘lga kiruvchi yoylarning o’tkazish qobilyatlarining eng kichigiga teng:

3) Topilgan yo’l yoylarining va ularga simmetrik yoylarning qolgan o‘tkazish qobilyatlarini aniqlaymiz. Buning uchun jadvalning bij- elementlaridan θ ni ayiramiz, bij+ elementlarga esa θ ni qo’shamiz. Bu amallarni bajargandan so’ng o’tkazish qobiliyatlari o’zgargan dastlabki jadvalga o’xshash yangi jadvalni hosil qilamiz. Yangi jadvalni hosil qilgandan so’ng umumiy qadamning 1-punktiga qaytamiz va uni a0 dan an ga o’tkazish qobilyati noldan katta bo’lgan yo‘l mavjud bo’lmagan jadval hosil bo’lguncha davom ettiramiz. Hal qiluvchi qadam. Dastlabki jadvalning elementlaridan oxirgi qadamda xosil bo’lgan jadvalning mos elementlarini ayiramiz. Natijada musbat elementlari (ai, aj) yoyning mos xij oqim miqdorlariga teng bo’lgan jadvalni hosil qilamiz. Tarmoqdagi 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 o'tkazish 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 hosil qilamiz.
2) topilgan yo`lning o`tkazish qobilyatini aniqlaymiz:

Topilgan yo`l yoylari o`tkazish qobilyatlarini θ 1=9 ga kamaytirib, simmetrik yoylarning o'tkazish 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 
bo’ladi.
3) Yangi 3-jadvalni hosil 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.

Download 145,04 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©www.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