Maksimal tarmoq oqimi. Maksimal oqimni topish algoritmi

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

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 bir marta oshiramiz, unda to'yingan yoy bo'lmaguncha.

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 cho'qqini 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 erishish uchun faqat bitta variant 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.

Javob: x 1 =1; x 3 =0; x 3 =4; W=3,5

UMUMIY ALGORITM

1. Tizimni tavsiflang. 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 qoʻllanma diskret matematika va/yoki grafiklar nazariyasi boʻyicha kurs oʻtayotgan talabalar uchun moʻljallangan.

Uning yordami bilan siz "Tarmoqdagi maksimal oqim va minimal kesish" mavzusini o'zlashtirasiz.

• To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin.=|Agar sizda MATLAB bo'lsa, ushbu sahifaga o'ting: u erda siz hisoblash skriptiga (dasturiga) aralashish imkoniyatiga egasiz. Bu erda tarmoqdagi maksimal oqim muammosi uni chiziqli dasturlash masalasiga qisqartirish yo'li bilan hal qilinadi. Keling, quyidagi belgini kiritamiz:
• n=|V| − grafik o‘lchami (cho‘qqilar soni);
• m E To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin.× n| − grafik kardinalligi (qirralar soni); A− o‘lchamdagi tarmoq digrafiyasining insidans matritsasi i; uning har bir elementi a ik=1 agar dan A- tepa chiqadi i k a ik-i yoyi; A=−1, agar mavjud boʻlsa
• s th cho'qqisi kiradi
• t-i yoyi; Va
• Boshqa hollarda =0; bunday matritsaning har bir ustunida aynan bitta, bitta minus bitta, qolganlari esa nolga teng;− tarmoqning manba cho‘qqisining soni; bu cho'qqidan faqat yoylar chiqishi kerak va boshqa har qanday cho'qqi manbadan yetib borishi kerak; − s m − tarmoq cho‘qqisining soni; bu cho'qqidan faqat yoylar kirishi kerak va boshqa har qanday cho'qqidan drenaj chiqishi mumkin bo'lishi kerak;
• Boshqa hollarda =0; bunday matritsaning har bir ustunida aynan bitta, bitta minus bitta, qolganlari esa nolga teng; a − t s m ;
• m unda faqat bittasi bo'lishi kerak, chunki manbadan faqat yoylar chiqishi kerak; t m -tarmoq digrafining insidans matritsasining qatori s; t unda faqat minuslar bo'lishi kerak, chunki drenajga faqat yoylar kirishi kerak;
• st − tarmoq digrafining insidans matritsasi n undan chiqarib yuborilganlar bilan th va th qatorlar; a ik e
• − uzunlikdagi ustun vektori − tarmoq digrafining insidans matritsasi n undan chiqarib yuborilganlar bilan ; uning har bir elementida e k a ik ichidagi oqimning kattaligi bo'ladi

th yoy;

c

c k

• ≥0 o'tkazish qobiliyatini o'rnatadi th va th yoy. th va = ; uning har bir elementida Keyin maksimal tarmoq oqimi muammosini chiziqli dasturlash muammosi sifatida shakllantirish mumkin:
• Manbadan (1) chiqadigan umumiy oqim maksimal darajaga ko'tariladi. Bundan tashqari, har qanday oraliq tepada kiruvchi oqim chiquvchi oqimga (2) teng va yoylarning sig'imi cheklangan (3).
• agar ikkita bunday komponent mavjud bo'lsa, unda tashlangan yoylar minimal kesimni beradi;
• agar ikkitadan ortiq ulangan komponentlar paydo bo'lsa, tarmoq digrafida bir nechta minimal kesmalar mavjud (tegishli chiziqli dasturlash muammosi buzilgan).

Degenerativ muammo uchun manbaga eng yaqin bo'lgan birinchi minimal kesish ushbu sahifada tuzilgan.

Ushbu sahifadan to'g'ri foydalanish uchun brauzeringiz skriptlarni qo'llab-quvvatlashi kerak Java skripti. Ularni yoqing.

