Metóda na nájdenie maximálneho prietoku. Príklad nájdenia maximálneho prietoku pomocou Ford-Fulkersonovej metódy
Hamiltonovské cykly
Graf je uvedený vo forme matice, kde bunky špecifikujú náklady na pohyb medzi bodmi. Symbol ∞ je umiestnený na hlavnej diagonále, aby eliminoval nezmyselnú cestu do seba.
Pretože Ak výsledná matica obsahuje stĺpec bez nulových prvkov, tak 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 | ∞ |
Zhrňme všetky odčítané prvky a získajme spodnú hranicu cyklu in= 2+2+3+2+1=10
1.2. Vyhodnoťme 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. Rozdeľme množinu ciest na dve podmnožiny: Q A.C.– cesty obsahujúce oblúk (AC) a Q A.C.– cesty, ktoré neobsahujú oblúk (AC). Pre druhú podmnožinu bude spodná hranica: v / = in + 6 = 10 + 2 = 12.
Na výpočet hranice pre prvú podmnožinu sa presunieme do matice o jeden rád nižšie, pričom prečiarkneme A-riadok a C-stĺpec. V novej matici na odstránenie reverznej cesty (CA) vložíme znamienko ∞ do zodpovedajúcej bunky.
Vypočítajme hranicu výslednej matice 2+0=2
a pridajte ho k spodnému okraju slučky. Táto suma v // =10+2=12 a bude hranicou pre prvú podmnožinu.
1.4. Porovnáme hranice všetkých visiacich vrcholov a vyberieme vrchol s najmenšou hranicou. Ak existujú dva z týchto vrcholov, vyberte ktorýkoľvek z nich. Toto je vrchol Q A.C., ktorej spodná hranica =12.
Vyberme si maximum z odhadov θ=max γ=γ BD=3
v / = 12 + 3 = 15.
1.6. Všetky nasledujúce body vykonávame podobne ako predchádzajúce.
Vyberme si maximum z odhadov θ=max γ=γ C B =∞
v / =in+ θ=∞
| A | |
| D |
Všetky riadky a stĺpce tejto matice obsahujú nuly. Preto limit zostáva rovný 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).
Vyberme dva pevné vrcholy: s- zdroj a t- vypustiť. Streamujte v sieti s→t zavolajme číselnú funkciu 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)
Vyžaduje sa na maximalizáciu premennej X
Vystrihnúť L v sieti oddeľujúcej vrcholy s t
nazývaný súbor oblúkov 
Akokoľvek s→t obsahuje aspoň jeden rezaný oblúk.
KRITÉRIÁ OPTIMALITY: v 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čítame hodnotu priepustnosti všetkých rezov. (K,V) – (T,V) rez s minimálnou priepustnosťou =6. Preto maximálny prietok =6.
Sieť s niekoľký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*). Definujme kapacitnú funkciu nastavením
SPÔSOB UMIESTNENIA ZNÁ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áciu opakujeme, kým nie je označený odtok. Ak tok zostane neoznačený, nájdený tok 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) nahradiť s f(j,t)+ε(t). Ak je zásoba označená (j-, ε(t)), To f(j,t) nahradiť s f(j,t)-ε(t). Poďme na vrchol j. Ak j má známku (i+, ε(j)), potom vymeníme f(i,j) na f(i,j)+ε(t), A keď (i-, ε(j)), f(j,i) nahradiť s f(j,i)-ε(t). Poďme na vrchol i. Túto operáciu opakujeme, 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,V)=0 |
| Krok 2 | 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 |
| Krok 3 | 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 |
| Krok 4 | 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 |
| Krok 5 | 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 |
| Krok 6 | A → (-, ∞) M → (A+,1) | Prietok je optimálny f=10 Minimálny rez: M→T-M→R-M→TO |
ÚLOHA. Nájdite najvyšší tok v sieti
ALGORITHM
Označme vrchol s= x 0. Všetky ostatné sú x i.
1. fáza
1. Vyberte ľubovoľnú cestu, ktorej všetky oblúky nie sú nasýtené.
2. Množstvo toku pozdĺž tejto dráhy zvyšujeme o jeden, až kým v ňom 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 х i už označený vrchol, potom označíme (+i) všetky neoznačené vrcholy, ku ktorým idú nenasýtené oblúky z х i, a indexom (–i) všetky neoznačené vrcholy, z ktorých idú oblúky s nenulovým tokom. do х 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 zväčšujeme o jeden ak pri pohybe z s Komu t orientácia oblúka sa zhoduje so smerom pohybu a zníži sa o jednu, ak má oblúk opačnú orientáciu. Prejdime na krok 1.
4. Keď vrchol t nie je možné označiť proces je ukončený a výsledný tok je najväčší tok siete.
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:
Na danej dopravnej sieti sa našiel úplný tok. Nasýtené oblúky sú zvýraznené
V tejto sieti môžete označiť aj konečný vrchol a výsledok označenia bude rovnaký. Zmenou toku dostaneme sieť, v ktorej nie je možné označiť konečný vrchol, takže tok v nej je najväčší a rovný 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. Dostaneme
V tejto sieti môžete označiť aj konečný vrchol a výsledok označenia bude rovnaký. Zmenou toku dostaneme sieť, v ktorej nie je možné označiť konečný vrchol, takže tok v nej je najväčší a rovný 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í; činnosť odvetvia počas niekoľkých 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 veľakrát vyriešiť jeden jednoduchý problém, ako raz vyriešiť zložitý.
PROBLÉM 1. O najvýhodnejšej trase 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ť povedzme, že vytýč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ždej z týchto sekcií sú známe.
PRÍKLAD 4.1. Nájdite minimálnu cestu z A do B.
Posledným krokom je dosiahnuť T.V. Pred posledným krokom by sme mohli byť v bodoch, z ktorých by sme mohli dosiahnuť T.V. v jednom kroku. Existujú dva takéto body (systém môže byť v jednom z dvoch stavov). Pre každú z nich existuje len jedna možnosť, ako dosiahnuť t.V: pre jednu - presun na východ; pre druhú - na sever. Napíšme náklady 4 a 3 v každom prípade.
4
Teraz poďme optimalizovať predposledný krok. Po predchádzajúcom kroku by sme mohli skončiť v jednom z troch bodov: C 1, C 2, C 3.
Pre bod C 1 je len jedna kontrola (označme ju šípkou) - pohyb na východ a náklady budú 2 (v tomto kroku) + 4 (v ďalšom kroku) = 6. Podobne pre položku C 3 budú náklady 2+3=5. Pre t.C 2 sú dve kontroly: choďte na východ alebo na sever. V prvom prípade budú náklady 3+3=6 av druhom prípade 1+4=5. To znamená, že podmienené optimálne ovládanie je ísť na sever. Označme si to ší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. Vyžaduje sa na naplnenie batohu schopného udržať ≤ 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ť alebo nebrať túto položku? Na každom kroku sú len 2 ovládacie prvky: kontrola =1, ak vezmeme túto položku; a 0 – ak to neberieme. Stav systému pred ďalším krokom je charakterizovaný hmotnosťou S, ktorá nám po dokončení predchádzajúcich krokov (niektoré položky už boli naložené) stále zostáva k dispozícii až do ukončenia plného naloženia, t.j. množstvo voľného miesta v batohu. ALGORITHM. 1. Začnime od posledného kroku. Urobme rôzne predpoklady o voľnom priestore v batohu: S=0,1,…R. Do batoha dajme poslednú vec, ak má dostatok úložného priestoru. 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 zisk v každom prípade ako súčet ziskov v aktuálnom kroku a v nasledujúcom už optimalizovanom kroku. Výsledky zapíšeme do pomocnej tabuľky. 3. V prvom kroku uvažujeme iba jediný možný stav S=R. 4. Hľadajme riešenie „pohybom vzad“, t.j. Optimálnou kontrolou 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 = 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ý generuje 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 konvenčný problém nelineárneho programovania.
Sformulujme problém ako problém dynamického programovania. Pre prvý krok vezmeme investovanie prostriedkov do podniku P 1, za druhý - do 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 – disponibilný stav 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. Je dôležité vedieť správne a „skromne“ nastaviť úlohu bez toho, aby sme ju preťažovali zbytočnými detailmi, čo najviac zjednodušili popis riadeného systému.
2. Rozdeľte operáciu na kroky (etapy). Tu treba brať do úvahy všetky primerané obmedzenia kladené na manažment. Krok musí byť dostatočne malý, aby postup optimalizácie riadenia kroku bol pomerne jednoduchý; a krok by zároveň nemal byť príliš malý, aby nedochádzalo k zbytočným výpočtom, 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. zapíšte si výplatné funkcie:
w i = f i (S, x i)
5. Určte, ako sa mení stav systému vplyvom riadenia x i pri prvom kroku, t.j. zapisovať funkcie zmeny stavu.
S / =φ i (S, x i)
6. Napíšte hlavnú rovnicu opakovaného dynamického programovania, vyjadrujúcu podmienené optimálne zosilnenie prostredníctvom 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álne riadenie v poslednom kroku.
W m (S) = max (f m (S, x m))
8. Vykonajte podmienenú optimalizáciu, počnúc predposledným krokom a končiac prvým krokom (cúvanie späť).
9. Vykonajte bezpodmienečnú optimalizáciu riadenia, v každom kroku „prečítajte“ zodpovedajúce odporúčania: v prvom kroku urobte nájdenú optimálnu kontrolu a zmeňte stav systému, v druhom kroku nájdite optimálnu kontrolu pre nájdený stav 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ť riadenie 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 neznamená, ž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 ďalších krokoch?
V praxi sa vyskytujú prípady, keď sa operácia musí plánovať na neurčito dlhú dobu. Modelom pre takýto prípad je nekonečný-krokový riadený proces, kde sú všetky kroky rovnaké. Tu výherná funkcia 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.Pridáme fiktívny zdroj a scedíme. Od zdroja po všetky biele vrcholy nakreslíme hrany s hmotnosťou B (náklady na ich prefarbenie na čierno). Od čiernych vrcholov po odtok nakreslíme hrany s hmotnosťou W (náklady na prefarbenie na bielo). A medzi všetky susedné vrcholy (či už sú rovnaké alebo rôzne farby) umiestnime hranu s hmotnosťou 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 medzi ne vložiť hranu s hmotnosťou rovnajúcou sa kapacitnému obmedzeniu tohto vrcholu.Riešenie
Pri klasickom probléme s minimálnym rezom je potrebné odstrániť okraje. Žiaden problém! Rozdeľme vrcholy na 2 a dáme medzi ne 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: Charkovská zimná škola programovania, 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. Musíte vytlačiť počet ciest z A do B pozdĺž takéhoto automatu.
Riešenie
Problém sa scvrkáva na nájdenie maximálneho počtu ciest bez toho, aby z jedného vrcholu pochádzalo viac ako jedna hrana rovnakej farby. 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, zvyšné vrcholy budú reprezentovať farby. Zo vstupného vrcholu kreslíme pozdĺž hrany s kapacitou 1 do každého z k vrcholov zodpovedajúcich farbe. Z vrcholov zodpovedajúcich 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ť. Pre každý typ mince vytvoríme jeden vrchol. Tieto topy budú zodpovedať vašim minciam. Potrebujeme nazbierať čo najviac unikátnych mincí, preto z každého takého vrcholu nakreslíme kapacitnú hranu 1 k umývadlu. Vo vrcholoch zodpovedajúcich minciam, ktoré máte na začiatku, nakreslíme hranu, ktorej kapacita sa rovná počtu takýchto mincí, ktoré máte.Pre každého člena klubu (okrem 1, teda vás) vytvoríme 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 získanú.
Ku každému takémuto vrcholu teda musíte nakresliť kapacitnú hranu 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 do vrcholu i, zodpovedajúce minciam, ktorých má člen klubu viac ako jednu.
Vybudovaná sieť odráža výmenné procesy v klube. Maximálny tok v takejto sieti sa bude rovnať maximálnemu počtu mincí, ktoré môžete nazbierať.
Zdroj: Charkovská zimná škola programovania, 2009, 4. deň
Je uvedený popis chladiaceho systému. Je potrebné zistiť, ako môže kvapalina prechádzať potrubím, aby boli splnené všetky stanovené podmienky.
Riešenie
Toto je problém nájsť cirkuláciu v sieti s danými nižšími obmedzeniami na okrajoch. Ak tok musí prechádzať pozdĺž okraja (u, v) v segmente , potom bude mať prestavaná sieť tri okraje (od, do, hmotnosť): (u, v, r - l), (S, v, l) , (u, T, l). S, T - dodatočne zavedený odtok a zdroj, resp. V skutočnosti prechádzame požadovaným minimálnym prietokom pozdĺž okraja a potom ho vyrovnávame tak, aby sme dosiahli cirkuláciu.Vyriešte problém nájdenia maximálneho toku v dopravnej sieti pomocou Ford-Fulkersonovho algoritmu a vytvorte sekciu siete S.
Počiatočné údaje:
Daná sieť S(X,U)
- zdroj siete; - odtok siete, kde ∈X; ∈X.
Hodnoty kapacity oblúka sú špecifikované 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 kapacity oblúka.). Hodnota prietoku rovnajúca sa „0“ nie je špecifikovaná.
2. Vyberte (ľubovoľne) cestu v sieti 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. Zvoľte si inú cestu, napríklad: X0-X2-X5-X7, nájdite 
a zvýšiť prietok o toto množstvo. Hrana X0-X2 je označená ako uvažovaná. 
5. Zvoľte si inú cestu, napríklad: X0-X3-X2-X5-X7, nájdite a zvýšte prietok o túto hodnotu. Hrana X3-X2 je označená ako uvažovaná. 
6. Od X0 do X7 už nie sú žiadne cesty, zhrňme zvýšenie prietoku: 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é.
Vrcholu X0 je priradené označenie. Všetkým vrcholom, pre ktoré nie je oblúk nasýtený, sú priradené značky (červené kruhy) 
Definujeme minimálne rezané oblúky: sú to oblúky, ktorých začiatky sú v označených vrcholoch a ktorých konce sú v neoznačených vrcholoch.
Toto sú oblúky:
Teda minimálny rez tejto siete 
Výpočet maximálnej hodnoty 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 závodu. Táto trieda problémov sa rieši nájdením maximálneho prietoku.
Uvažujme distribučnú sieť (obr. 4.21), v ktorej sú body 0 (vstup napr. sklad hotových výrobkov výrobcu) resp. 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 spojené, tzv priepustnosť oblúky. Hodnota priepustnosti charakterizuje maximálne prípustné množstvo toku materiálu, ktorý môže prejsť pozdĺž zodpovedajúceho oblúka za jednotku času.
Ryža. 4.21.
Množstvo produktov prechádzajúcich po oblúku z i predtým j , budeme to nazývať tok pozdĺž oblúka ( i ,j ) a označené . To je zrejmé
Ak vezmeme do úvahy, že celý materiálový tok vstupujúci do medziľahlého bodu siete ho musí úplne opustiť, dostaneme
Z prirodzenej požiadavky rovnosti tokov na vstupe a výstupe máme
Hodnotu Z nazveme hodnotou toku v sieti a postavíme problém maximalizácie Z za vyššie uvedených podmienok.
Nájdenie maximálneho prietoku spočíva v nájdení priepustnosti minimálneho rezu.
Uvažujme o univerzálnom vyhľadávacom algoritme v maticovej forme.
Počiatočná fáza algoritmu pozostáva z konštrukcie matice D 0, do ktorého sa zadávajú hodnoty priepustnosti (pre neorientovaný oblúk berieme symetrické hodnoty prvkov matice).
Hlavnými krokmi algoritmu je nájsť určitú cestu a opraviť tok pozdĺž tejto cesty.
Pri hľadaní cesty používame proces označovania. Symbolom * označíme nulový riadok a stĺpec matice (sieťový vstup). V 0. riadku hľadáme , označíme zodpovedajúce stĺpce indexmi
a presuňte označenia stĺpcov do riadkov. Potom vezmeme i-tý označený riadok, hľadáme v ňom neoznačený stĺpec s , ku ktorému priradíme indexové označenia
Štítky stĺpcov prenesieme do riadkov a pokračujeme v tomto procese, kým sa neoznačí n-tý stĺpec.
Potom pomocou indexov zistíme cestu, ktorá viedla k η-tému vrcholu pomocou indexov, a znížime kapacitu oblúkov cesty (prvkov matice) o V n a zvýšiť symetrické prvky o rovnakú hodnotu.
Tento postup pokračuje až do označenia n -topy sa nestanú nemožné.
Maximálny tok možno nájsť odčítaním od pôvodnej matice D 0, získané po vyššie uvedenej korekcii matice kapacity:
Príklad 4.4
Výroba sa nachádza v Moskve. Na distribúciu produktov spoločnosť láka sprostredkovateľov, ktorí so spoločnosťou spolupracujú prostredníctvom distribučných centier na rôznych úrovniach. V európskej časti Ruska je veľkoobchodný podnik 1, ktorý 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. Spoločnosť má vlastných klientov na miestnom trhu (Moskva a Moskovský región) - maloobchodníkov, ktorí dostávajú produkty z mestského distribučného centra. Regionálne a mestské distribučné centrá sa dopĺňajú z centrálneho distribučného centra.
Vyzdvihnime časť 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;
- dva veľkoobchodné podniky;
- maloobchodná predajňa vo vlastníctve spoločnosti;
- spotrebiteľov.
Ryža. 4.22.
Označme každý článok distribučnej siete číslom a umiestnime kapacitu nad oblúky. Priepustná kapacita 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 produktu je znázornený na obr. 4.23. Zostavme maticu D 0, do ktorého zadávame hodnoty priepustných kapacít spojov distribučnej siete (obr. 4.24).
Ryža. 4.23.
Ryža. 4.24.
Z nultého riadku označíme vrcholy (riadky-stĺpce) 1, 2 a 3 indexmi μ = 0 a V, rovná 30,10 a 10.
Z vyznačenej čiary 1 označte vrcholy 4 a 5 indexmi μ = 1 a V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Z riadku 3 vyznačíme vrchol 6 a napokon z riadku 4 – vrchol 7 (obr. 4.25).
Ryža. 4.25.
Návratom späť po μ nájdeme cestu: k vrcholu 7 z 4, k vrcholu 4 z 1, k vrcholu 1 z 0; nastavovacie prvky D 0 na 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 označenie nie je možné. Odtiaľ získame maticu maximálneho prietoku (obr. 4.28).
Ryža. 4.28.
V dôsledku aplikácie algoritmu na nájdenie maximálneho toku 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 tovaru dodávaného 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 tokov 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 , … , M k, ktorý nemá žiadne 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 A(M i).KROK 3. Korekcia aktuálnej hodnoty maximálneho prietoku v sieti. Pridávame tie, ktoré sa nachádzajú na KROK 2 hodnoty maximálnych prietokov v nezávislých trasách M 1 , … , M k k aktuálnemu celkovému maximálnemu toku siete: A t:= At + A(M 1)+ A(M 2)+…+ A(M k)KROK 4. Korekcia siete. Našiel na KROK 2 maximálne prietoky A(M 1), … , A(M k) odpočítané 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 nezostali 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 A:= A t, algoritmus sa ukončí, pretože celá kapacita siete bola vyčerpaná. Ak v upravenej sieti existujú trasy zo zdroja v a Na sklade v s, potom prejdite na KROK 2 a pokračovanie v vykonávaní algoritmu . Príklad 2 Pomocou tohto algoritmu nájdite maximálny prietok v sieti na obr. 1.15. Riešenie.KROK 1. Úvodné zadania. A t: = 0.I iterácia. KROK 2. Výber nezávislých trás v sieti a určenie tokov v nich. Ako M 1 cesta ( v a =V 1 , V 2 , V 5 , v s =V 7), uvažované v príklade 1. Pre neho A(M 1) = 10.
Je tiež ľahké izolovať nezávislé M 1 trasa M 2 = (v a =V 1 , V 3 , V 6 , v s =V 7). Vypočítajme pre ňu maximálnu priepustnosť a upravíme priepustnosť oblúkov: 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.
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 A(M 1), A(M 2) v trasách M 1 , M 2 sa odpočíta od kapacity ich oblúkov. Oblúky s nulovou zvyškovou kapacitou sú odstránené. Výsledok je uvedený na obr. 1.16 a. a) b) Obr. 1.16. Výsledok korekcie siete po iteráciách ja A IISTEP 5. Kontrola dokončenia algoritmu. V upravenej 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 s =V 7). Pokračovanie vykonávania algoritmu .II iterácia. KROK 2. Ako jedinú nezávislú trasu, ktorou ideme M 3 = (v a =V 1 , V 4 , V 2 , V 5 , v s =V 7). Pre neho:
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.
KROK 3. A t:= At + A(M 3) = 40 + 10= 50.KROK 4. Korekcia siete. Maximálny prietok A(M 3) odpočítajte od oblúkov trasy M 13. Výsledok je uvedený na obr. 1.16 b.
5. KROK V upravenej sieti nezostali žiadne trasy zdroj-odpad. A:= A t:= 50, dokončenie algoritmu. odpoveď: maximálny prietok v sieti na obr.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 kapacitou. Potom sa problém vyrieši pomocou obvyklého algoritmu. Požadované toky cez pôvodné zdroje budú toky pozdĺž novo pridaných oblúkov vstupujúcich do nich z nového spoločného zdroja. Urobte to isté, ak je v sieti niekoľko odtokov.
Plánovanie siete
Akákoľvek úloha navrhovania alebo konštrukcie 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ý rozsah činností na realizáciu projektu je prezentovaný ako súbor diania A Tvorba. Udalosti sa nazývajú jednotlivé fázy projektu. Práca je proces jej dokončenia. Celý komplex podujatí a prác potrebných na dokončenie projektu môže byť reprezentovaný formou dvojpólovej siete G =({v a, v z} , V, X), kde:
a všetko diania označené množinou vrcholov V, zvýraznené medzi nimi počiatočná udalosť v a(začiatok práce) a záverečná udalosť v z(dokončenie celého projektu), definujú vnútorné vrcholy siete prechodné udalosti- etapy, ktoré je potrebné dokončiť počas procesu implementácie projektu,
b) všetko práca sú naznačené oblúkmi spájajúcimi dvojice udalostí – vrcholov.
Grafické znázornenie tejto siete je tzv sieťový diagram. Ak chcete uviesť postupnosť akcií, zadajte aj sieťový diagram fiktívne diela, ktoré nie sú spojené s vykonávaním žiadnych úkonov. Príslušné 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ý prieskum zariadení, III) organizovanie predajnej siete, IV) realizácia reklamnej kampane, V) vypracovanie technických špecifikácií výrobných zariadení, VI) vypracovanie technickej dokumentácie výrobných priestorov a komunikácií, VII) nákup štandardných zariadení, VIII) návrh a výroba neštandardných zariadení, IX) výstavba výrobných zariadení 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 označíme v sieťovom diagrame 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 predajnej 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 zariadení a inštalácia komunikácií, 11) dokončenie inštalácie zariadenia a uvedenie do prevádzky,
12) dokončenie projektu (záverečné podujatie).
Vrcholy spájame so zodpovedajúcimi číslami k udalostiam. Plán siete pre projekt je znázornený na obr. 1.17:
Obr.1.17. Plán implementácie projektu siete
