Mavzu: Maksimal o

Mavzu: Maksimal oqim. Oqim tushunchasi.
Reja:

1. 
   Maksimal oqim haqidagi masala
   
2. 
   Belgi qo'yish usuli
   
3. 
   Ommaviy xizmat ko'rsatish masalalari
   
4. 
   Buyurtmalar oqimi
   

Maksimal oqim haqidagi masala
Maksimal oqim haqidagi masalani bayon qilamiz. 0 punktdan m punktga iloji boricha ko'prok miqdordagi yuklarni jo'natishdan iborat. Bunda biz 0 punktda yuklarning chegaralanmagan zaxirasi mavjud va yoylarning yuk o'tkazish qobiliyati yuqoridan chegaralangan deb faraz qilamiz. Shunday qilib, berilgan o'tkazish qobiliyatiga ega bo'lgan yoylardan foydalanib, jo'natish punktidan qabul qilish punktiga jo'natiladigan maksimal oqimni (uni v bilan belgilaymiz) aniqlashimiz kerak. Qo'yilgan masalani quyidagi to'r yordamida bayon qilamiz.

Bunga o'xshash to'r uchun matematik modelni qurish qiyin emas.
Buning uchun quyidagilardan foydalanamiz:
1) i punktdan j punktga olib boriladigan yuk miqdori o'zgaruvchidan iborat;
2) to'r orqali o'tkazilgan yuklarning umumiy miqdori v dan iborat;
3) yo'ldagi oqimning yuqori chegarasi dan iborat;
4) oqimning saqlanishi haqidagi faraz bajariladi;
5) v oqim va o'zgaruvchilar nomanfiy.
Natijada quyidagi chiziqli programmalash masalasini hosil qilamiz:

shartlardan

funkstiya maksimallashtirilsin.
Sistemadagi 1-tenglama 0 punktga tushgan v oqim 0 punktdan boshqa (1,2,3) tugun punktlarga jo'natilayotgan yig'indi oqimga teng bo'lishini bildiradi. 2-tenglama 1 punktdan 2,3,m punktlarga jo'natilayotgan yuklar miqdorlarining yig'indisi 1-punktga kelayotgan yuk miqdori ga tengligidan, ya'ni tenglamadan kelib chiqadi. Qolgan tenglamalar ham shunga o'xshash talqin qilinadi. Sistemadagi tengsizliklar yoydagi oqimning yuqori chegarasi dan iboratligidan kelib chiqadi. tengsizlik 5) jumladan kelib chiqadi.
Masala, shubhasiz,yechimga ega chunki agar va bo'lsa, barcha cheklanishlar qanoatlanadi. Garchi maksimal oqim haqidagi masalani simpleks usul bilanyechish mumkin bo'lsa ham, bunga o'xshash masalalarning matematik tuzilishi maqsadga tez va oson yetkazadigan yechish usullarini qo'llashga imkon beradi. Bunday masalalarniyechish uchun samarali usullar asoslanadigan ba'zi ma'lumotlarni keltiramiz.
Kesim tushunchasini kiritamiz. Kesim bu shunday yo'llar to'plamiki, uni to'rdan olib tashlansa, to'r birida jo'natish punkti, boshqasida qabul punkti bo'lgan ikkita o'zaro bog'lanmagan qismlarga ajralgan bo'lib qoladi. Biror kesimga tegishli bo'lgan yo'llar aniq belgilangan umumiy o'tkazish qobiliyatiga ega bo'ladi. 0 va m punktlarni ajratuvchi kesimlar orasida o'tkazish qobiliyati eng kichik bo'lgan kesim minimal kesim deb ataladi.
To'rlar nazariyasining asosiy teoremasi (Maksimal oqim va minimal kesim haqidagi Ford-Falkerson teoremasi) quyidagidan iborat. Ixtiyoriy to'r uchun 0 punktdan m punktga bo'lgan maksimal oqim kattaligi minimal kesimning o'tkazish qobiliyatiga teng. Maksimal oqim haqidagi masalani belgi qo'yish usuli bilanyechish ham mumkin. Bu usul keyingi mavzuda bayon qilinadi.