Quyidagi kirish joylariga dastlabki ma'lumotlarni kiriting. Birinchi sohada tarmoqning digrafini chizish uchun cho'qqilarning koordinatalarini kiritishingiz kerak (aniqrog'i, mumkin). Ular matritsa shaklida ko'rsatilgan To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin.×2: birinchi ustunda - x th koordinatalari, ikkinchisida - y-e. Raqamlar butun sonlar, kasrli yoki eksponensial shaklda ko'rsatilishi mumkin. Raqamlarni bo'sh joylar bilan ajrating. Umumiy miqdor ushbu kirish maydonidagi chiziqlar digrafning o'lchamini aniqlaydi To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin.− uchlari soni. Ushbu dastlabki ma'lumotlar (cho'qqi koordinatalari) ixtiyoriydir: agar ular ko'rsatilmagan bo'lsa, tarmoq digrafiyasi to'g'ri chiziladi. To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin.-gon va uchlari soni keyingi kiritish maydonidagi maksimal cho'qqi soni bilan aniqlanadi.

Keyingi kirish maydonida chap tomoni- to'ldirish talab qilinadi. U tarmoq digrafining tuzilishini belgilaydi. n Digrafdagi har bir yoy ikkita cho'qqini bog'laydi. Ushbu cho'qqilarning raqamlari matritsa shaklida ko'rsatilgan ×2 ikkinchi kirish maydonining chap tomonida. Har bir satrda avval yoyning 1-choʻqqisi (dumi, manbasi), soʻngra boʻsh joy orqali yoyning 2-choʻqqisi (uch, drenaj) koʻrsatiladi. Ushbu ustunlar bo'lishi kerak To'g'ridan-to'g'ri ushbu qo'llanmadan siz kompyuteringizda MATLAB bo'lmasa ham, ID raqamingizni hisoblashingiz mumkin. natural sonlar n 1 dan

Ushbu ustunlarning har biridagi raqamlarning umumiy soni digrafning kardinalligini aniqlaydi − yoylar soni. , Hisoblash Yo'naltirilgan grafik berilgan bo'lsin G= har bir yoyning yo'nalishi qaysi vÎV V oqim yo'nalishini bildiradi (masalan, avtomobillar oqimi), har bir yoyning sig'imi ga teng t Va s d(v). t Ko'p cho'qqilarda s ikkita cho'qqisi ta'kidlangan t. Vertex s .

oqim manbai, - drenaj. Cho'qqidan o'tishi mumkin bo'lgan maksimal oqimni aniqlash talab qilinadi V bilan belgilaymiz x(v)

yoy bo'ylab harakatlanadigan oqim miqdori (6. 1)

v . Bu aniq 0 £ x(v) £ d(v) , vÎV .

Har bir cho'qqida)iÎE\(t,s)

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

Yuqori uchun t

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

uchi uchun s

(x(v)| iO V + (i)) -(x(v)¦ i O V - (i))= Q.(6.4)

Kattalik Q cho'qqidan chiqadigan oqimning kattaligi t va tepaga kiradi s.

Aniqlash kerak

Q ® maks(6.5)

cheklovlar ostida (6.1-6.4).

Miqdorlar Q, x(v) , vÎV, cheklovlarni qondirish (6.1-6.4) biz tarmoqdagi oqimni chaqiramiz va agar ular qiymatni maksimal darajada oshirsa Q, keyin maksimal oqim. Qadriyatlar ekanligini ko'rish oson Q=0, x(v)=0, vÎV, tarmoqdagi oqimdir.

(6.1-6.5) masala chiziqli dasturlash masalasi bo'lib, uni simpleks usuli algoritmlari yordamida yechish mumkin.

E cho'qqilar to'plamini ikkita ajratilgan E1 va E2 qismlarga shunday ajratamiz tÎE1, sÎE2. Kesish bo'yicha V(E1,E2), ajratish t Va s to'plamni chaqiramiz V(E1,E2)ÌV har bir yoy uchun shunday v O V(E1,E2) yoki h1(v)OE1 Va h2(v)OE2, yoki h1(v)OE2 Va h2(v)OE1.

Keling, to'plamni ajratamiz V(E1,E2) ikki qismga V(E1,E2,+),V(E1,E2,-) quyida bayon qilinganidek:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1 Va h2(v)OE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1 Va h1(v)OE2)

Kesimning o'tkazish qobiliyatini chaqiramiz

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

Quyidagi gaplar haqiqat

Teorema 1. (Maksimal oqim va minimal kesish haqida).

Har qanday tarmoqda manbadan maksimal oqim a zaxiraga olish s minimal o'tkazish qobiliyatiga teng Q(E1,E2) barcha qisqartirishlar orasida V(E1,E2), uchlarini ajratish t Va s.

E'tibor bering, maksimal oqimda

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Mayli Q, x(v), vÎV, - ba'zi tarmoq oqimi, ketma-ketligi

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

cho‘qqilarni bog‘lovchi zanjirdir t Va s. Keling, bu zanjirga tepadan harakat yo'nalishini o'rnatamiz t Kimga s. yoy v(j) bu zanjirdan uning yo'nalishi harakat yo'nalishiga to'g'ri kelsa, to'g'ri chiziq deyiladi t Kimga s, va aksincha. Biz bu zanjirni yo'l deb ataymiz ortib borayotgan oqim, agar tekis yoylar uchun bilan belgilaymiz zanjirlar x(v)< d(v) va teskari uchun x(v) > 0. Ushbu sxema orqali qo'shimcha oqim o'tkazilishi mumkin q dan t Kimga s hajmi q = min(q1,q2), Qayerda q1=min (d(v) -x(v)), minimal zanjirning barcha to'g'ri yoylari uchun olinadi, q1=min (x(v)), zanjirning barcha teskari yoylari uchun minimal qabul qilinadi.

Teorema 2.

Oqim Q, x(v) , vÎV, agar oqimni oshirishning hech qanday usuli bo'lmasa va faqat maksimal bo'ladi.

Tarmoqdagi maksimal oqim muammosini hal qilish uchun taklif qilingan algoritm oqimni ko'paytirish yo'lini topishga asoslangan. t. Vertex s, bu o'z navbatida vertex teglarini tartibga solish jarayoniga asoslangan. Buni aytaylik

cho'qqi i belgisi bilan belgilanadi q(i)>0, va to'g'ri yoy yoyi ham ma'lum v(i), bu oqim orqali kelgan yoki bilan belgilangan , kattalikdagi ba'zi qo'shimcha oqim bo'lsa q(i)>0, va teskari yoy ham ma'lum v(i), bu oqim orqali kirgan;

Agar uning barcha qo'shni cho'qqilari belgilangan bo'lsa, i cho'qqisi ko'riladi.

Agar cho'qqi s belgilangan bo'lsa, u holda oqimni kattalik bo'yicha oshirish uchun yo'l topildi q, bu yo'l bo'ylab o'tadi. Algoritmni tasvirlash uchun bizga massiv ham kerak SPW, unda belgilangan cho'qqilarning raqamlari belgilangan tartibda joylashgan. C1- massivdagi raqam SPW ko'rilgan cho'qqi, C2- bu massivdagi oxirgi belgilangan cho'qqi raqami.

Ushbu algoritmning g'oyasi manbadan cho'kmagacha 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 - qoldiq 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. Biz 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, uchidan 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 tarmoqning 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'imlarining qiymatlariga (i, j) 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. Ushbu 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

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

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 funksiya (munosabat (0) yoki (4)) shaklidan va transport hajmlarining manfiy emasligidan 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").

Yoylardan o'tgan oqimlar yig'indisi bilan belgilaymiz, yoylar tushgan oqimlar yig'indisiga teng w; bu summa oqim qiymati deb ataladi. Bizni, birinchi navbatda, mumkin bo'lgan eng katta hajmga 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 bilan belgilaymiz. Vertex 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 kesmaning 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, oddiy tanlov orqali maksimal oqimni topish qiyin. Keling, butun sonli o'tkazish qobiliyatiga ega har qanday tarmoqda maksimal oqimni topish uchun bitta algoritmni tasvirlab beraylik.

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 bilan belgilaymiz endi manba emas, balki lavabo.

3-qadam. Agar N' tarmog'ida biz nolga teng bo'lmagan oqimni topishimiz mumkin bilan belgilaymiz 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.

Foydalanilgan adabiyotlar:

(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