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

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 (a<sub>0</sub>,a<sub>1</sub>,a<sub>2</sub>......a<sub>n</sub>) deb nomerlab chiqamiz  ={a<sub>0</sub>,a<sub>1</sub>,a<sub>2</sub>......a<sub>n</sub>} U vaqtda (i,j) yoy (a<sub>i</sub>,a<sub>j</sub>) kabi ham yoziladi.
Xar bir  uch uning intensivligini ifodalovchi d(a<sub>i</sub>) son bilan xarakterlanadi. d(a<sub>i</sub>)>0 bo`lgan uchga manba (a_i-ishlab chiqarish punkti) deb, d(a_i) bo`lgan uchga yaqin a<sub>i</sub> - iste’mol punkti deb, d(a<sub>i</sub>)=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 (a<sub>i</sub>,a<sub>j</sub>) yoyga b<sub>ij</sub> 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 a₀ -yagona manba, a_n yagona yechim, a₁,a₂......a_n-1  oraliq uchlardir. Xar bir yoydan vaqt birligida o`tgan modda miqdorini x<sub>ij</sub> deb belgilaymiz va uni yoy bo`ylab oqim deb ataymiz. Agar tarmoqda (i,j) yo`l, ya’ni (a<sub>i</sub>,a<sub>j</sub>) yoy mavjud bo`lmasa, unga mos oqim x_ij=0.
Tarmoqdagi a₀ manbadan a_n yiginga oqim deb barcha (a_i,a_j) yoylar bo`ylab x<sub>ij</sub> 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.
a<sub>0</sub> ni a<sub>n</sub> dan ajratuvchi kesim deb barcha (a<sub>i</sub>, a<sub>j</sub>) 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 a₀ ni a_n 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 a₀ manbadan a_n yig’inga maksimal oqim miqdori a₀ ni a_n 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.
(a_i,a_j) yoyning o’tkazish qobilyati b_ij noldan katta bo’lsa va simmetrik yoy (a_j,a_i) ning o’tkazish qobilyati nolga teng bo’lsa (i,j) katakka b_ij ni (j,i) katakka esa nol yozamiz. Agarda b_ij=b_ji=0 bo`lsa (i,j) va (j,i) kataklarga hech narsa yozmaymiz.
Umumiy qadam:
1) a<sub>0</sub> dan a<sub>n</sub> ga o’tkazish qobilyati noldan katta bo’lgan yo’lni topamiz. Buning uchun a<sub>0</sub> ga mos ustunga * belgisi kuyamiz. a<sub>0</sub> qatorda b<sub>0j</sub>>0 bulgan ustunlarni topib qaralayotgan qator tepasiga 0 (nol) raqami bilan belgi qo’yamiz. Natijada musbat o’tkazish qobilyatiga ega bo’lgan barcha (a<sub>0</sub>,a<sub>j</sub>) yoylar ajratiladi. Ular a<sub>0</sub> dan a<sub>n</sub> ga boruvchi yo’lning dastlabki yoylari bo’lishadi. Keyin ustunlari belgilangan nomerli qatorlarni qaraymiz. Xar bir, masalan a<sub>i</sub> qatorda, belgilangan ustunlar uchun b<sub>ij</sub>>0 bo`lgan elementlarni topamiz va ularni qaralayotgan qator nomeri bilan nomerlaymiz. Shunday qilib, a₀ dan a_n ga boruvchi yo’lning keyingi yoylarini topgan bo’lamiz. Qatorlarni qarashni shu vaqtgacha davom ettiramizki: a) yo a_n ustun belgilangan holga kelamiz (bu hol a₀ dan a_n 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 a₀ dan a_n ga boruvchi yo‘l mavjud emas.U holda ustunlar belgilaridan foydalanib izlangan a₀ dan a_n ga μ yo’lni topamiz. Faraz qilaylik yo‘lning oxirgi uchi a_n k bilan bilan belgilangan bo‘lsin. Shu belgi yordamida a_n oldingi a_k uchni topamiz (a_k qatorni qaraganda a_n ustun bilan yo‘ldagi eng oxirgi (a_k, a_n) yoy belgilangan edi). a_k qator a_n ustun kesishish nuqtasidagi b_kn elementni minus belgi bilan belgilaymiz. Mos simmetrik element b_nk ni esa plyus belgisi bilan belgilaymiz. Natijada  va  sonlarni hosil qilamiz.
a_k qator qaralgani uchun undan oldin, aytaylik r nomer bilan, a_k ustun belgilangan edi. SHuning uchun  elementdan a_k ustun bo‘ylab r qatorgacha harakat qilamiz va b_rk ni minus belgisi bilan, b_rk ni esa minus belgisi bilan belgilaymiz. Bu jarayonni a₀ 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 a_n ustunni belgilash mumkin emas. Shu sababli noldan katta o‘tkazish qobilyatiga ega bo‘lgan a₀ dan a_n ga boshqa yo‘l mavjud emas, demak umumiy qadam tugaydi. Jadvalning belgilangan ustunlarida joylashgan uchlar R to‘plamni tashkil etadi (a₀ 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 b_ij 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 a₀ dan a_n 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 b_ij- elementlaridan θ ni ayiramiz, b_ij+ 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 a₀ dan a_n 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 (a_i, a_j) yoyning mos x_ij oqim miqdorlariga teng bo’lgan jadvalni hosil qilamiz. Tarmoqdagi maksimal oqim esa a₀ qator a_n ustunning elementlari yigindisiga teng bo`ladi, ya’ni

Misol. Quyida chizmada berilgan tarmoq uchun a₀ 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. μ ₁=(a₀-a₂-a₄)
Yo’lni hosil qilamiz.
2) topilgan yo`lning o`tkazish qobilyatini aniqlaymiz:

Topilgan yo`l yoylari o`tkazish qobilyatlarini θ ₁=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) μ₂=(a₀-a₁-a₃-a₄) yo`lni topamiz.
2) μ<sub>2</sub> 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) μ₃=(a₀-a₂-a₃-a₄) 2) 
3) Navbatdagi jadvalni tuzamiz.