Hisoblash algoritmi maksimal oqim tarmoqlarda
QADAM 1. Dastlabki topshiriqlar. Joriy qiymat Da Tarmoqdagi maksimal oqim 0 qiymati bilan belgilanadi. QADAM 2. Tarmoqda mustaqil marshrutlarni tanlash va ulardagi oqimlarni aniqlash. Tarmoqdagi barcha mumkin bo'lgan yo'nalishlar to'plamidan manbadan tortib to cho'kishgacha, biz mustaqil marshrutlarni tanlaymiz M 1 , … , M k, ega emas umumiy uchlari, dastlabkisidan tashqari (manba v va) va yakuniy (drenaj v bilan). Har bir tanlangan marshrut uchun M i(1£ i£ k) maksimal oqimni aniqlang A(M i).QADAM 3. Tarmoqdagi maksimal oqimning joriy qiymatini tuzatish. Biz topilganlarni qo'shamiz 2-QADAM mustaqil yo'nalishlarda maksimal oqimlarning qiymatlari M 1 , … , M k joriy umumiy maksimal tarmoq oqimiga: Da:= A t + A(M 1)+ A(M 2)+…+ A(M k)QADAM 4. Tarmoqni tuzatish. Topilgan 2-QADAM maksimal oqimlar A(M 1), … , A(M k) mos keladigan tarmoq yoylarining sig'imidan ayiriladi. Nol qoldiq sig'imga ega bo'lgan yoylar olib tashlanadi. QADAM 5. Algoritmning bajarilishini tekshirish. Agar tuzatishdan keyin tarmoqda manbadan marshrutlar qolmasa v va zaxiraga olish v bilan, keyin tarmoqdagi kerakli maksimal oqim topilgan oqimga teng A:= A t, algoritm tugatiladi, chunki barcha tarmoq sig'imi tugagan. Agar sozlangan tarmoqda manbadan marshrutlar mavjud bo'lsa v va zaxiraga olish v bilan, keyin o'ting 2-QADAM va algoritmni bajarishni davom ettirish . 2-misol. Ushbu algoritm yordamida 1.15-rasmda tarmoqdagi maksimal oqimni toping. Yechim.QADAM 1. Dastlabki topshiriqlar. Da: = 0.takrorlash. QADAM 2. Tarmoqda mustaqil marshrutlarni tanlash va ulardagi oqimlarni aniqlash. Sifatda M 1 ta marshrut ( v va = V 1 , V 2 , V 5 , v s = V 7), 1-misolda ko'rib chiqiladi. Uning uchun A(M 1) = 10.
Bundan tashqari, mustaqil ravishda izolyatsiya qilish oson M 1 marshrut M 2 = (v va = V 1 , V 3 , V 6 , v s = V 7). Keling, buning uchun maksimal o'tkazuvchanlikni hisoblaymiz va yoylarning o'tkazuvchanligini sozlaymiz: A(M 2)=min{d 13 ,d 36 ,d 67 } =min{45, 40, 30} = 30. d 13¢ =d 13 - 30 = 15,d 36¢ =d 36 - 30 = 10,d 67¢ =d 67 - 30 = 0.
QADAM 3. Tarmoqdagi maksimal oqimning joriy qiymatini tuzatish. Da:= A t + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.QADAM 4. Tarmoqni tuzatish. Topilgan 2-QADAM maksimal oqimlar A(M 1), A(M 2) marshrutlarda M 1 , M Ularning yoylarining sig'imidan 2 ayiriladi. Nol qoldiq sig'imga ega bo'lgan yoylar olib tashlanadi. Natija 1.16 a-rasmda keltirilgan. a) b) 1.16-rasm. Iteratsiyadan keyin tarmoqni tuzatish natijasi I Va IISTEP 5. Algoritmning bajarilishini tekshirish. Sozlangan tarmoqda (1.16-rasm a) manbadan marshrutlar mavjud v va zaxiraga olish v bilan, Masalan M 3 = (v va = V 1 , V 4 , V 2 , V 5 , v s = V 7). Algoritmni bajarishni davom ettirish .II iteratsiya. 2-QADAM. Biz yagona mustaqil yo'l sifatida M 3 = (v va = V 1 , V 4 , V 2 , V 5 , v s = V 7). Uning uchun:
A(M 3)=min{d 14 ,d 42 ,d 25 ,d 57 } =min{15, 10, 10, 15} = 10.
d 14¢ =d 14 - 10 = 5,d 42¢ =d 42 - 10 = 0,d 25¢ =d 25 - 10 = 0,d 57¢ =d 57 - 10 = 5.
3-QADAM. A t:= A t + A(M 3) = 40 + 10= 50.QADAM 4. Tarmoqni tuzatish. Maksimal oqim A(M 3) marshrut yoylaridan ayirish M 13 . Natija 1.16 b-rasmda keltirilgan.
5-QADAM. Sozlangan tarmoqda manbadan cho'kish yo'llari qolmadi. A:= A t:= 50, algoritmni bajarish. Javob: 1.15-rasmdagi tarmoqdagi maksimal oqim 50 ga teng.Agar tarmoqda bir nechta manbalar ko'rsatilgan bo'lsa, u cheksiz sig'imga ega bo'lgan yoylar orqali dastlabki manbalarga ulangan yangi umumiy manbani kiritish bilan yakunlanadi. Keyin muammo hal qilinadi odatiy algoritmga. Asl manbalar orqali kerakli oqimlar yangi umumiy manbadan ularga kiradigan yangi qo'shilgan yoylar bo'ylab oqimlar bo'ladi. Tarmoqda bir nechta drenaj mavjud bo'lsa, xuddi shunday qiling.
Tarmoqni rejalashtirish
Juda murakkab ob'ektni loyihalash yoki qurish bo'yicha har qanday vazifa ( loyiha) bir necha kichik komponent bosqichlariga bo'linishi mumkin. Kimdan to'g'ri tanlov Ushbu bosqichlarning ketma-ketligi butun loyihaning vaqtiga bog'liq.
Loyihani amalga oshirish bo'yicha barcha harakatlar to'plami sifatida taqdim etiladi voqealar Va ishlaydi. Voqealar loyihaning individual bosqichlari deb ataladi. Ish - bu uni yakunlash jarayoni. Loyihani bajarish uchun zarur bo'lgan voqealar va ishlarning butun majmuasi ikki kutupli tarmoq shaklida taqdim etilishi mumkin G =({v va, v z} , V, X), bunda:
va hammasi voqealar cho'qqilar to'plami bilan belgilanadi V, ular orasida alohida ta'kidlab o'tildi boshlang'ich hodisa v va(ishning boshlanishi) va yakuniy voqea v z(butun loyihani yakunlash), tarmoqning ichki cho'qqilarini aniqlaydi oraliq hodisalar- jarayonda bajarilishi kerak bo'lgan bosqichlar loyihani amalga oshirish,
b) hamma narsa ish hodisa juftlarini - cho'qqilarni bog'lovchi yoylar bilan ko'rsatiladi.
Ushbu tarmoqning grafik tasviri deyiladi tarmoq diagrammasi. Harakatlar ketma-ketligini ko'rsatish uchun tarmoq diagrammasiga ham kiriting xayoliy asarlar, ular hech qanday harakatni bajarish bilan bog'liq emas. Tegishli ishlar chiziqli yoylar bilan ko'rsatilgan.
Misol tariqasida, ayrim ishlab chiqarishni tashkil qilishni ko'rib chiqing. Loyiha quyidagi ishlarni talab qiladi:
I) marketing tadqiqotlari, II) asbob-uskunalarni loyihalashdan oldingi tadqiqotlar, III) savdo tarmog'ini tashkil etish, IV) o'tkazish reklama kampaniyasi, V) ishlab chiqarish uskunalari uchun texnik shartlarni ishlab chiqish, VI) ishlab chiqish texnik hujjatlar ishlab chiqarish binolari va kommunikatsiyalari uchun, VII) standart uskunalarni sotib olish, VIII) nostandart uskunalarni loyihalash va ishlab chiqarish, IX) ishlab chiqarish ob'ektlarini qurish va kommunikatsiyalarni o'rnatish, X) standart uskunalarni o'rnatish, XI) nostandart uskunalarni o'rnatish , XII) ishga tushirish.
Ushbu ishlarni tarmoq diagrammasida mos keladigan raqamlar bilan yoylar bilan belgilaymiz.
Ushbu loyihadagi voqealar quyidagilar bo'ladi:
1) ishning boshlanishi (dastlabki voqea), 2) tugallanishi marketing tadqiqotlari, 3) loyihadan oldingi tadqiqotlarni yakunlash, 4) savdo tarmog'ini tashkil etish, 5) reklama kampaniyasini tashkil etish, 6) ishlab chiqarish uskunalari uchun texnik shartlarni tayyorlash, 7) ishlab chiqarish binolari va kommunikatsiyalari uchun texnik hujjatlarni ishlab chiqishni yakunlash. , 8) standart uskunalarni sotib olishni yakunlash, 9) nostandart uskunalarni loyihalash va ishlab chiqarishni yakunlash, 10) ishlab chiqarish ob'ektlarini qurish va kommunikatsiyalarni o'rnatishni yakunlash, 11) uskunalarni o'rnatish va ishga tushirish ishlarini yakunlash,
12) loyihani yakunlash (yakuniy tadbir).
Biz cho'qqilarni voqealarga mos keladigan raqamlar bilan bog'laymiz. Tarmoq diagrammasi Loyihaning amalga oshirilishi rasmda ko'rsatilgan. 1.17:
1.17-rasm. Loyiha tarmog'i jadvali
Gamilton sikllari
Grafik matritsa shaklida berilgan, bu erda hujayralar nuqtalar orasidagi harakat narxini belgilaydi. O'ziga ma'nosiz yo'lni yo'q qilish uchun asosiy diagonalga ∞ belgisi qo'yilgan.
Chunki Agar olingan matritsada nol elementsiz ustun bo'lsa, unda biz undagi minimal elementni topamiz va uni ushbu ustunning barcha elementlaridan ayiramiz.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Keling, barcha olib tashlangan elementlarni jamlaymiz va tsiklning pastki chegarasini olamiz in= 2+2+3+2+1=10
1.2. Matritsaning barcha nol elementlarini baholaymiz.
Jadvalda nollarning bahosini taqdim etish qulay.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
th=max g=g A C =2
1.3. Keling, yo'llar to'plamini ikkita kichik to'plamga ajratamiz: Q A.C.– yoy (AC) va Q bo‘lgan yo‘llar A.C.– yoyni (AC) o'z ichiga olmaydigan yo'llar. Ikkinchi kichik to'plam uchun pastki chegara quyidagicha bo'ladi: in / = in + th =10+2=12.
Birinchi kichik to'plamning chegarasini hisoblash uchun biz A qatorini va C ustunini kesib o'tib, bir daraja pastroq matritsaga o'tamiz. Teskari yo'lni (CA) yo'q qilish uchun yangi matritsada biz mos keladigan katakchaga ∞ belgisini qo'yamiz.
Olingan 2+0=2 matritsaning chegarasini hisoblaymiz
va pastadirning pastki chegarasiga qo'shing. Bu miqdor ichida // =10+2=12 va birinchi kichik to'plam uchun chegara bo'ladi.
1.4. Keling, barcha osilgan cho'qqilarning chegaralarini solishtiramiz va eng kichik chegaraga ega cho'qqini tanlaymiz. Agar ushbu uchlardan ikkitasi bo'lsa, ulardan birini tanlang. Bu Q ning tepasi A.C., uning pastki chegarasi =12.
Keling, taxminlarning maksimalini tanlaylik th=max g=g BD =3
ichida / =12+3=15.
1.6. Biz barcha keyingi fikrlarni avvalgilariga o'xshash tarzda bajaramiz.
Keling, taxminlarning maksimalini tanlaylik th=max g=g C B =∞
ichida / =in+ th=∞
| A | |
| D |
Ushbu matritsaning barcha satrlari va ustunlari nollarni o'z ichiga oladi. Shuning uchun chegara 12 ga teng bo'lib qoladi.
VAZIFA. Transport tarmog'idagi maksimal oqim qiymatini toping.
MUAMMONI TOPLANTIRISH.
Tarmoqdagi transport muammosini ko'rib chiqing ( I, D, G) berilgan yoy sig'imlari bilan c(i,j).
Keling, ikkita sobit cho'qqini tanlaymiz: s- manba va t- drenajlash. Tarmoqdagi oqim s→t sonli funksiyani chaqiramiz f, yoylar to'plamida aniqlangan va quyidagilarni qanoatlantiradi chiziqli tenglamalar va tengsizliklar:
0≤ f(i,j) ≤c(i,j) har qanday uchun (i, j)
O'zgaruvchini maksimallashtirish uchun talab qilinadi x
Kesish L cho'qqilarni ajratuvchi tarmoqda s t
yoylar to'plami deb ataladi 
Nima bo'lganda ham s→t kamida bitta kesilgan yoyni o'z ichiga oladi.
OPTIMALLIK MEZONLARI: haqiqiy tarmoqda ixtiyoriy oqimning qiymati kesmaning o'tkazuvchanligidan oshmaydi va maksimal oqimning qiymati kesishning minimal o'tkazuvchanligiga teng.
MISOL 3.12.
M 9 K
M 8 K
MISOL 3.13.
M 2 K
YECHIMA :
Chiqib ketuvchi yoyning sig'imi (T,B) mos keladigan cho'qqiga kiradigan yoylarning umumiy sig'imidan oshadi. Tarmoq real bo'lishi uchun c(T,B)=5 ni almashtiramiz.
Keling, barcha kesmalarning o'tkazish qobiliyatining qiymatini topamiz va hisoblaymiz. (K,V) - (T,V) minimal o'tkazuvchanlik =6 bilan kesish. Shunday qilib, maksimal oqim =6.
Bir nechta manbalar va cho'kmalarga ega bo'lgan tarmoqni bitta manba va lavabo bilan tarmoqqa qisqartirish mumkin.
MISOL. Bir nechta manbalar S va cho'kma T bo'lsin ( transport muammosi). Tarmoqni ikkita tugun s*, t* va barcha yoylarni (s*, S) , (T,t*) qoʻshish orqali kengaytiramiz. Imkoniyat funksiyasini sozlash orqali aniqlaymiz
MARKALARNI JOYLASH USULI.
1. Dastlabki oqim f(i,j) = 0.
Keling, ushbu tarmoqning shaklga ega bo'lgan uchlariga teglar tayinlaymiz (i+, e) yoki
(i - , e). Keling, manbani belgilaymiz (-, ∞),
bular . e(lar)= ∞.
2. Belgilangan har qanday cho'qqi uchun i
barcha etiketlanmagan uchlarini tanlang j
buning uchun f(i,j)
Drenaj belgilanmaguncha ushbu operatsiyani takrorlaymiz. Agar oqim yorliqsiz qolsa, u holda topilgan oqim maksimal bo'ladi va belgilangan cho'qqilarni belgilanmaganlar bilan bog'laydigan yoylar to'plami minimal kesimni hosil qiladi.
3. Qimmatli qog'ozlar yorliqli bo'lsin (j+, e(t)), Keyin f(j,t) bilan almashtiring f(j,t)+e(t). Agar aktsiya belgilangan bo'lsa (j-, e(t)), Bu f(j,t) bilan almashtiring f(j,t)-e(t). Keling, tepaga chiqaylik j. Agar j belgisi bor (i+, e(j)), keyin almashtiramiz f(i,j) yoqilgan f(i,j)+e(t), va agar (i-, e(j)), f(j,i) bilan almashtiring f(j,i)-e(t). Keling, tepaga chiqaylik i. Manbaga yetguncha bu amalni takrorlaymiz s. Oqim o'zgarishi to'xtaydi, barcha belgilar o'chiriladi va 2-bosqichga o'ting
3.14. MISUL.
M 4 K
| 1 qadam | A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( K,B)=0 |
| 2-qadam | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| 3-qadam | A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| 4-qadam | A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| 5-qadam | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( M,T)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| 6-qadam | A → (-, ∞) M → (A+,1) | Oqim optimal f=10 Minimal kesish: M→T-M→R-M→TO |
VAZIFA. Tarmoqdagi eng yuqori oqimni toping
ALGORITM
Tepani belgilaylik s= x 0. Qolganlarning hammasi x i.
1-bosqich.
1. Yoylari to'yinmagan har qanday yo'lni tanlang.
2. Biz bu yo'l bo'ylab oqim miqdorini unda to'yingan yoy bo'lmaguncha bir marta oshiramiz.
To'liq oqim qurilgunga qadar oqimni oshirish jarayonini davom ettiramiz, ya'ni. har qanday yo'lda kamida bitta to'yingan yoy bo'ladi.
2-bosqich.
2. Agar x i allaqachon belgilangan cho'qqi bo'lsa, u holda (+i) to'yinmagan yoylar x i dan chiqadigan barcha belgilanmagan cho'qqilarni va (–i) indeks bilan nolga teng bo'lmagan oqimli yoylar chiqadigan barcha belgilanmagan cho'qqilarni belgilaymiz. x i ga.
3. Agar bu jarayon natijasida cho`qqi belgilansa t, keyin orasida s Va t barcha uchlari oldingi cho'qqilarning raqamlari bilan belgilangan yo'l bor. Biz bu yo'lning barcha yoylaridagi oqimni bittaga ko'paytiramiz, agar dan harakatlanayotganda s Kimga t yoyning yo'nalishi harakat yo'nalishiga to'g'ri keladi va agar yoy qarama-qarshi yo'nalishga ega bo'lsa, bittaga kamayadi. Keling, 1-bosqichga o'tamiz.
4. Qachon yuqori t jarayon tugatilganligini belgilash mumkin emas va natijada paydo bo'lgan oqim tarmoqning eng katta oqimidir.
ESLATMA. Birinchi bosqichni tugatmasdan 2-bosqichga o'tishingiz mumkin (3.16-misolga qarang).
3.15-MISA.
9
YECHIM:
Berilgan transport tarmog'ida to'liq oqim topildi. To'yingan yoylar ta'kidlangan
Ushbu tarmoqda siz oxirgi cho'qqini ham belgilashingiz mumkin va markalash natijasi bir xil bo'ladi. Oqimni o'zgartirib, biz tarmoqni olamiz, unda oxirgi cho'qqini belgilash mumkin emas, shuning uchun undagi oqim eng katta va 10 ga teng.
3.16-MISA.
8 2 1
Berilgan transport tarmog'ida to'liq bo'lmagan oqim aniqlandi
Keling, tarmoqni belgilaymiz va algoritmga muvofiq undagi oqimni oshiramiz. olamiz
Ushbu tarmoqda siz oxirgi cho'qqini ham belgilashingiz mumkin va markalash natijasi bir xil bo'ladi. Oqimni o'zgartirib, biz oxirgi tepalikni belgilash mumkin bo'lmagan tarmoqni olamiz, shuning uchun undagi oqim eng katta va 6 ga teng.
IV bo'lim. DINAMIK DASTURLASH.
Optimal ko'p bosqichli echimlarni topish uchun dinamik dasturlash qo'llaniladi. Masalan, uskunani almashtirishni uzoq muddatli rejalashtirish; sanoatning bir necha yillardagi faoliyati. U optimallik printsipidan foydalanadi, unga ko'ra har qanday yangi qisman yechim erishilgan holatga nisbatan optimal bo'lishi kerak.
Bir necha marta hal qilish yaxshiroqdir oddiy vazifa bir necha marta murakkab.
MUAMMO 1. Ikki nuqta orasidagi eng foydali marshrut haqida.
Ikki A va B nuqtalarini bog'laydigan yo'lni qurish kerak, ulardan ikkinchisi birinchisining shimoli-sharqida joylashgan. Oddiylik uchun aytaylik, yo'lni yotqizish bir qator qadamlardan iborat va har bir qadamda biz shimolga yoki sharqqa qarab harakat qilishimiz mumkin. Keyin har qanday yo'l bosqichli siniq chiziq bo'lib, uning segmentlari koordinata o'qlaridan biriga parallel bo'ladi. Ushbu bo'limlarning har birini qurish xarajatlari ma'lum.
4.1-MISA. A dan B gacha bo'lgan minimal yo'lni toping.
Oxirgi qadam - T.V.ga erishish. Oxirgi bosqichdan oldin biz televizorga bir qadamda etib boradigan nuqtalarda bo'lishimiz mumkin edi. Bunday ikkita nuqta mavjud (tizim ikkita holatdan birida bo'lishi mumkin). Ularning har biri uchun t.V ga erishishning bitta varianti mavjud: bittasi uchun - sharqqa harakat qiling; ikkinchisi uchun - shimolga. Keling, har bir holatda 4 va 3 xarajatlarni yozamiz.
4
Endi oxirgi qadamni optimallashtiramiz. Oldingi bosqichdan so'ng, biz uchta nuqtadan biriga tushishimiz mumkin: C 1, C 2, C 3.
C 1 nuqtasi uchun faqat bitta boshqaruv mavjud (uni o'q bilan belgilaymiz) - sharqqa harakatlaning va xarajatlar 2 (bu bosqichda) + 4 (keyingi bosqichda) = 6 bo'ladi. Xuddi shunday, C 3-band uchun xarajatlar 2+3=5 bo'ladi. t.C 2 uchun ikkita boshqaruv mavjud: sharqqa yoki shimolga boring. Birinchi holda, xarajatlar 3+3=6, ikkinchi holatda esa 1+4=5 bo'ladi. Bu shuni anglatadiki, shartli optimal nazorat shimolga borishdir. Keling, uni o'q bilan belgilaymiz va tegishli xarajatlarni kiritamiz.
| |
| |
| |
| 2-VAZIFA. Avtomobilni yuklash haqida (ryukzak haqida). N ta element mavjud. Ma'lum vazn a i va qiymat phi har bir element. ≤ og'irlikni ushlab turishga qodir ryukzakni to'ldirish uchun talab qilinadi R , eng katta qiymatga ega bo'lgan bunday elementlar to'plami.
Ryukzakni yuklash jarayonini N bosqichga bo'lish mumkin. Har bir qadamda biz savolni hal qilamiz: bu narsani olish yoki olmaslik? Har bir qadamda faqat 2 ta boshqaruv mavjud: nazorat =1, agar biz ushbu elementni olsak; va 0 - agar biz uni qabul qilmasak. Keyingi bosqich oldidan tizimning holati S vazni bilan tavsiflanadi, u avvalgi bosqichlar bajarilgandan so'ng (ba'zi elementlar allaqachon yuklangan) to'liq yuklash tugagunga qadar bizning ixtiyorimizda qoladi, ya'ni. xaltadagi bo'sh joy miqdori. ALGORITM. 1. Keling, oxirgi bosqichdan boshlaylik. Keling, ryukzakdagi bo'sh joy haqida turli xil taxminlarni keltiramiz: S=0,1,…R. Eng oxirgi narsani ryukzakka joylashtiramiz, agar unda yetarli joy bo'lsa. 2. Har bir oldingi bosqichda barcha mumkin bo'lgan S holatlar uchun biz 2 variantni ko'rib chiqamiz: ob'ektni olish yoki olmaslik. Keling, har bir holatda daromadni joriy bosqichdagi va keyingi optimallashtirilgan bosqichdagi yutuqlar yig'indisi sifatida topamiz. Natijalarni yordamchi jadvalga kiritamiz. 3. Birinchi bosqichda faqat S=R mumkin bo'lgan holatni ko'rib chiqamiz. 4. Keling, "orqaga harakat qilish" orqali yechim topamiz, ya'ni. Birinchi bosqichda optimal boshqaruvni olib, ikkinchi bosqichda tizim holatini o'zgartiramiz: S=R– x 1 a 1 va bu holat uchun optimal boshqaruv x 2 ni tanlang. Va hokazo. O'RNAK 4.2. Dastlabki ma'lumotlar
Asosiy jadval
Yordamchi stol.
Javob: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15 3-VAZIFA. Resurslarni taqsimlash bo'yicha. P 1, P 2,… P N N ta korxona mavjud bo'lib, ularning har biri x miqdorida resurs ajratilsa, ph k (x) daromad keltiradi. Jami daromad maksimal bo'lishi uchun A miqdorida mavjud bo'lgan resursni ob'ektlar o'rtasida taqsimlash talab qilinadi. X k - korxonaga ajratilgan resurs miqdori bo'lsin. Keyin ko'rib chiqilayotgan muammo odatdagi muammoga tushiriladi chiziqli dasturlash.
Keling, muammoni dinamik dasturlash muammosi sifatida shakllantiramiz. Birinchi qadam uchun biz mablag'larni P 1 korxonasiga, ikkinchisi - P 2 ga va boshqalarga investitsiya qilamiz. Boshqariladigan tizim ichida Ushbu holatda- taqsimlangan mablag'lar. Har bir qadam oldidan tizimning holati bitta parametr bilan tavsiflanadi - hali investitsiya qilinmagan mablag'larning mavjud zaxirasi. Bu muammoda bosqichli boshqaruvlar korxonalarga ajratilgan mablag'lardir. Umumiy daromad maksimal bo'lgan optimal nazoratni (x 1, x 2,...x N) topish talab qilinadi: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| S=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| i=1 S=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
Javob: x 1 =1; x 3 =0; x 3 =4; W=3,5
UMUMIY ALGORITM
1. Tizimni tavsiflab bering. Ya'ni, har bir qadamdan oldin boshqariladigan tizimning holatini qanday parametrlar tavsiflashini bilib oling. Vazifani keraksiz tafsilotlar bilan ortiqcha yuklamasdan, boshqariladigan tizimning tavsifini iloji boricha soddalashtirib, to'g'ri va "kamtarona" qo'yish imkoniyatiga ega bo'lish muhimdir.
2. Operatsiyani bosqichlarga (bosqichlarga) ajrating. Bu erda boshqaruvga qo'yilgan barcha oqilona cheklovlar hisobga olinishi kerak. Bosqich etarlicha kichik bo'lishi kerak, shuning uchun qadamni boshqarishni optimallashtirish jarayoni juda oddiy; va qadam, shu bilan birga, optimal echimni topish tartibini murakkablashtiradigan keraksiz hisob-kitoblarni amalga oshirmaslik uchun juda kichik bo'lmasligi kerak, lekin optimal echimning sezilarli o'zgarishiga olib kelmaydi. maqsad funktsiyasi.
3. Har bir qadam uchun x i qadam boshqaruvlari to'plamini va ularga qo'yilgan cheklovlarni aniqlang.
4. Boshqarish x i i-bosqichda qanday daromad keltirishini aniqlang, agar bundan oldin tizim S holatda bo'lsa, ya'ni. to'lov funktsiyalarini yozing:
w i =f i (S, x i)
5. Boshqarish x i ta'sirida tizim holati qanday o'zgarishini aniqlang 1-qadam, ya'ni. holatni o'zgartirish funksiyalarini yozing.
S / =ph i (S, x i)
6. Ma’lum funksiya orqali shartli optimal daromadni ifodalovchi asosiy takrorlanuvchi dinamik dasturlash tenglamasini yozing.
W i (S)= max(f i (S, x i)+W i+1 (ph i (S, x i)))
7. Ishlab chiqarish shartli optimallashtirish oxirgi qadam, oxirgidan oldingi bosqich qanday tugaganligi haqida turli xil taxminlarni amalga oshiring va bu taxminlarning har biri uchun oxirgi bosqichda shartli (qadam biror narsa bilan tugashi sharti asosida tanlangan) optimal boshqaruvni toping.
W m (S)= maks (f m (S, x m))
8. Shartli optimallashtirishni oxirgidan oldingi bosqichdan boshlab va birinchi qadam (orqaga qaytish) bilan yakunlang.
9. Ishlab chiqarish shartsiz optimallashtirish nazorat qilish, har bir bosqichda tegishli tavsiyalarni "o'qish": birinchi bosqichda topilgan optimal boshqaruvni oling va tizim holatini o'zgartiring, topilgan holat uchun ikkinchi bosqichda optimal boshqaruvni toping va hokazo. oxirgi qadamgacha.
OPTIMALLIK PRINSIBI. Keyingi bosqichdan oldin tizimning holati qanday bo'lishidan qat'iy nazar, ushbu bosqichda nazoratni tanlash kerak, shunda bu bosqichdagi daromad va barcha keyingi bosqichlarda optimal daromad maksimal bo'ladi.
Dinamik dasturlash printsipi har bir qadam boshqalardan mustaqil ravishda alohida optimallashtirilganligini anglatmaydi. Agar bu qadam bizni keyingi bosqichlarda yaxshi g'alaba qozonish imkoniyatidan mahrum qilsa, aniq bir bosqichda samaradorligi maksimal bo'lgan boshqaruvni tanlashning nima keragi bor?
Amalda, operatsiyani cheksiz uzoq muddatga rejalashtirish kerak bo'lgan holatlar mavjud. Bunday holat uchun model cheksiz bosqichli boshqariladigan jarayon bo'lib, unda barcha bosqichlar tengdir. Bu erda g'olib funktsiya va holatni o'zgartirish funktsiyasi qadam raqamiga bog'liq emas.
V bo'lim. SIMULYASYONI MODELLASH
Ushbu algoritmning g'oyasi manbadan cho'kishgacha bo'lgan ijobiy oqimlarga ega bo'lgan oxirigacha yo'llarni topishdir.
(Boshlang'ich) sig'imga ega bo'lgan chekka (i, j) ni ko'rib chiqing. Algoritmni bajarish jarayonida ushbu sig'imning qismlari ma'lum bir chekkadan o'tadigan oqimlar bilan "olib tashlanadi", buning natijasida har bir chekka qoldiq sig'imga ega bo'ladi. Yozish - Qolgan tarmoqli kengligi. Barcha qirralari qoldiq sig'imga ega bo'lgan tarmoq qoldiq deb ataladi.
i tugundan oqim qabul qiluvchi ixtiyoriy j tugun uchun biz yorliqni aniqlaymiz, bu erda j tugundan i tugungacha oqayotgan oqimning qiymati. Maksimal oqimni topish uchun biz quyidagi amallarni bajaramiz.
Barcha qirralar uchun biz qoldiq quvvatni dastlabki quvvatga tenglashtiramiz, ya'ni. tenglashtiramiz =. 1-tugunni belgilab belgilaymiz va belgilaymiz. i=1 deb faraz qilamiz.
I tugundan barcha j uchun musbat qoldiq sig'imi >0 bo'lgan chekka bo'ylab borish mumkin bo'lgan j tugunlar to'plami. Agar biz 3-bosqichni bajarsak, aks holda biz 4-ga o'tamiz.
Biz k tugunida shunday topamiz. Keling, k tugunini yorliq bilan joylashtiramiz va belgilaymiz. Agar k=n boʻlsa, uchdan uchiga yoʻl topiladi va biz 5-bosqichga oʻtamiz, aks holda i=k ni oʻrnatamiz va 2-bosqichga qaytamiz.
Orqaga qaytarish. Agar i=1 bo'lsa, hech qanday uchdan uchgacha yo'l mumkin emas va 6 ga o'ting. Agar i tugunidan darhol oldingi r tugunini topamiz va uni r tuguniga qo'shni tugunlar to'plamidan olib tashlaymiz. Biz i=r ni o'rnatamiz va 2-bosqichga qaytamiz.
Qoldiq tarmog'ining ta'rifi. Biz tugunlar to'plamini belgilaymiz, ular orqali p_-chi manba tugunidan (tugun 1) cho'zilgan tugunga (tugun n) o'tadi, keyin bu yo'l bo'ylab o'tadigan maksimal oqim
Oxir-oqibat yo'lni tashkil etuvchi qirralarning qoldiq sig'imi oqim yo'nalishi bo'yicha bir miqdorga kamayadi va teskari yo'nalishda bir xil miqdorda ortadi.
Bu. uchigacha yo'lga kiritilgan chekka (i, j) uchun joriy qoldiq quvvatlar o'zgaradi:
1) agar oqim i tugundan j ga o'tsa,
2) agar oqim j tugunidan i ga ketsa.
a) topilgan m uchigacha yo'llar bilan maksimal oqim bilan ifodalanadi
b) Chetning boshlang'ich va yakuniy sig'imlari (i, j) qiymatlariga ega bo'lgan holda, biz ushbu chekka orqali optimal oqimni quyidagicha hisoblashimiz mumkin. Keling, qo'yaylik. Agar >0 bo'lsa, chetidan (i, j) o'tadigan oqim teng bo'ladi. Agar > 0 bo'lsa, oqim teng bo'ladi. (har ikkala >0 va >0 imkonsiz bo'lgan holat).
Misol 1. Tarmoqdagi maksimal oqimni toping. 1
Takrorlash 1. =
3) k=3, chunki. Biz 3-tugunni belgi bilan belgilaymiz va belgilaymiz. i=3 va 2 ga qayting)
5) k=5 va. Biz 5-tugunni yorliq bilan belgilaymiz. Biz o'tish yo'lini olamiz.
6) biz 5-tugundan boshlab va 1-tugun bilan tugaydigan teglar bo'yicha uchdan-uchgacha yo'lni aniqlaymiz: . Va. Biz yo'l bo'ylab qoldiq quvvatlarni hisoblaymiz:
Takrorlash 2.
1) va 1-tugunni yorliq bilan belgilang. i=1
2") (shuning uchun 5-tugun kiritilmagan
3") k=4 va 4-tugunni belgi bilan belgilang. i=4 va 2 ga qayting)
2""") (1 va 3 tugunlar belgilanganligi sababli ular kiritilmagan)
3""") k=5 va. 5-tugunni yorliq bilan belgilaymiz.Uchdan oxirigacha yo'l olinadi.5 ga o'ting)
Takrorlash 3.
1) va 1-tugunni yorliq bilan belgilang. i=1
3) k=2 va 2-tugunni belgi bilan belgilang. i=2 va 2 ga qayting)
3") k=3 va. 3-tugunni belgi bilan belgilang. i=3 va 2 ga qayting)
2") (bundan buyon) 4 ga o'ting)
4) 3-tugun yorlig'i oldingi tugunning raqamini ko'rsatadi. Ushbu iteratsiyada 3-tugun kelajakda hisobga olinmaydi; va 2 ga qayting)
2""") (chunki 3-tugun mumkin bo'lgan uchdan oxirigacha yo'ldan olib tashlangan)
3""") va. 5-tugunni yorliq bilan belgilaymiz. Oxir-oqibat yo'l olinadi. 5-ga o'ting)
5) i. Biz yo'l bo'ylab qoldiq quvvatlarni hisoblaymiz:
Takrorlash 4. Bu iteratsiyada yo'l bilan
Takrorlash 5. Bu iteratsiyada yo'l bilan
6-Iteratsiya: Yangi uchdan-uchgacha yo'llar mumkin emas, chunki 1-tugundan kelib chiqqan barcha qirralarning nol qoldiq sig'imi bor. Yechimni aniqlash uchun 6) ga o'ting
6) tarmoqdagi maksimal oqim hajmi birliklarga teng.
Turli qirralar bo'ylab oqim qiymatlari boshlang'ich quvvat qiymatlaridan oxirgi qoldiq sig'im qiymatlarini ayirish yo'li bilan hisoblanadi.
Hisoblash natijalari: jadval. 1
|
Oqim miqdori |
yo'nalishi |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
Maksimal oqimni topish algoritmining grafik ketma-ket bajarilishi (1-misol)
e) f) O'tish yo'llari yo'q
Guruch.
Transport tizimi bo'yicha dastlabki ma'lumotlar, masalan, zavod ichidagi, rasmda ko'rsatilgan. 2, jadval bilan ham ko'rsatilishi mumkin (2-jadval).
2-jadval. Maksimal oqim muammosi uchun dastlabki ma'lumotlar
Shubhasiz, transport tizimining maksimal sig'imi 6 dan oshmaydi, chunki 0 boshlang'ich nuqtasidan 6 birlikdan ko'p bo'lmagan yuk, ya'ni 1-bandga 2 birlik, 2-bandga 3 birlik va 3-bandga 1 birlik yuborilishi mumkin emas. Keyinchalik, barcha 6 birlik yuk 0 punktiga yakuniy nuqtaga etib borishini ta'minlash kerak. Shubhasiz, 1-bandga kelgan 2 birlik yuk to'g'ridan-to'g'ri 4-bandga yuborilishi mumkin. 2-bandga kelgan yuk. bo'linishi kerak: 2 birlik darhol 4-bandga va 1 birlik - oraliq 3-bandga yuboriladi (2 va 4-bandlar orasidagi uchastkaning cheklangan sig'imi tufayli). 3-bandga quyidagi yuk yetkazildi: 0-banddan 1 birlik va 3-banddan 1 birlik. Biz ularni 4-bandga jo'natamiz. Shunday qilib, ko'rib chiqilayotgan transport tizimining maksimal o'tkazish qobiliyati 6 birlik yukni tashkil qiladi. Bunday holda, 1 va 2-bandlar orasidagi, shuningdek, 1 va 3-bandlar orasidagi ichki qismlar (filiallar) ishlatilmaydi, 1 va 4-bandlar orasidagi filial to'liq yuklanmagan - u bilan birga 2 birlik yuk jo'natiladi. o'tkazish qobiliyati 3 birlik. Yechim jadval shaklida taqdim etilishi mumkin (3-jadval)
3-jadval. Maksimal oqim muammosini hal qilish
|
Chiqish nuqtasi |
Manzil |
Transport rejasi |
Tarmoqli kengligi |
Oqimni maksimallashtirish uchun chiziqli dasturlash muammosi. Maksimal oqim masalasini chiziqli dasturlash nuqtai nazaridan tuzamiz. X KM - K nuqtadan M nuqtagacha bo'lgan tashish hajmi bo'lsin. 2 K = 0,1,2,3, M = 1,2,3,4 va tashish faqat yuqori raqamga ega bo'lgan nuqtaga mumkin. Bu shuni anglatadiki, X KM jami 9 ta o'zgaruvchi mavjud, ya'ni X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Chiziqli dasturlash muammosi maksimal darajaga erishishga qaratilgan. oqim quyidagi shaklga ega:
X 01 + X 02 + X 03 = F (0)
X 01 + X 12 + X 13 + X 14 = 0 (1)
X 02 - X 12 + X 23 + X 24 = 0 (2)
X 03 - X 13 - X 23 + X 34 = 0 (3)
X 14 - X 24 - X 34 = - F (4)
X KM? 0, K, M = 0, 1, 2, 3, 4
Bu yerda F maqsad funksiyasi, (0) sharti tovarning transport tizimiga kirishini tavsiflaydi. Shartlar (1) - (3) tizimning 1-3 tugunlari uchun muvozanat munosabatlarini o'rnatadi. Boshqacha qilib aytadigan bo'lsak, ichki tugunlarning har biri uchun kiruvchi tovarlar oqimi tizim ichida to'planmaydi va unda "tug'ilmaydi". Shart (4) - tizimdan yuklarning "chiqish" sharti. Shart (0) bilan birgalikda u butun tizim uchun muvozanat munosabatlarini tashkil qiladi ("kirish" "chiqish" ga teng). Quyidagi to'qqizta tengsizlik transport tizimining alohida "tarmoqlari" imkoniyatlariga cheklovlar qo'yadi. Keyin transport hajmlarining manfiy emasligi va maqsad funktsiyasi ko'rsatiladi. Ko'rinib turibdiki, oxirgi tengsizlik maqsad funktsiyasi (0) yoki (4) munosabatlari) va transport hajmlarining manfiy emasligi shaklidan kelib chiqadi. Biroq, oxirgi tengsizlik ba'zi narsalarni olib keladi Umumiy ma'lumot- yukning ijobiy hajmi tizim orqali o'tishi mumkin yoki nolga teng (masalan, tizim ichida aylana bo'ylab harakat bo'lsa), lekin salbiy emas (bu iqtisodiy ma'noga ega emas, lekin rasmiy. matematik model bu haqda "bilmaydi").
Tarqatish tarmog'ida mahsulotlarni oqilona taqsimlashni rejalashtirayotganda, kanal quvvatini mijozlar ehtiyojlari va ishlab chiqarish zavodining quvvati bilan muvofiqlashtirish kerak. Ushbu toifadagi masalalar maksimal oqimni topish orqali hal qilinadi.
Keling, tarqatish tarmog'ini ko'rib chiqaylik (4.21-rasm), unda 0 nuqta (kirish, masalan, tayyor mahsulotlar ishlab chiqaruvchisi ombori) va P (chiqish, tarqatish markazlari, ulgurji va chakana tashkilotlarning omborlari, iste'molchi) va har bir yoy (segment) ulanish nuqtalari i Va j, dij > 0 soni bog'langan, deyiladi o'tkazish qobiliyati yoylar. O'tkazish qiymati maksimalni tavsiflaydi ruxsat etilgan miqdor vaqt birligida mos keladigan yoy bo'ylab o'tishi mumkin bo'lgan material oqimi.
Guruch. 4.21.
dan yoy bo'ylab o'tadigan mahsulotlar miqdori i oldin j , biz uni yoy bo'ylab oqim deb ataymiz ( i ,j ) va bilan belgilanadi. Bu aniq
Agar tarmoqning oraliq nuqtasiga kiradigan butun material oqimi undan butunlay chiqib ketishi kerakligini hisobga olsak, biz
Bizda mavjud bo'lgan kirish va chiqishdagi oqimlarning tengligi tabiiy talabidan
Z ning qiymatini tarmoqdagi oqim qiymati deb ataymiz va yuqoridagi shartlarga rioya qilgan holda Z ni maksimallashtirish masalasini qo‘yamiz.
Maksimal oqimni topish minimal kesishning o'tkazuvchanligini topishga to'g'ri keladi.
Matritsa ko'rinishida universal qidiruv algoritmini ko'rib chiqamiz.
Algoritmning dastlabki bosqichi matritsani qurishdan iborat D 0, o'tkazuvchanlik qiymatlari kiritilgan (yo'naltirilmagan yoy uchun biz matritsa elementlarining nosimmetrik qiymatlarini olamiz).
Algoritmning asosiy bosqichlari ma'lum bir yo'lni topish va bu yo'l bo'ylab oqimni tuzatishdir.
Yo'lni topishda biz belgilash jarayonidan foydalanamiz. Biz * belgisi bilan matritsaning nol qatori va ustunini belgilaymiz (tarmoq kiritish). 0-chi qatorda biz qidiramiz , tegishli ustunlarni indekslar bilan belgilang
va ustun yorliqlarini satrlarga o'tkazing. Keyin biz i-belgilangan qatorni olamiz, undagi belgilanmagan ustunni qidiramiz, biz indeks belgilariga mos kelamiz.
Ustun belgilarini satrlarga o'tkazamiz va bu jarayonni n-ustun belgilanmaguncha davom ettiramiz.
Keyin " teskari"indekslardan foydalanib, biz ē-chi cho'qqiga olib boradigan yo'lni aniqlaymiz, yo'l yoylarining sig'imini (matritsa elementlari) kamaytiramiz. V n va simmetrik elementlarni bir xil miqdorda oshiring.
Ushbu protsedura belgilanishgacha davom etadi n - tepaliklar imkonsiz bo'lib qolmaydi.
Maksimal oqimni dastlabki matritsadan ayirish yo'li bilan topish mumkin D 0, Imkoniyatlar matritsasi yuqoridagi tuzatishdan so'ng olingan:
4.4-misol
Ishlab chiqarish Moskvada joylashgan. Mahsulotlarni tarqatish uchun kompaniya turli darajadagi tarqatish markazlari orqali kompaniya bilan ishlaydigan vositachilarni jalb qiladi. Rossiyaning Yevropa qismida markaziy tarqatish markazi tomonidan xizmat ko'rsatadigan 1-ulgurji korxona mavjud. Ulgurji korxona 2 yaqin xorijda (Ukraina, Belarusiya) faoliyat yuritadi va mintaqaviy distribyutorlik markazi tomonidan xizmat ko'rsatadi. Kompaniyaning mahalliy bozorda (Moskva va Moskva viloyati) o'z mijozlari bor - shahar tarqatish markazidan mahsulot oladigan chakana sotuvchilar. Viloyat va shahar tarqatish markazlari markaziy tarqatish markazidan qayta tiklanadi.
Keling, tarqatish tarmog'ining bir qismini ajratib ko'rsatamiz:
- ishlab chiqarish korxonasining tayyor mahsulot ombori;
- markaziy tarqatish markazi;
- hududiy tarqatish markazi;
- shahar tarqatish markazi;
- ikkita ulgurji korxona;
- kompaniyaga tegishli chakana savdo nuqtasi;
- iste'molchilar.
Guruch. 4.22.
Keling, tarqatish tarmog'ining har bir bo'g'inini raqam bilan belgilaymiz va sig'imni yoylarning ustiga qo'yamiz. Bog'lanish turiga qarab o'tkazuvchanlik quvvati ishlab chiqarish quvvati hajmi, iste'molchilarning rejalashtirilgan ehtiyoji (talabi) va bozor sig'imi bilan ifodalanishi mumkin.
Mahsulotni tarqatish tarmog'i grafigi rasmda ko'rsatilgan. 4.23. Keling, matritsa quraylik D 0, unga biz tarqatish tarmog'i havolalarining o'tkazish qobiliyatining qiymatlarini kiritamiz (4.24-rasm).
Guruch. 4.23.
Guruch. 4.24.
Nol qatordan 1, 2 va 3 uchlarini (satr-ustunlarni) m = 0 indekslari bilan belgilaymiz va V, 30.10 va 10 ga teng.
Belgilangan 1-chiziqdan m = 1 va V4 = min (30,15) = 15, V5 = min (30,10) = 10 indekslari bilan 4 va 5 uchlarini belgilang.
3-qatordan biz 6-vertexni va nihoyat, 4-qatordan - 7-vertexni belgilaymiz (4.25-rasm).
Guruch. 4.25.
m bo'ylab orqaga qaytib, yo'lni topamiz: 4 dan 7 cho'qqiga, 1 dan 4 - cho'qqiga, 0 dan 1 - cho'qqiga; sozlash elementlari D Har bir oqim qiymati uchun 0 V7 = 15.
Keyingi qadam 5-oqimli yo'lni beradi (4.26-rasm).
Guruch. 4.26.
Keyingi qadam rasmda ko'rsatilgan natijani beradi. 4.27.
Guruch. 4.27.
Hech qanday belgi qo'yish mumkin emas. Bu yerdan biz maksimal oqim matritsasini olamiz (4.28-rasm).
Guruch. 4.28.
Tarmoqdagi maksimal oqimni topish algoritmini qo'llash natijasida natijalar rasmda keltirilgan. 4.29. Grafik yoylarida ko'rsatilgan qavsdagi raqamlar juftligi yoyning maksimal o'tkazuvchanligini va tarmoqqa etkazib beriladigan tovarlarning tavsiya etilgan hajmini ko'rsatadi.
Yoylardan o'tgan oqimlar yig'indisi v, yoylar tushgan oqimlar yig'indisiga teng w; bu summa oqim qiymati deb ataladi. Bizni, birinchi navbatda, mumkin bo'lgan eng katta qiymatga ega bo'lgan oqimlar - maksimal oqim deb ataladigan oqimlar qiziqtiradi. IN umumiy holat tarmoq bir necha xil maksimal oqimlarga ega bo'lishi mumkin, ammo ularning qiymatlari bir xil bo'lishi kerak. (4)
Tarmoq orqali maksimal oqimlarni o'rganish N = (V, D, a) kesim tushunchasi bilan chambarchas bog'liq, ya'ni. har qanday oddiy zanjir xossasiga ega bo'lgan D digrafining yoylarining shunday A to'plami v V A ga tegishli yoydan o'tadi.Kesim sig'imi unga tegishli yoylar sig'imlarining yig'indisiga teng. Mumkin bo'lgan eng kichik o'tkazuvchanlikka ega bo'lgan kesmalar minimal kesmalar deb ataladi.
Har qanday oqimning kattaligi har qanday kesimning o'tkazuvchanligidan oshmaydi va shuning uchun har qanday maksimal oqimning kattaligi har qanday minimal kesimning o'tkazuvchanligidan oshmaydi. Biroq, bu ikkalasi darhol aniq emas oxirgi raqamlar har doim bir-biriga teng; Bu natija 1955 yilda amerikalik matematiklar Ford va Fulkerson tomonidan olingan va maksimal oqim va minimal kesish teoremasi deb nomlangan.
Teorema (maksimal oqim va minimal kesish haqida). Har qanday tarmoqda har qanday maksimal oqimning o'lchami har qanday minimal kesish hajmiga teng.
Maksimal oqim va minimal kesish teoremasi berilgan oqim maksimal yoki yo'qligini tekshirishga imkon beradi, lekin faqat juda oddiy tarmoqlar uchun. Albatta, amalda biz katta va murakkab tarmoqlar bilan shug'ullanishimiz kerak va umuman olganda oddiy tanlash orqali maksimal oqimni topish qiyin. Keling, butun sonli o'tkazuvchanlikka ega har qanday tarmoqda maksimal oqimni topish uchun bitta algoritmni tasvirlaylik.
1-qadam. Birinchidan, nolga teng bo'lmagan qiymatga ega bo'lgan oqimni tanlaymiz (agar bunday oqim mavjud bo'lsa). Misol uchun, agar N - rasmda ko'rsatilgan tarmoq bo'lsa. 29.3, keyin shaklda ko'rsatilgan oqim. 29.4. Shuni ta'kidlash kerakki, biz tanlagan dastlabki oqimning qiymati qanchalik katta bo'lsa, keyingi qadamlar shunchalik oson bo'ladi.
2-qadam. N ga asoslanib, oqim yo'nalishini teskari tomonga o'zgartirib, yangi N tarmog'ini quramiz. Aniqroq qilib aytadigan bo'lsak, (a) = 0 bo'lgan har qanday a yoyi N' da o'zining dastlabki sig'imi bilan qoladi va har qanday a yoyi uchun , sig'imli a yoyi va sig'imi (a) bilan qarama-qarshi yoy bilan almashtiriladi. Bizning misolimizdagi N tarmog'i rasmda ko'rsatilgan. 29.5. Vertex v endi manba emas, balki lavabo.
3-qadam. Agar N' tarmog'ida biz nolga teng bo'lmagan oqimni topishimiz mumkin v c, keyin uni asl oqimga qo'shish va N da kattaroq qiymatdagi yangi oqimni olish mumkin. Endi siz tarmoqni qurishda N' o'rniga yangi N' ipidan foydalanib, 2-bosqichni takrorlashingiz mumkin. Ushbu protsedurani takrorlash orqali biz oxir-oqibat nol bo'lmagan oqimlarga ega bo'lmagan N' tarmog'iga erishamiz; keyin mos keladigan oqim maksimal oqim bo'ladi. Misol uchun, rasmda. 29.5 yoylar bo'ylab oqadigan nolga teng bo'lmagan oqim mavjud ( v,u), (u, z), (z,x), (x,y) va ( y,) birga teng, qolgan yoylardan o’tuvchi oqimlar esa nolga teng. Ushbu oqimni shakldagi oqimga qo'shish. 29.4, biz shaklda ko'rsatilgan oqimni olamiz. 29,6; 2-bosqichni takrorlash, bu maksimal oqim ekanligini ko'rsatish oson.
Ishlatilgan kitoblar:
(1) http://pgap.chat.ru/zap/zap264.htm#0
(2) Asanov M.O., Baranskiy V.A., Rasin V.V. Diskret matematika: matroid grafiklar, algoritmlar
(3) Basaker R., Saati T. Cheklangan grafiklar va tarmoqlar.
(4) Wilson R. Grafik nazariyasiga kirish
