Metóda na nájdenie maximálneho prietoku. Príklad nájdenia maximálneho prietoku pomocou Ford-Fulkersonovej metódy
Hamiltonovské cykly
Graf je daný vo forme matice, kde bunky obsahujú náklady na pohyb medzi bodmi. Symbol ∞ je umiestnený na hlavnej diagonále, aby sa vylúčila nezmyselná cesta do seba.
Pretože vo výslednej matici je stĺpec bez nulových prvkov, potom v ňom nájdeme minimálny prvok a odpočítame ho od všetkých prvkov tohto stĺpca.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Spočítajte všetky odčítané prvky a získajte spodnú hranicu cyklu v = 2+2+3+2+1=10
1.2. Odhadnime všetky nulové prvky matice.
Je vhodné prezentovať odhad núl v tabuľke.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ AC =2
1.3. Množinu ciest rozdeľujeme na dve podmnožiny: Q AC sú cesty obsahujúce oblúk (AC) a Q AC– cesty, ktoré neobsahujú oblúk (AC). Pre druhú podmnožinu bude spodná hranica: v / \u003d v + θ \u003d 10 + 2 \u003d 12.
Aby sme vypočítali hranicu pre prvú podmnožinu, prejdeme do matice o rádovo nižšie, pričom vymažeme A-riadok a C-stĺpec. V novej matici, aby sme vylúčili návratovú cestu (CA), vložíme do zodpovedajúcej bunky znamienko ∞.
Vypočítajte hranicu výslednej matice 2+0=2
a pridajte ho k spodnej hranici slučky. Táto suma v // =10+2=12 a bude hranicou pre prvú podmnožinu.
1.4. Porovnajte hranice všetkých visiacich vrcholov a vyberte vrchol s najmenšou hranicou. Ak existujú dva z týchto vrcholov, vyberte ktorýkoľvek z nich. Toto je top Q AC, ktorej spodná hranica je =12.
Vyberáme maximum z odhadov θ=max γ=γ BD=3
v / \u003d 12 + 3 \u003d 15.
1.6. Všetky nasledujúce body sa vykonávajú podobne ako predchádzajúce.
Vyberáme maximum z odhadov θ=max γ=γ C B =∞
v / =in+ θ=∞
| A | |
| D |
Všetky riadky a stĺpce tejto matice obsahujú nuly. Preto hranica zostáva na 12.
ÚLOHA. Nájdite hodnotu maximálneho toku na dopravnej sieti.
FORMULÁCIA PROBLÉMU.
Zvážte problém prenosu v sieti ( I,D,G) s danými kapacitami oblúkov c(i, j).
Vyberieme dva pevné vrcholy: s- zdroj a t- zásoba. Tok na sieti s→t zavolajme funkciu čísla f, definované na množine oblúkov a spĺňajúce nasledujúce lineárne rovnice a nerovnice:
0≤f(i,j) ≤c(i,j) pre akékoľvek (i,j)
Je potrebné maximalizovať premennú X
Vystrihnúť L v sieti, ktorá oddeľuje vrcholy s t
nazývaný súbor oblúkov 
Akokoľvek s→t obsahuje aspoň jeden rezaný oblúk.
KRITÉRIUM OPTIMALITY: na reálnej sieti hodnota ľubovoľného prietoku nepresahuje priepustnosť rezu a hodnota maximálneho prietoku sa rovná minimálnemu prietoku rezu.
PRÍKLAD 3.12.
M 9 K
M 8 K
PRÍKLAD 3.13.
M 2 K
RIEŠENIE :
Kapacita výstupného oblúka (T, B) presahuje celkovú kapacitu oblúkov vstupujúcich do zodpovedajúceho vrcholu. Aby sa sieť stala reálnou, nahradíme c(T, B)=5.
Nájdite a vypočítajte hodnotu priepustnosti všetkých rezov. (K, B) - (T, B) úsek s minimálnou priepustnosťou =6. Preto maximálny prietok =6.
Sieť s viacerými zdrojmi a záchytmi možno zredukovať na sieť s jedným zdrojom a záchytom.
PRÍKLAD. Nech je niekoľko zdrojov S a záchytov T (dopravný problém). Rozšírime sieť pridaním dvoch uzlov s* , t* a všetkých oblúkov (s*, S) , (T,t*). Rozšírime kapacitnú funkciu nastavením
SPÔSOB USPORIADANIE POZNÁMOK.
1. Počiatočný tok f(i,j) = 0.
Priraďme štítky k vrcholom tejto siete, ktoré budú mať tvar (i+, ε) alebo
(i-, ε). Označme zdroj (-, ∞),
tie . ε(s)= ∞.
2. Pre akýkoľvek označený vrchol i
vyberte všetky neoznačené vrcholy j
pre ktoré f(i,j)
Táto operácia sa opakuje, kým nie je označený odtok. Ak výlevka zostane neoznačená, nájdený prietok je maximálny a množina oblúkov spájajúcich označené vrcholy s neoznačenými tvorí minimálny rez.
3. Nechajte si zásobu označiť (j+, ε(t)), potom f(j,t) nahraď s f(j,t)+ε(t). Ak je zásoba označená (j-, ε(t)), potom f(j,t) nahraď s f(j,t)-ε(t). Poďme na vrchol j. Ak j je označený (i+, ε(j)), potom vymeníme f(i,j) na f(i,j)+ε(t), A keď (i-, ε(j)), f(j,i) nahraď s f(j,i)-ε(t). Poďme na vrchol i. Táto operácia sa opakuje, kým sa nedostaneme k zdroju s . Zmena prietoku sa zastaví, všetky značky sa vymažú a prejdite na krok 2
PRÍKLAD 3.14.
M 4 K
| 1 krok | 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 krok | A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) | f(K,B)=3 f(M,K)=3f(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 krok | 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 krok | 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 krok | A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) | f(A,M)=7 f(M,K)=4f(K,T)=lf(T,B)=7f(P,T)=4f(M,P)=lf( M, T) = 2 f(K,B)=3f(A,P)=3f(P,K)=0 |
| 6 krok | A → (-, ∞) M → (A+,1) | Prietok je optimálny f=10 Minimálny rez: M→T-M→R-M→Komu |
ÚLOHA. Nájdite najvyšší tok v sieti
ALGORITHM
Označte vrchol s= x 0. Všetko ostatné - x i.
1. fáza
1. Vyberte si ľubovoľnú cestu, ktorej všetky oblúky nie sú nasýtené.
2. Zvýšte hodnotu prietoku pozdĺž tejto dráhy o jednu, až kým v nej nebude nasýtený oblúk.
Pokračujeme v procese zvyšovania prietoku, až kým sa nevybuduje plný prietok, t.j. každá cesta bude obsahovať aspoň jeden nasýtený oblúk.
2. fáza
2. Ak je x i už označený vrchol, potom označíme (+i) všetky neoznačené vrcholy, do ktorých idú nenasýtené oblúky z x i, a indexom (–i) všetky neoznačené vrcholy, z ktorých idú oblúky s nenulovým tokom. do x i .
3. Ak je v dôsledku tohto procesu označený vrchol t, potom medzi s a t existuje cesta, ktorej všetky vrcholy sú označené číslami predchádzajúcich vrcholov. Prietok vo všetkých oblúkoch tejto dráhy sa zvýši o jeden, ak sa pri pohybe z s do t orientácia oblúka je rovnaká ako smer pohybu a ak má oblúk opačnú orientáciu, znížte ho o jednu. Prejdeme k bodu 1.
4. Keď vrchol t proces nie je možné označiť ako ukončený a výsledný tok je najväčší sieťový tok.
POZNÁMKA. Do fázy 2 môžete prejsť bez dokončenia prvej fázy (pozri príklad 3.16).
PRÍKLAD 3.15.
9
RIEŠENIE:
V danej dopravnej sieti sa nachádza úplný tok. Zvýraznené nasýtené oblúky
V tejto sieti môžete označiť aj koncový vrchol a výsledok označenia bude rovnaký. Zmenou toku dostaneme sieť, v ktorej nemožno označiť koncový vrchol, takže tok v nej je najväčší a rovná sa 10.
PRÍKLAD 3.16.
8 2 1
Na danej dopravnej sieti sa zistil neúplný tok
Označme sieť a zväčšíme v nej prietok podľa algoritmu. Získajte
V tejto sieti môžete označiť aj koncový vrchol a výsledok označenia bude rovnaký. Zmenou toku dostaneme sieť, v ktorej nemožno označiť koncový vrchol, takže tok v nej je najväčší a rovná sa 6.
Oddiel IV. DYNAMICKÉ PROGRAMOVANIE.
Dynamické programovanie sa používa na hľadanie optimálnych viacstupňových riešení. Napríklad dlhodobé plánovanie výmeny zariadení; činnosti tohto odvetvia už niekoľko rokov. Využíva princíp optimality, podľa ktorého každé nové čiastkové riešenie musí byť optimálne vzhľadom na dosiahnutý stav.
Je lepšie vyriešiť jeden jednoduchý problém mnohokrát ako jeden ťažký.
ÚLOHA 1. O najvýhodnejšej ceste medzi dvoma bodmi.
Je potrebné vybudovať cestu spájajúcu dva body A a B, z ktorých druhý leží na severovýchod od prvého. Pre jednoduchosť predpokladajme, že položenie cesty pozostáva zo série krokov a na každom kroku sa môžeme pohybovať buď na sever alebo na východ. Každá cesta je potom stupňovitá prerušovaná čiara, ktorej segmenty sú rovnobežné s jednou zo súradnicových osí. Náklady na výstavbu každého z týchto segmentov sú známe.
PRÍKLAD 4.1. Nájdite najkratšiu cestu z bodu A do bodu B.
Posledným krokom je dosiahnuť T.V. Pred posledným krokom by sme mohli byť v bodoch, z ktorých sa dá jedným krokom dosiahnuť e.V. Existujú dva takéto body (systém môže byť v jednom z dvoch stavov). Pre každého z nich existuje len jeden spôsob, ako dosiahnuť bod B: pre jeden z nich je možný pohyb na východ; pre druhú - na sever. Napíšme náklady 4 a 3 v každom prípade.
4
Teraz optimalizujeme predposledný krok. Po predchádzajúcom kroku by sme mohli skončiť na jednom z troch bodov: С 1 , С 2 , С 3 .
Pre bod C 1 je len jedna kontrola (označte ju šípkou) - presunúť sa na východ, pričom náklady budú 2(v tomto kroku)+4(v ďalšom kroku)=6. Podobne pre t C 3 budú náklady 2+3=5. Pre bod C 2 sú dva ovládacie prvky: choďte na východ alebo choďte na sever. V prvom prípade budú náklady 3+3=6 a v druhom prípade 1+4=5. Takže podmienená optimálna kontrola je ísť na sever. Označíme ho šípkou a zadáme zodpovedajúce náklady.
| |
| |
| |
| ÚLOHA 2. O naložení auta (o batohu). Je tam N položiek. Známa hmotnosť a i a hodnotu φi každú položku. Potrebujete naplniť batoh, ktorý udrží hmotnosť ≤ R , taký súbor predmetov, ktorý by mal najväčšiu hodnotu.
Proces nakladania batohu možno rozdeliť do N krokov. V každom kroku rozhodujeme o otázke: vziať túto položku alebo ju nebrať? Na každom kroku sú len 2 ovládacie prvky: kontrola = 1, ak vezmeme túto položku; a 0, ak neberieme. Stav systému pred ďalším krokom je charakterizovaný hmotnosťou S, ktorú máme po dokončení predchádzajúcich krokov (niektoré položky už boli naložené) stále k dispozícii až do konca plného zaťaženia, t.j. množstvo voľného miesta v batohu. ALGORITHM. 1. Začnime posledným krokom. Urobme rôzne predpoklady o voľnom priestore v batohu: S=0,1,…R. Do batohu dáme posledný predmet, ak je v ňom celkovo dosť miesta. 2. V každom predchádzajúcom kroku pre všetky možné stavy S zvažujeme 2 možnosti: vziať alebo nezobrať predmet. Nájdime výnos v každom prípade ako súčet výnosov v aktuálnom kroku a v nasledujúcom už optimalizovanom kroku. Výsledky sa zapisujú do pomocnej tabuľky. 3. V prvom kroku zvážte iba jediný možný stav S=R. 4. Nájdime riešenie „krokom späť“, t.j. pri optimálnej kontrole v prvom kroku zmeníme stav systému v druhom kroku: S=R– x 1 a 1 a zvoliť optimálne ovládanie x 2 pre tento stav. Atď. PRÍKLAD 4.2. Počiatočné údaje
Hlavný stôl
Pomocný stôl.
Odpoveď: x 4 \u003d 0; x3 = 1; x2=0; x 1 = 1; W=15 ÚLOHA 3. O rozdelení zdrojov. Existuje N podnikov P 1 , P 2 ,… P N , z ktorých každý dáva príjem φ k (x), ak je mu pridelený zdroj vo výške x. Je potrebné rozdeliť zdroj dostupný v množstve A medzi objekty tak, aby bol celkový príjem maximálny. Nech x k je množstvo zdrojov pridelených k-tému podniku. Potom sa uvažovaný problém zredukuje na obvyklý problém nelineárneho programovania.
Problém formulujeme ako problém dynamického programovania. V prvom kroku investujeme do podniku P 1, v druhom - v P 2 atď. Riadeným systémom sú v tomto prípade prostriedky, ktoré sa rozdeľujú. Stav systému pred každým krokom charakterizuje jeden parameter – hotovostná rezerva ešte nevložených prostriedkov. V tomto probléme sú krokovými kontrolami finančné prostriedky pridelené podnikom. Je potrebné nájsť optimálnu kontrolu (x 1, x 2, ... x N), pri ktorej je celkový príjem maximálny: | 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 |
Odpoveď: x 1 = 1; x3=0; x3=4; W = 3,5
VŠEOBECNÝ ALGORITHM
1. Popíšte systém. To znamená, pred každým krokom zistiť, aké parametre charakterizujú stav riadeného systému. Dôležité je vedieť správne a „skromne“ nastaviť úlohu, nezaťažovať ju zbytočnými detailmi, čo najviac zjednodušiť popis riadeného systému.
2. Rozdeľte operáciu na kroky (etapy). Tu treba brať do úvahy všetky rozumné obmedzenia kladené na manažment. Krok musí byť dostatočne malý, aby postup optimalizácie riadenia kroku bol celkom jednoduchý; a krok by zároveň nemal byť príliš malý, aby sa nerobili zbytočné výpočty, ktoré komplikujú postup pri hľadaní optimálneho riešenia, ale nevedú k výraznej zmene optima účelovej funkcie.
3. Zistite množinu krokových ovládacích prvkov x i pre každý krok a obmedzenia, ktoré sú na ne kladené.
4. Určte, aký zisk prináša riadenie x i na i-kroku, ak predtým bola sústava v stave S, t.j. napíšte výplatné funkcie:
w i = f i (S, x i)
5. Určte, ako sa mení stav systému vplyvom riadenia x i na I-tom kroku, t.j. zapisovať funkcie zmeny stavu.
S / =φ i (S, x i)
6. Napíšte hlavnú rovnicu rekurentného dynamického programovania vyjadrujúcu podmienenú optimálnu výplatu z hľadiska už známej funkcie
W i (S) = max (f i (S, x i) + W i + 1 (φ i (S, x i)))
7. Vykonajte podmienenú optimalizáciu posledného kroku, urobte rôzne predpoklady o tom, ako skončil predposledný krok, a pre každý z týchto predpokladov nájdite podmienenú (vybranú na základe podmienky, že krok niečím skončil) optimálnu kontrolu v poslednom kroku.
W m (S) = max (f m (S, x m))
8. Vykonajte podmienenú optimalizáciu, začnite od predposledného a končiac prvým krokom (späť).
9. Vykonajte bezpodmienečnú optimalizáciu riadenia, v každom kroku „prečítajte“ príslušné odporúčania: v prvom kroku urobte nájdenú optimálnu kontrolu a zmeňte stav systému, pre nájdený stav nájdite optimálnu kontrolu v druhom kroku atď. . až do posledného kroku.
PRINCÍP OPTIMALITY. Bez ohľadu na stav systému pred ďalším krokom je potrebné v tomto kroku zvoliť ovládanie tak, aby zosilnenie v tomto kroku plus optimálne zosilnenie vo všetkých nasledujúcich krokoch bolo maximálne.
Princíp dynamického programovania nepredpokladá, že každý krok je optimalizovaný samostatne, nezávisle od ostatných. Aký má zmysel vybrať si kontrolu, ktorej účinnosť je maximálna v jednom konkrétnom kroku, ak nás tento krok pripraví o možnosť dobre vyhrať v nasledujúcich krokoch?
V praxi sa vyskytujú prípady, kedy sa operácia musí plánovať na neurčito dlhú dobu. Model takéhoto prípadu je riadený proces s nekonečným počtom krokov, kde sú všetky kroky rovnaké. Tu funkcia výplaty a funkcia zmeny stavu nezávisia od čísla kroku.
Časť V. SIMULAČNÉ MODELOVANIE
Extrémny prípad: ak má matica rovnakú farbu - odpoveď je 0.Pridajme atrapa zdroj a drez. Nakreslite okraje od zdroja po všetky biele vrcholy s hmotnosťou v B (náklady na prefarbenie na čiernu). Nakreslíme okraje od čiernych vrcholov po odtok, s hmotnosťou vo W (náklady na prefarbenie na bielu). A medzi všetky susedné vrcholy (či už sú rovnakej alebo inej farby) - vložíme hranu s váhou v G (sivá čiara). Odpoveďou na problém bude hodnota maximálneho prietoku.
Zdroj: Celoukrajinská školská olympiáda v informatike, 2007, 1. deň
Riešenie
Všetko, čo potrebujeme, je rozdeliť každý vrchol na dva a vložiť medzi ne hranu, zvážiac limit šírky pásma tohto vrcholuRiešenie
V klasickom probléme s minimálnym rezom musíte odstrániť okraje. Žiaden problém! Vrcholy rozdelíme na 2 a medzi ne vložíme hranu s váhou 1. Potom je odpoveďou na problém nájsť minimálny rez v grafe (čo je maximálny prietok).Zdroj: Kharkiv Winter Programming School, 2009, 3. deň
Po prechode automatom z i do j po hrane k sa vymažú všetky prechody z i po hrane k, ako aj všetky prechody do j po hrane k. Je potrebné vytlačiť počet ciest z A do B pomocou takéhoto automatu.
Riešenie
Problém sa redukuje na nájdenie maximálneho počtu ciest a viac ako jedna hrana rovnakej farby neopúšťa jeden vrchol. Zredukujme problém na nájdenie maximálneho prietoku. Pre každý vrchol vytvoríme k+1 vrcholov v prestavanej sieti. Prvý vrchol bude vstupom, ostatné vrcholy budú reprezentovať farby. Zo vstupného vrcholu nakreslite hranu s kapacitou 1 ku každému z k vrcholov zodpovedajúcich farbe. Z vrcholu zodpovedajúceho farbe i nakreslíme všetky hrany farby i na vstupy koncov hrán. Po nájdení maximálneho toku v takejto sieti získame maximálny počet ciest, ktoré spĺňajú požadovanú vlastnosť.Riešenie
Poďme vybudovať sieť. Vytvorme jeden vrchol pre každý typ mincí. Tieto topy budú zodpovedať vašim minciam. Potrebujeme nazbierať čo najviac unikátnych mincí, preto si z každého takého vrcholu nakreslíme hranu kapacity 1 k umývadlu. Vo vrcholoch zodpovedajúcich minciam, ktoré máte na začiatku, nakreslíme hranu, ktorej priepustnosť sa rovná počtu takýchto mincí, ktoré máte.Za každého člena klubu (okrem 1, teda vás) získame jeden vrchol. Tento vrchol môže prijať najviac jednu mincu, ktorú nemá, a dať
najviac k-1 mincí, z ktorých má k (k > 1). Prirodzene, člen klubu dáva jednu mincu výmenou za jednu prijatú.
Ku každému takémuto vrcholu je teda potrebné nakresliť hranu kapacity 1 z vrcholov zodpovedajúcich minciam, ktoré tento člen klubu nemá. A z týchto vrcholov je potrebné nakresliť hrany s kapacitou k i - 1 k vrcholu i, zodpovedajúce minciam, ktorých má člen klubu viac ako jednu.
Vybudovaná sieť odráža procesy výmeny v klube. Maximálny tok v takejto sieti sa bude rovnať maximálnemu počtu mincí, ktoré môžete nazbierať.
Zdroj: Kharkiv Winter Programming School, 2009, 4. deň
Je uvedený popis chladiaceho systému. Je potrebné zistiť, ako je možné previesť kvapalinu potrubím tak, aby boli splnené všetky uvedené podmienky.
Riešenie
Toto je problém nájsť cirkuláciu v sieti s danými obmedzeniami dolnej hrany. Ak hrana (u, v) musí mať tok v segmente , potom bude mať rekonštruovaná sieť tri hrany (odkiaľ, kde, hmotnosť): (u, v, r - l), (S, v, l) , (u, T, 1). S, T - dodatočne zavedený odtok a zdroj, resp. V skutočnosti prechádzame požadovaným minimálnym prietokom pozdĺž okraja, po ktorom ho vyvažujeme tak, aby sme získali cirkuláciu.Vyriešte problém nájdenia maximálneho toku v dopravnej sieti pomocou Ford-Fulkersonovho algoritmu a zostrojte časť siete S.
Počiatočné údaje:
Daná sieť S(X,U)
- sieťový zdroj; - záchyt siete, kde ∈X; ∈X.
Hodnoty kapacít oblúka sú uvedené v smere orientácie oblúka: od indexu i po index j.
r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20
1. Nastavte nulový prietok na sieti (na všetkých oblúkoch je hodnota prietoku 0). Nulový tok je počiatočný povolený tok v sieti. Hodnota prietoku na každom oblúku bude uvedená mimo zátvoriek priepustnosti oblúka.). Hodnota toku rovnajúca sa "0" nie je špecifikovaná.
2. V sieti si vyberte (ľubovoľne) cestu vedúcu z vrcholu x0 do vrcholu x7:
X0-X1-X4-X6-X7
3. Nájdite 
a zvýšiť prietok o toto množstvo. Hrana X1-X4 je označená ako uvažovaná. 
4. Vyberieme ešte jeden spôsob, napríklad: X0-X2-X5-X7, nájdeme 
a zvýšiť prietok o toto množstvo. Okraj X0-X2 označíme ako uvažovaný. 
5. Zvolíme ešte jeden spôsob, napríklad: X0-X3-X2-X5-X7, nájdite a zväčšite prietok o túto hodnotu. Okraj X3-X2 označíme ako uvažovaný. 
6. Od X0 do X7 už nie sú žiadne cesty, zhrnieme prírastky toku: 25+10+20=55.
Záver: maximálny prietok je 55.
2) Zostrojte časť siete S.
Postup označovania vrcholov.
Počiatočný stav: všetky vrcholy sú neoznačené.
Vrchol X0 je označený. Všetkým vrcholom, pre ktoré nie je oblúk nasýtený, sú priradené značky (červené kruhy) 
Určujeme oblúky minimálneho rezu: sú to oblúky, ktorých začiatky sú umiestnené na označených vrcholoch a konce sú umiestnené na neoznačených vrcholoch.
Toto sú oblúky:
Teda minimálny rez tejto siete 
Výpočet maximálneho prietoku
Pri plánovaní racionálnej distribúcie produktov v distribučnej sieti je potrebné koordinovať kapacitu kanálov s potrebami zákazníkov a s kapacitou výrobného podniku. Táto trieda problémov je riešená metódou hľadania maximálneho prietoku.
Uvažujme distribučnú sieť (obr. 4.21), v ktorej sú zvýraznené body 0 (vstup napr. sklad hotových výrobkov výrobcu) a P (výstup, distribučné centrá, sklady veľkoobchodných a maloobchodných organizácií, spotrebiteľ) a každý oblúk (segment) spojovacie body i a j, číslo dij > 0 je priradené, volané priepustnosť oblúky. Hodnota priepustnosti charakterizuje maximálne prípustné množstvo toku materiálu, ktorý môže prejsť zodpovedajúcim oblúkom za jednotku času.
Ryža. 4.21.
Množstvo produktov prechádzajúcich pozdĺž oblúka z i predtým j , budeme nazývať tok pozdĺž oblúka ( i ,j ) a označené . To je zrejmé
Ak vezmeme do úvahy, že celý materiálový tok, ktorý vstúpil do medziľahlého bodu siete, ho musí úplne opustiť, získame
Z prirodzenej požiadavky rovnosti tokov na vstupe a výstupe máme
Hodnotu Z nazveme hodnotou toku v sieti a nastavíme problém maximalizácie Z za vyššie uvedených podmienok.
Hľadanie maximálneho prietoku sa redukuje na hľadanie priepustnosti minimálneho rezu.
Uvažujme o univerzálnom vyhľadávacom algoritme v maticovej forme.
Počiatočná fáza algoritmu spočíva v konštrukcii matice D 0, v ktorom sú zadané hodnoty šírky pásma (pre neorientovaný oblúk berieme symetrické hodnoty prvkov matice).
Hlavnými krokmi algoritmu je nájsť nejakú cestu a opraviť tok pozdĺž tejto cesty.
Pri hľadaní cesty využívame proces značenia. Nulový riadok a stĺpec matice (sieťový vstup) označíme symbolom *. V 0. riadku nájdeme , príslušné stĺpce označíme indexmi
a preniesť označenia stĺpcov do riadkov. Potom vezmeme ί-tý označený riadok, hľadáme v ňom neoznačený stĺpec s , ku ktorému porovnáme štítky-indexy
Označenie stĺpcov prenesieme do riadkov a pokračujeme v tomto procese, kým nebude označený n-tý stĺpec.
Potom „obrátením“ podľa indexov zistíme cestu, ktorá viedla k η-tému vrcholu, znížime kapacity oblúkov dráhy (prvkov matice) o V n a zvýšiť symetrické prvky o rovnakú hodnotu.
Tento postup pokračuje až po značku n -tý vrchol sa nestane nemožným.
Maximálny prietok možno nájsť odčítaním od pôvodnej matice D 0, získané po vyššie uvedenej korekcii matice šírky pásma:
Príklad 4.4
Výroba sa nachádza v Moskve. Na distribúciu produktov spoločnosť angažuje sprostredkovateľov, ktorí so spoločnosťou spolupracujú prostredníctvom distribučných centier rôznych úrovní. Veľkoobchod 1 pôsobí v európskej časti Ruska a obsluhuje centrálne distribučné centrum. Veľkoobchodný podnik 2 pôsobí v blízkom zahraničí (Ukrajina, Bielorusko) a je obsluhovaný regionálnym distribučným centrom. Podnik má svojich vlastných zákazníkov na miestnom trhu (Moskva a Moskovský región) - maloobchodníkov, ktorí dostávajú výrobky z mestského distribučného centra. Zásoby regionálnych a mestských distribučných centier sa dopĺňajú z centrálneho distribučného centra.
Vyberme fragment distribučnej siete:
- sklad hotových výrobkov výrobného podniku;
- centrálne distribučné centrum;
- regionálne distribučné centrum;
- mestské distribučné centrum;
- dvaja veľkoobchodníci;
- maloobchodná predajňa vo vlastníctve spoločnosti;
- spotrebiteľov.
Ryža. 4.22.
Každý článok distribučnej siete bude označený číslom a priepustnosť zapíšeme nad oblúky. Priepustnosť v závislosti od typu spojenia môže byť vyjadrená objemom výrobnej kapacity, plánovanou potrebou (dopytom) spotrebiteľov a kapacitou trhu.
Graf distribučnej siete produktov je znázornený na obr. 4.23. Zostavme maticu D 0, do ktorého zadáme hodnoty priepustnosti spojov distribučnej siete (obr. 4.24).
Ryža. 4.23.
Ryža. 4.24.
Z nultého riadku označíme vrcholy (riadok-stĺpce) 1, 2 a 3 s indexmi μ = 0 a V, rovná 30,10 a 10.
Z označeného riadku 1 označte vrcholy 4 a 5 indexmi μ = 1 a V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Z riadku 3 označíme vrchol 6 a nakoniec z riadku 4 - vrchol 7 (obr. 4.25).
Ryža. 4.25.
Pri spätnom pohybe po μ nájdeme cestu: k vrcholu 7 z 4, k vrcholu 4 z 1, k vrcholu 1 z 0; úprava prvkov D 0 o hodnotu prietoku V7 = 15.
Ďalším krokom je dráha s prietokom 5 (obr. 4.26).
Ryža. 4.26.
Ďalším krokom je výsledok znázornený na obr. 4.27.
Ryža. 4.27.
Ďalšie značenie nie je možné. Odtiaľ dostaneme maticu maximálneho prietoku (obr. 4.28).
Ryža. 4.28.
Výsledkom aplikácie algoritmu na nájdenie maximálneho prietoku v sieti sú výsledky uvedené na obr. 4.29. Dvojice čísel v zátvorkách zobrazené na oblúkoch grafu označujú maximálnu priepustnosť oblúka a odporúčaný objem dodávky tovaru do siete.
Algoritmus na výpočet maximálneho prietoku v sieťach
KROK 1. Úvodné úlohy. súčasná hodnota A t maximálny prietok v sieti má priradenú hodnotu 0. KROK 2. Výber nezávislých trás v sieti a určenie prietokov v nich. Z celej množiny možných trás v sieti od zdroja po záchytku vyberáme nezávislé trasy M 1 , … , Mk, ktoré nemajú spoločné vrcholy, okrem počiatočného (zdroj v a) a konečná (odtok v s). Pre každú zvolenú trasu M i(1 £ i£ k) určiť maximálny prietok ALE(M i).KROK 3. Korekcia aktuálnej hodnoty maximálneho prietoku v sieti. Pridávame nájdené KROK 2 hodnoty maximálnych prietokov v nezávislých trasách M 1 , … , Mk k aktuálnemu celkovému maximálnemu toku siete: A t:= At + A(M 1)+ A(M 2)+…+ A(Mk).KROK 4. Oprava siete. našiel na KROK 2 maximálne prietoky ALE(M 1), … , ALE(Mk) odpočítajte od kapacity zodpovedajúcich sieťových oblúkov. Oblúky s nulovou zvyškovou kapacitou sú odstránené. KROK 5. Kontrola dokončenia algoritmu. Ak po oprave nezostanú v sieti žiadne trasy zo zdroja v a Na sklade v s, potom sa požadovaný maximálny prietok v sieti rovná nájdenému prúdu ALE:= A t, algoritmus ukončí svoju prácu, pretože celá šírka pásma siete je vyčerpaná. Ak v opravenej sieti existujú trasy zo zdroja v a Na sklade v s, potom prechod na KROK 2 a pokračujte vo vykonávaní algoritmu . Príklad 2 Nájdite maximálny prietok v sieti na obrázku 1.15 pomocou tohto algoritmu. Riešenie KROK 1. Úvodné úlohy. A t: = 0.I iterácia. KROK 2. Výber nezávislých trás v sieti a určenie prietokov v nich. Ako M 1 cesta ( v a =V 1 , V 2 , V 5 , v c \u003d V 7) uvažované v príklade 1. Pre neho ALE(M 1) = 10.
Je tiež ľahké rozlíšiť nezávisle od M 1 trasa M 2 = (v a =V 1 , V 3 , V 6 , v c \u003d V 7). Vypočítajme pre ňu maximálnu priepustnosť a upravíme priepustnosť oblúkov: ALE(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.
KROK 3. Korekcia aktuálnej hodnoty maximálneho prietoku v sieti. A t:= At + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.KROK 4. Korekcia siete. našiel na KROK 2 maximálne prietoky ALE(M 1), ALE(M 2) v trasách M 1 , M 2 odpočítajte od kapacity ich oblúkov. Oblúky s nulovou zvyškovou kapacitou sú odstránené. Výsledok je uvedený na obrázku 1.16 a. a) b) Obr.1.16. Výsledok korekcie siete po iteráciách ja a II KROK 5. Kontrola dokončenia algoritmu. V opravenej sieti (obr. 1.16 a) sú trasy od zdroja v a Na sklade v s, napríklad M 3 = (v a =V 1 , V 4 , V 2 , V 5 , v c \u003d V 7). Pokračujúce vykonávanie algoritmu .II iterácia. KROK 2. Ako jedinú nezávislú cestu ideme M 3 = (v a =V 1 , V 4 , V 2 , V 5 , v c \u003d V 7). Pre neho:
ALE(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.
KROK 3. A t:= At + A(M 3) = 40 + 10= 50.KROK 4. Korekcia siete. Maximálny prietok ALE(M 3) odpočítajte od oblúkov trasy M 13. Výsledok je uvedený na obrázku 1.16 b.
5. KROK V upravenej sieti nezostali žiadne trasy zdroj-odpad. ALE:= A t:= 50, dokončenie algoritmu. odpoveď: maximálny tok siete na obrázku 1.15 je 50.Ak je v sieti špecifikovaných viacero zdrojov, je ukončená zavedením nového spoločného zdroja, ktorý je s pôvodnými zdrojmi spojený oblúkmi s neobmedzenou šírkou pásma. Potom sa problém vyrieši podľa obvyklého algoritmu. Požadované toky cez pôvodné zdroje budú toky pozdĺž novo pridaných oblúkov, ktoré do nich vstupujú z nového spoločného zdroja. To isté platí, ak je v sieti niekoľko zásuviek.
Plánovanie siete
Akákoľvek úloha navrhovania alebo výstavby pomerne zložitého objektu ( projektu) možno rozdeliť na niekoľko menších krokov. Načasovanie celého projektu závisí od správneho výberu postupnosti týchto krokov.
Celý komplex akcií na realizáciu projektu je prezentovaný vo forme súboru diania a Tvorba. Udalosti sa nazývajú jednotlivé etapy projektu. Úlohy sú proces, ktorým sú dokončené. Celý komplex podujatí a prác potrebných na realizáciu projektu možno reprezentovať ako dvojpólovú sieť G =({v i, v z} , V, X), kde:
a všetko vývoj označené mnohými vrcholmi V, medzi nimi zvýraznené počiatočná udalosť v a(začiatok práce) a záverečná udalosť v(dokončenie celého projektu), definujú vnútorné vrcholy siete prechodné udalosti- kroky, ktoré sa majú vykonať počas realizácie projektu,
b) všetky práca sú naznačené oblúkmi spájajúcimi dvojice udalostí – vrcholov.
Grafické znázornenie tejto siete je tzv sieťový graf. Na označenie postupnosti akcií v sieťovom diagrame tiež zavádzajú fiktívne diela, ktoré nie sú spojené s vykonávaním žiadnych úkonov. Zodpovedajúce práce sú označené prerušovanými oblúkmi.
Ako príklad zvážte organizáciu nejakej výroby. Projekt si vyžaduje nasledujúce práce:
I) marketingový prieskum, II) predprojektový výskum zariadení, III) organizácia predajnej siete, IV) reklamná kampaň, V) vypracovanie technických špecifikácií výrobných zariadení, VI) vypracovanie technickej dokumentácie výrobných zariadení a komunikácií, VII ) nákup štandardných zariadení, VIII) návrh a výroba neštandardných zariadení, IX) výstavba priemyselných priestorov a inštalácia komunikácií, X) inštalácia štandardných zariadení, XI) inštalácia neštandardných zariadení, XII) uvedenie do prevádzky.
Tieto práce sú v sieťovom diagrame označené oblúkmi s príslušnými číslami.
Udalosti v tomto projekte budú nasledovné:
1) začiatok prác (úvodná akcia), 2) ukončenie marketingového prieskumu, 3) ukončenie predprojektového výskumu, 4) organizácia distribučnej siete, 5) organizácia reklamnej kampane, 6) príprava technických špecifikácií pre výrobu zariadení, 7) dokončenie vypracovania technickej dokumentácie výrobných priestorov a komunikácií, 8) dokončenie nákupu štandardného vybavenia, 9) dokončenie návrhu a výroby neštandardných zariadení, 10) dokončenie výstavby výrobných priestorov a inštalácie komunikácie, 11) dokončenie inštalácie zariadenia a uvedenie do prevádzky,
12) ukončenie projektu (ukončenie projektu).
Udalosti sú spojené s vrcholmi so zodpovedajúcimi číslami. Harmonogram siete pre realizáciu projektu je uvedený na obr. 1.17:
Obr.1.17. Plán siete projektu
