Metoda za određivanje maksimalnog protoka. Primjer određivanja maksimalnog protoka Ford-Fulkersonovom metodom
Hamiltonovi ciklusi
Graf je dan u obliku matrice, gdje ćelije određuju trošak kretanja između točaka. Simbol ∞ postavljen je na glavnu dijagonalu kako bi eliminirao besmislen put u sebe.
Jer Ako dobivena matrica sadrži stupac bez nula elemenata, tada ćemo pronaći minimalni element u njemu i oduzeti ga od svih elemenata tog stupca.
| A | B | C | D | |
| A | ∞ | |||
| B | ∞ | |||
| C | ∞ | |||
| D | ∞ |
Zbrojimo sve oduzete elemente i dobijemo donju granicu ciklusa u= 2+2+3+2+1=10
1.2. Procijenimo sve nulte elemente matrice.
Prikladno je procjenu nula prikazati u tablici.
| A | B | C | D | |
| A | ||||
| B | ||||
| C | ||||
| D |
θ=max γ=γ A C =2
1.3. Podijelimo skup staza u dva podskupa: Q A.C.– putanje koje sadrže luk (AC) i Q A.C.– staze koje ne sadrže luk (AC). Za drugi podskup donja granica će biti: u / = u + θ =10+2=12.
Kako bismo izračunali granicu za prvi podskup, pomičemo se na matricu jedan red veličine niže, križajući A-redak i C-stupac. U novoj matrici za eliminaciju obrnutog puta (CA) stavljamo znak ∞ u odgovarajuću ćeliju.
Izračunajmo granicu rezultirajuće matrice 2+0=2
i dodajte ga donjem rubu petlje. Ovaj iznos u // =10+2=12 i bit će granica za prvi podskup.
1.4. Usporedimo granice svih visećih vrhova i izaberimo vrh s najmanjom granicom. Ako postoje dva od ovih vrhova, odaberite bilo koji od njih. Ovo je vrh Q A.C., čija je donja granica =12.
Izaberimo maksimum od procjena θ=max γ=γ BD =3
u / =12+3=15.
1.6. Sve sljedeće točke izvodimo slično prethodnima.
Izaberimo maksimum od procjena θ=max γ=γ C B =∞
u / =u+ θ=∞
| A | |
| D |
Svi redovi i stupci ove matrice sadrže nule. Stoga granica ostaje jednaka 12.
ZADATAK. Odredite vrijednost maksimalnog protoka na prometnoj mreži.
FORMULACIJA PROBLEMA.
Razmotrite problem prijenosa na mreži ( I,D,G) sa zadanim kapacitetima luka c(i,j).
Izaberimo dva fiksna vrha: s- izvor i t– odvod. Stream na mreži s→t nazovimo numeričku funkciju f, definirana na skupu lukova i koja zadovoljava sljedeće linearne jednadžbe i nejednadžbe:
0≤ f(i,j) ≤c(i,j) za bilo koji (i J)
Potrebno za maksimiziranje varijable x
Izrežite L u mreži koja razdvaja vrhove s t
naziva skup lukova 
Na bilo koji način s→t sadrži najmanje jedan presječeni luk.
KRITERIJI OPTIMALNOSTI: na realnoj mreži vrijednost proizvoljnog protoka ne prelazi propusnost presjeka, a vrijednost maksimalnog protoka jednaka je minimalnoj propusnosti presjeka.
PRIMJER 3.12.
M 9 K
M 8 K
PRIMJER 3.13.
M 2 K
RIJEŠENJE :
Kapacitet izlaznog luka (T,B) premašuje ukupni kapacitet lukova koji ulaze u odgovarajući vrh. Da bi mreža postala stvarna zamijenimo c(T,B)=5.
Pronađimo i izračunajmo vrijednost propusnih kapaciteta svih usjeka. (K,V) – (T,V) rez s minimalnom propusnošću =6. Stoga, maksimalni protok =6.
Mreža s nekoliko izvora i ponora može se svesti na mrežu s jednim izvorom i ponorom.
PRIMJER. Neka postoji nekoliko izvora S i ponora T (problem transporta). Proširimo mrežu dodavanjem dva čvora s*, t* i svih lukova (s*, S) , (T,t*). Definirajmo funkciju kapaciteta postavljanjem
NAČIN POSTAVLJANJA OZNAKA.
1. Početni tok f(i,j) = 0.
Dodijelimo oznake vrhovima te mreže koji će imati oblik (i+, ε) ili
(i - , ε). Označimo izvor (-, ∞),
oni . ε(s)= ∞.
2. Za bilo koji označeni vrh ja
odaberite sve neoznačene vrhove j
za koji f(i,j)
Ovu operaciju ponavljamo sve dok se odvod ne označi. Ako tok ostane neoznačen, tada je pronađeni tok maksimalan, a skup lukova koji povezuju označene vrhove s neoznačenim čini minimalni rez.
3. Neka dionica bude označena (j+, ε(t)), Zatim f(j,t) zamijeniti s f(j,t)+ε(t). Ako je dionica označena (j-, ε(t)), To f(j,t) zamijeniti s f(j,t)-ε(t). Idemo na vrh j. Ako j ima oznaku (i+, ε(j)), zatim zamijenimo f(i,j) na f(i,j)+ε(t), i ako (i-, ε(j)), f(j,i) zamijeniti s f(j,i)-ε(t). Idemo na vrh ja. Ovu operaciju ponavljamo dok ne dođemo do izvora s. Promjena protoka se zaustavlja, sve oznake se brišu i prijeđite na korak 2
PRIMJER 3.14.
M 4 K
| 1 korak | 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 |
| Korak 2 | 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. korak | 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 |
| Korak 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 |
| Korak 5 | 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 |
| Korak 6 | A → (-, ∞) M → (A+,1) | Protok je optimalan f=10 Minimalni rez: M→T-M→R-M→DO |
ZADATAK. Pronađite najveći protok na mreži
ALGORITAM
Označimo vrh s= x 0 . Svi ostali su x i.
1. faza.
1. Odaberite bilo koji put čiji svi lukovi nisu zasićeni.
2. Povećavamo količinu protoka duž ove staze za jedan sve dok u njoj više nema zasićenog luka.
Proces povećanja protoka nastavljamo dok se ne izgradi puni protok, tj. svaka staza će sadržavati barem jedan zasićeni luk.
Faza 2.
2. Ako je h i već označeni vrh, tada označavamo (+i) sve neoznačene vrhove do kojih iz h i idu nezasićeni lukovi, a indeksom (–i) sve neoznačene vrhove iz kojih idu lukovi s protokom različitim od nule do h i.
3. Ako je kao rezultat ovog procesa označen vrh t, zatim između s I t postoji put čiji su svi vrhovi označeni brojevima prethodnih vrhova. Povećavamo protok u svim lukovima ove staze za jedan ako, kada se krećemo od s Do t orijentacija luka poklapa se sa smjerom kretanja, a smanjuje se za jedan ako je luk suprotne orijentacije. Prijeđimo na 1. korak.
4. Kada je vrh t nemoguće je označiti da je proces prekinut i rezultirajući protok je najveći protok mreže.
BILJEŠKA. Možete prijeći na fazu 2 bez dovršetka prve faze (vidi primjer 3.16).
PRIMJER 3.15.
9
RIJEŠENJE:
Potpuni tok je pronađen na danoj transportnoj mreži. Zasićeni lukovi su istaknuti
U ovoj mreži također možete označiti konačni vrh, a rezultat označavanja bit će isti. Promjenom protoka dobivamo mrežu u kojoj je nemoguće označiti krajnji vrh, pa je protok u njoj najveći i jednak 10.
PRIMJER 3.16.
8 2 1
Na određenoj prometnoj mreži pronađen je nepotpun protok
Označimo mrežu i povećajmo protok u njoj prema algoritmu. Dobivamo
U ovoj mreži također možete označiti konačni vrh, a rezultat označavanja bit će isti. Promjenom protoka dobivamo mrežu u kojoj je nemoguće označiti krajnji vrh, pa je protok u njoj najveći i jednak 6.
odjeljak IV. DINAMIČKO PROGRAMIRANJE.
Dinamičko programiranje koristi se za pronalaženje optimalnih višefaznih rješenja. Na primjer, dugoročno planiranje zamjene opreme; aktivnost industrije tijekom niza godina. Koristi se načelom optimalnosti, prema kojem svako novo parcijalno rješenje mora biti optimalno u odnosu na postignuto stanje.
Bolje je više puta riješiti jedan jednostavan problem nego jednom riješiti težak.
PROBLEM 1. O najpovoljnijem putu između dviju točaka.
Potrebno je izgraditi put koji povezuje dvije točke A i B, od kojih druga leži sjeveroistočno od prve. Radi jednostavnosti, recimo da se postavljanje staze sastoji od niza koraka, a na svakom koraku se možemo kretati ili prema sjeveru ili prema istoku. Tada je svaka staza stepenasto izlomljena linija čiji su segmenti paralelni s jednom od koordinatnih osi. Troškovi izgradnje svake od ovih dionica su poznati.
PRIMJER 4.1. Pronađite minimalni put od A do B.
Zadnji korak je postizanje T.V. Prije posljednjeg koraka mogli bismo biti na točkama odakle bismo mogli doći do TV-a u jednom koraku. Postoje dvije takve točke (sustav može biti u jednom od dva stanja). Za svakoga od njih postoji samo jedna mogućnost da dosegnu t.V: za jednog - pomakni se na istok; za drugu - na sjever. Zapišimo troškove 4 i 3 u svakom slučaju.
4
Optimizirajmo sada pretposljednji korak. Nakon prethodnog koraka mogli bismo završiti u jednoj od tri točke: C 1, C 2, C 3.
Za točku C 1 postoji samo jedna kontrola (označimo je strelicom) - pomakni se na istok, a troškovi će biti 2 (u ovom koraku) + 4 (u sljedećem koraku) = 6. Slično, za stavku C 3 troškovi će biti 2+3=5. Za t.C 2 postoje dvije kontrole: idi na istok ili na sjever. U prvom slučaju troškovi će biti 3+3=6, au drugom slučaju – 1+4=5. To znači da je uvjetna optimalna kontrola ići na sjever. Označimo ga strelicom i unesemo pripadajuće troškove.
| |
| |
| |
| ZADATAK 2. O tovaru automobila (o ruksaku). Ima N stavki. Poznata težina a ja i vrijednost φ i svaki predmet. Potreban za punjenje ruksaka koji može držati ≤ težine R , takav skup predmeta koji bi imao najveću vrijednost.
Proces punjenja ruksaka može se podijeliti u N koraka. Na svakom koraku odlučujemo o pitanju: uzeti ovaj predmet ili ga ne uzeti? U svakom koraku postoje samo 2 kontrole: kontrola =1, ako uzmemo ovu stavku; i 0 - ako ga ne uzmemo. Stanje sustava prije sljedećeg koraka karakterizirano je težinom S koja nam još uvijek ostaje na raspolaganju do kraja punog opterećenja nakon što su prethodni koraci završeni (neke stavke su već učitane), tj. količina slobodnog prostora u ruksaku. ALGORITAM. 1. Krenimo od posljednjeg koraka. Napravimo različite pretpostavke o slobodnom prostoru u ruksaku: S=0,1,…R. Zadnju stvar stavimo u ruksak ako ima dovoljno mjesta za pohranu. 2. U svakom prethodnom koraku, za sva moguća stanja S, razmatramo 2 opcije: uzeti ili ne uzeti objekt. Nađimo dobitak u svakom slučaju kao zbroj dobitaka na trenutnom koraku i na sljedećem već optimiziranom koraku. Rezultate ćemo unijeti u pomoćnu tablicu. 3. U prvom koraku razmatramo samo jedino moguće stanje S=R. 4. Nađimo rješenje "kretanjem unazad", tj. Preuzimajući optimalnu kontrolu u prvom koraku, mijenjamo stanje sustava u drugom koraku: S=R– x 1 a 1 i odabrati optimalnu kontrolu x 2 za ovo stanje. itd. PRIMJER 4.2. Početni podaci
Glavni stol
Pomoćni stol.
Odgovor: x 4 =0; x 3 =1; x 2 =0; x 1 =1; Š=15 ZADATAK 3. O raspodjeli resursa. Postoji N poduzeća P 1, P 2,… P N, od kojih svako ostvaruje prihod φ k (x) ako mu se dodijeli resurs u iznosu x. Potrebno je raspodijeliti resurs raspoloživ u količini A između objekata tako da ukupni prihod bude maksimalan. Neka je x k količina resursa dodijeljena k-tom poduzeću. Tada se problem koji se razmatra svodi na konvencionalni problem nelinearnog programiranja.
Formulirajmo problem kao problem dinamičkog programiranja. Za prvi korak uzet ćemo ulaganje sredstava u poduzeće P 1, za drugi - u P 2 itd. Upravljani sustav u ovom slučaju su sredstva koja se distribuiraju. Stanje sustava prije svakog koraka karakterizira jedan parametar - raspoloživa zaliha još neuloženih sredstava. U ovom problemu, korak kontrole su sredstva dodijeljena poduzećima. Potrebno je pronaći optimalnu kontrolu (x 1, x 2,...x N), pri kojoj je ukupni prihod maksimalan: | 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 |
Odgovor: x 1 =1; x 3 =0; x 3 =4; W=3,5
GENERALIZIRANI ALGORITAM
1. Opišite sustav. Odnosno, saznajte koji parametri karakteriziraju stanje kontroliranog sustava prije svakog koraka. Važno je biti u stanju ispravno i "skromno" postaviti zadatak, bez preopterećenja nepotrebnim detaljima, pojednostavljujući opis kontroliranog sustava što je više moguće.
2. Podijelite operaciju u korake (faze). Ovdje se moraju uzeti u obzir sva razumna ograničenja nametnuta menadžmentu. Korak mora biti dovoljno mali kako bi postupak optimizacije kontrole koraka bio prilično jednostavan; a korak, pritom, ne smije biti premali kako se ne bi radili nepotrebni izračuni koji kompliciraju postupak traženja optimalnog rješenja, ali ne dovode do značajne promjene optimuma funkcije cilja.
3. Pronađite skup kontrola koraka x i za svaki korak i ograničenja koja su im nametnuta.
4. Odrediti koliki dobitak donosi upravljanje x i na i-koraku, ako je prije toga sustav bio u stanju S, tj. zapiši funkcije isplate:
w i =f i (S, x i)
5. Odrediti kako se mijenja stanje sustava pod utjecajem upravljanja x i na prvom koraku, tj. napisati funkcije promjene stanja.
S / =φ i (S, x i)
6. Zapišite glavnu rekurentnu jednadžbu dinamičkog programiranja, izražavajući uvjetno optimalno pojačanje kroz već poznatu funkciju
W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))
7. Provedite uvjetnu optimizaciju zadnjeg koraka, donoseći razne pretpostavke o tome kako je pretposljednji korak završio, i za svaku od tih pretpostavki pronađite uvjetnu (odabranu na temelju uvjeta da je korak završio s nečim) optimalnu kontrolu na zadnjem koraku.
W m (S) = max (f m (S, x m))
8. Izvršite uvjetnu optimizaciju, počevši od pretposljednjeg koraka i završavajući s prvim korakom (natrag).
9. Izvršite bezuvjetnu optimizaciju upravljanja, „čitajući“ odgovarajuće preporuke u svakom koraku: uzmite pronađeno optimalno upravljanje u prvom koraku i promijenite stanje sustava, pronađite optimalno upravljanje za pronađeno stanje u drugom koraku itd. do posljednjeg koraka.
NAČELO OPTIMALNOSTI. Bez obzira na stanje sustava prije sljedećeg koraka, potrebno je odabrati upravljanje u ovom koraku tako da dobitak u ovom koraku plus optimalni dobitak u svim sljedećim koracima bude maksimalan.
Načelo dinamičkog programiranja ne podrazumijeva da se svaki korak optimizira zasebno, neovisno o drugima. Koja je svrha odabira kontrole čija je učinkovitost maksimalna u jednom određenom koraku, ako će nas taj korak lišiti mogućnosti da dobro pobijedimo u sljedećim koracima?
U praksi ima slučajeva da se operacija mora planirati na neodređeno dugo vrijeme. Model za takav slučaj je kontrolirani proces u beskonačnim koracima, gdje su svi koraci jednaki. Ovdje pobjednička funkcija i funkcija promjene stanja ne ovise o broju koraka.
Odjeljak V. SIMULACIONO MODELIRANJE
Ekstremni slučaj: ako je sva matrica iste boje - odgovor je 0.Dodajmo fiktivni izvor i odvod. Od izvora do svih bijelih vrhova povlačimo rubove s težinom B (trošak njihovog ponovnog bojanja u crno). Od crnih vrhova do odvoda povlačimo rubove s težinom W (trošak ponovnog bojanja u bijelo). A između svih susjednih vrhova (bilo da su iste ili različite boje) postavljamo brid težine G (siva linija). Vrijednost maksimalnog protoka bit će odgovor na problem.
Izvor: Sveukrajinska školska olimpijada iz informatike, 2007., 1. dan
Riješenje
Sve što trebamo je podijeliti svaki vrh na dva, a između njih staviti brid s težinom jednakom ograničenju kapaciteta tog vrhaRiješenje
U klasičnom problemu minimalnog reza potrebno je ukloniti rubove. Nema problema! Podijelimo vrhove na 2 i stavimo brid između njih s težinom 1. Tada je odgovor na problem pronalaženje minimalnog rezanja u grafu (što je maksimalni protok).Izvor: Harkovska zimska škola programiranja, 2009., 3. dan
Nakon pomicanja kroz automat od i do j duž ruba k, brišu se svi prijelazi od i duž ruba k, kao i svi prijelazi prema j duž ruba k. Trebate ispisati broj puteva od A do B duž takvog automata.
Riješenje
Problem se svodi na pronalaženje maksimalnog broja staza bez više od jednog ruba iste boje koji dolazi iz jednog vrha. Svedimo problem na pronalaženje maksimalnog protoka. Za svaki vrh, kreirat ćemo k+1 vrhova u ponovno izgrađenoj mreži. Prvi vrh će biti ulaz, ostali vrhovi će predstavljati boje. Iz ulaznog vrha povlačimo brid kapaciteta 1 do svakog od k vrhova koji odgovaraju boji. Od vrhova koji odgovaraju boji i povlačimo sve bridove boje i do ulaza krajeva bridova. Pronalaženjem maksimalnog protoka u takvoj mreži dobivamo maksimalan broj staza koje zadovoljavaju traženo svojstvo.Riješenje
Izgradimo mrežu. Kreirajmo jedan vrh za svaku vrstu novčića. Ovi vrhovi će odgovarati vašim novčićima. Moramo sakupiti što više jedinstvenih novčića, pa povucimo rub kapaciteta 1 do umivaonika iz svakog takvog vrha. Na vrhovima koji odgovaraju novčićima koje inicijalno imate, nacrtat ćemo rub čiji je kapacitet jednak broju takvih novčića koje imate.Za svakog člana kluba (osim za 1, odnosno tebe) napravit ćemo jedan vertex. Ovaj vrh može prihvatiti najviše jedan novčić koji nema i dati
najviše k-1 novčića, od kojih ima k (k > 1). Naravno, član kluba daje jedan novčić u zamjenu za primljeni.
Dakle, svakom takvom vrhu potrebno je nacrtati rub kapaciteta 1 od vrhova koji odgovaraju novčićima koje ovaj član kluba nema. I iz ovih vrhova trebate povući rubove kapaciteta k i - 1 do vrha i, koji odgovaraju novčićima kojih član kluba ima više od jednog.
Izgrađena mreža odražava procese razmjene u klubu. Maksimalni protok u takvoj mreži bit će jednak maksimalnom broju novčića koje možete prikupiti.
Izvor: Harkovska zimska škola programiranja, 2009., 4. dan
Dat je opis rashladnog sustava. Potrebno je saznati kako se tekućina može provesti kroz cijevi tako da su ispunjeni svi navedeni uvjeti.
Riješenje
Ovo je problem pronalaženja cirkulacije u mreži s danim nižim ograničenjima na rubovima. Ako protok mora proći duž ruba (u, v) u segmentu, tada će obnovljena mreža imati tri ruba (od, do, težina): (u, v, r - l), (S, v, l) , (u, T, l). S, T - dodatno uvedeni odvod i izvor, redom. Zapravo, propuštamo potrebni minimalni protok duž ruba, a zatim ga balansiramo tako da dobijemo cirkulaciju.Riješite problem pronalaženja maksimalnog protoka u transportnoj mreži pomoću Ford-Fulkersonovog algoritma i konstruirajte dionicu S mreže.
Početni podaci:
Dana je mreža S(X,U)
- izvor mreže; - mrežni odvod, gdje je ∈X; ∈X.
Vrijednosti kapaciteta luka navedene su u smjeru orijentacije luka: od indeksa i do indeksa 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. Postavite nulti protok na mreži (na svim lukovima vrijednost protoka je 0). Protok nula je početni dopušteni protok na mreži. Vrijednost protoka na svakom luku bit će naznačena izvan zagrada kapaciteta luka.). Vrijednost protoka jednaka "0" nije navedena.
2. Odaberite (proizvoljno) stazu na mreži koja vodi od vrha x0 do vrha x7:
X0-X1-X4-X6-X7
3. Pronađite 
i povećajte protok za ovaj iznos. Rub X1-X4 označen je kao razmatran. 
4. Odaberite drugi put, na primjer: X0-X2-X5-X7, pronađi 
i povećajte protok za ovaj iznos. Rub X0-X2 je označen kao razmatran. 
5. Odaberite drugi put, na primjer: X0-X3-X2-X5-X7, pronađite i povećajte protok za ovaj iznos. Rub X3-X2 označen je kao razmatran. 
6. Nema više puta od X0 do X7, zbrojimo povećanje protoka: 25+10+20=55.
Zaključak: maksimalni protok je 55.
2) Konstruirajte dionicu mreže S.
Postupak "označavanja vrhova".
Početno stanje: svi vrhovi su neoznačeni.
Vrhu X0 dodijeljena je oznaka. Svim vrhovima za koje luk nije zasićen dodjeljuju se oznake (crveni kružići) 
Definiramo minimalne presječene lukove: to su lukovi čiji su počeci u označenim vrhovima, a krajevi u neoznačenim vrhovima.
Ovo su lukovi:
Dakle, minimalni rez ove mreže 
Izračun maksimalne vrijednosti protoka
Pri planiranju racionalne distribucije proizvoda u distributivnoj mreži potrebno je uskladiti kapacitet kanala s potrebama kupaca i kapacitetom proizvodnog pogona. Ova klasa problema rješava se pronalaženjem maksimalnog protoka.
Razmotrimo distribucijsku mrežu (sl. 4.21), u kojoj su točke 0 (ulaz, na primjer, proizvođačko skladište gotovih proizvoda) i P (izlaz, distribucijski centri, skladišta veleprodajnih i maloprodajnih organizacija, potrošač) i svaki luk (segment) spojne točke ja I j, pridružen je broj dij > 0, tzv propusnost lukovi. Vrijednost protoka karakterizira najveću dopuštenu količinu protoka materijala koji može proći duž odgovarajućeg luka po jedinici vremena.
Riža. 4.21.
Količina proizvoda koja prolazi duž luka od ja prije j , to ćemo nazvati protok duž luka ( ja ,j ) i označeno sa . Očito je da
Ako uzmemo u obzir da cjelokupni tok materijala koji ulazi u međutočku mreže mora iz nje u potpunosti izaći, dobivamo
Iz prirodnog zahtjeva jednakosti tokova na ulazu i izlazu imamo
Vrijednost Z ćemo nazvati vrijednošću protoka u mreži i postaviti problem maksimiziranja Z podložno gornjim uvjetima.
Pronalaženje maksimalnog protoka svodi se na pronalaženje propusnosti minimalnog rezanja.
Razmotrimo univerzalni algoritam pretraživanja u obliku matrice.
Početna faza algoritma sastoji se od konstruiranja matrice D 0, u koje se unose vrijednosti propusnosti (za neorijentirani luk uzimamo simetrične vrijednosti elemenata matrice).
Glavni koraci algoritma su pronaći određeni put i ispraviti tok duž tog puta.
Prilikom pronalaženja puta koristimo se postupkom označavanja. Označavamo simbolom * nulti red i stupac matrice (mrežni ulaz). U 0. retku tražimo , označimo odgovarajuće stupce indeksima
i premjestite oznake stupaca u retke. Zatim uzmemo i-ti označeni redak, tražimo neoznačeni stupac u njemu pomoću , s kojim spajamo oznake indeksa
Oznake stupaca prenosimo u retke i nastavljamo taj postupak sve dok ne označimo n-ti stupac.
Zatim pomoću indeksa pronalazimo put koji je doveo do η-tog vrha pomoću indeksa i smanjujemo kapacitet lukova puta (elemenata matrice) za V n i za isti iznos povećajte simetrične elemente.
Ovaj postupak se nastavlja do označavanja n -vrhovi neće postati nemogući.
Maksimalni tok se može pronaći oduzimanjem od izvorne matrice D 0, dobiveno nakon gornje korekcije matrice kapaciteta:
Primjer 4.4
Proizvodnja se nalazi u Moskvi. Za distribuciju proizvoda tvrtka privlači posrednike koji rade s tvrtkom kroz distribucijske centre na različitim razinama. U europskom dijelu Rusije postoji veleprodajno poduzeće 1, koje servisira središnji distribucijski centar. Veleprodajno poduzeće 2 djeluje u bliskom inozemstvu (Ukrajina, Bjelorusija) i servisira ga regionalni distribucijski centar. Tvrtka ima svoje klijente na lokalnom tržištu (Moskva i Moskovska regija) - trgovce na malo koji proizvode dobivaju iz gradskog distribucijskog centra. Regionalni i gradski distributivni centri obnavljaju se iz središnjeg distributivnog centra.
Istaknimo dio distribucijske mreže:
- skladište gotovih proizvoda proizvodnog poduzeća;
- središnji distribucijski centar;
- regionalni distribucijski centar;
- gradski distribucijski centar;
- dva veleprodajna poduzeća;
- maloprodajno mjesto u vlasništvu tvrtke;
- potrošači.
Riža. 4.22.
Označimo svaku kariku distribucijske mreže brojem, a kapacitet stavimo iznad lukova. Propusni kapacitet, ovisno o vrsti veze, može se izraziti obujmom proizvodnog kapaciteta, planiranom potrebom (potražnjom) potrošača i kapacitetom tržišta.
Grafikon distribucijske mreže proizvoda prikazan je na sl. 4.23. Izgradimo matricu D 0, u koje unosimo vrijednosti propusnih kapaciteta poveznica distribucijske mreže (slika 4.24).
Riža. 4.23.
Riža. 4.24.
Iz nultog reda označavamo vrhove (redove-stupce) 1, 2 i 3 indeksima μ = 0 i V, jednako 30,10 i 10.
Iz označene crte 1 označite vrhove 4 i 5 indeksima μ = 1 i V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Od crte 3 označavamo vrh 6 i, konačno, od linije 4 – vrh 7 (slika 4.25).
Riža. 4.25.
Vraćajući se duž μ nalazimo put: do vrha 7 od 4, do vrha 4 od 1, do vrha 1 od 0; elementi za podešavanje D 0 po vrijednosti protoka V7 = 15.
Sljedeći korak daje stazu s protokom 5 (Slika 4.26).
Riža. 4.26.
Sljedeći korak daje rezultat prikazan na sl. 4.27.
Riža. 4.27.
Daljnje označavanje nije moguće. Odavde dobivamo matricu maksimalnog protoka (Sl. 4.28).
Riža. 4.28.
Kao rezultat primjene algoritma za pronalaženje maksimalnog protoka u mreži, rezultati prikazani na sl. 4.29. Parovi brojeva u zagradama prikazani na lukovima grafikona označavaju maksimalnu propusnost luka i preporučenu količinu robe koja se isporučuje mreži.
Algoritam za izračun maksimalnog protoka u mrežama
KORAK 1. Početni zadaci. Trenutna vrijednost A t Maksimalni protok u mreži ima vrijednost 0. KORAK 2. Odabir neovisnih ruta u mreži i određivanje tokova u njima. Od cjelokupnog skupa mogućih ruta u mreži od izvora do ponora odabiremo neovisne rute M 1 , … , M k, koji nema zajedničkih vrhova osim početnog (izvor v i) i završni (odvod v s). Za svaku odabranu rutu M i(1£ ja£ k) odrediti maksimalni protok A(M i).KORAK 3. Korekcija trenutne vrijednosti maksimalnog protoka u mreži. Dodajemo one pronađene na KORAK 2 vrijednosti maksimalnih protoka u neovisnim pravcima M 1 , … , M k na trenutni ukupni maksimalni protok mreže: A t:= A t + A(M 1)+ A(M 2)+…+ A(M k)KORAK 4. Ispravak mreže. Pronađeno na KORAK 2 maksimalne protoke A(M 1), … , A(M k)oduzeto od kapaciteta odgovarajućih mrežnih lukova. Uklanjaju se lukovi s nultim preostalim kapacitetom. KORAK 5. Provjera dovršenosti algoritma. Ako nakon ispravka u mreži nema ruta od izvora v i na zalihu v s, tada je traženi maksimalni protok u mreži jednak pronađenoj struji A:= A t, algoritam se prekida jer je sav mrežni kapacitet potrošen. Ako u prilagođenoj mreži postoje rute od izvora v i na zalihu v s, zatim idite na KORAK 2 i nastavak izvođenja algoritma . Primjer 2. Pomoću ovog algoritma pronađite maksimalni protok u mreži na slici 1.15. Rješenje.KORAK 1. Početni zadaci. A t: = 0.I iteracija. KORAK 2. Odabir neovisnih ruta u mreži i određivanje tokova u njima. Kao M 1 kreni rutom ( v i =V 1 , V 2 , V 5 , v s =V 7), razmatran u primjeru 1. Za njega A(M 1) = 10.
Također je lako izolirati neovisne M 1 ruta M 2 = (v i =V 1 , V 3 , V 6 , v s =V 7). Izračunajmo maksimalnu propusnost za njega i prilagodimo propusnost lukova: 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.
KORAK 3. Korekcija trenutne vrijednosti maksimalnog protoka u mreži. A t:= A t + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.KORAK 4. Ispravak mreže. Pronađeno na KORAK 2 maksimalne protoke A(M 1), A(M 2) u rutama M 1 , M 2 se oduzima od kapaciteta njihovih lukova. Uklanjaju se lukovi s nultim preostalim kapacitetom. Rezultat je dan na slici 1.16 a. a) b) sl. 1.16. Rezultat korekcije mreže nakon ponavljanja ja I IISTEP 5. Provjera dovršenosti algoritma. U prilagođenoj mreži (slika 1.16 a) postoje rute od izvora v i na zalihu v s, Na primjer M 3 = (v i =V 1 , V 4 , V 2 , V 5 , v s =V 7). Nastavak izvođenja algoritma .II ponavljanje. KORAK 2. Kao jedina neovisna ruta kojom idemo M 3 = (v i =V 1 , V 4 , V 2 , V 5 , v s =V 7). Za njega:
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.
KORAK 3. A t:= A t + A(M 3) = 40 + 10= 50.KORAK 4. Ispravak mreže. Maksimalni protok A(M 3) oduzmite od lukova rute M 13 . Rezultat je dan na slici 1.16 b.
KORAK 5. Nema preostalih ruta od izvora do ponora u prilagođenoj mreži. A:= A t:= 50, završetak algoritma. Odgovor: maksimalni protok u mreži na slici 1.15 je 50.Ako je u mreži navedeno više izvora, ona se dovršava uvođenjem novog zajedničkog izvora, koji je s izvornim izvorima povezan lukovima neograničenog kapaciteta. Zatim se problem rješava uobičajenim algoritmom. Potrebni tokovi kroz izvorne izvore bit će tokovi duž novododanih lukova koji u njih ulaze iz novog zajedničkog izvora. Učinite isto ako u mreži postoji nekoliko odvoda.
Mrežno planiranje
Svaki zadatak projektiranja ili konstruiranja prilično složenog objekta ( projekt) može se rastaviti na više manjih komponentnih koraka. Vrijeme cijelog projekta ovisi o pravilnom odabiru slijeda ovih koraka.
Cijeli niz radnji za provedbu projekta predstavljen je kao skup događanja I djela. Događaji se nazivaju pojedinačnim fazama projekta. Rad je proces njegovog dovršavanja. Cijeli kompleks događaja i radova potrebnih za dovršetak projekta može se prikazati u obliku dvopolne mreže G =({v i, v z} , V, X), pri čemu:
i sve događanja označen skupom vrhova V, istaknuti među njima početni događaj v i(početak rada) i završni događaj v z(završetak cjelokupnog projekta), definiraju unutarnji vrhovi mreže međudogađaji- faze koje je potrebno dovršiti tijekom provedbe projekta,
b) sve raditi označeni su lukovima koji povezuju parove događaja - vrhova.
Grafički prikaz ove mreže naziva se mrežni dijagram. Da biste naznačili redoslijed radnji, također unesite mrežni dijagram fiktivna djela, koji nisu povezani s izvođenjem bilo kakvih radnji. Odgovarajući radovi označeni su isprekidanim lukovima.
Kao primjer, razmotrite organizaciju neke proizvodnje. Projekt zahtijeva sljedeće radove:
I) marketinško istraživanje, II) predprojektno istraživanje opreme, III) organiziranje prodajne mreže, IV) provođenje reklamne kampanje, V) izrada tehničke specifikacije proizvodne opreme, VI) izrada tehničke dokumentacije za proizvodne prostore i komunikacije, VII) nabava standardne opreme, VIII) projektiranje i izrada nestandardne opreme, IX) izgradnja proizvodnih objekata i ugradnja komunikacija, X) ugradnja standardne opreme, XI) ugradnja nestandardne opreme, XII) puštanje u rad.
Ove ćemo radove u mrežnom dijagramu označiti lukovima s pripadajućim brojevima.
Događaji u ovom projektu bit će sljedeći:
1) početak rada (inicijalni događaj), 2) završetak marketinškog istraživanja, 3) završetak predprojektnog istraživanja, 4) organizacija prodajne mreže, 5) organizacija reklamne kampanje, 6) priprema tehničke specifikacije za proizvodnju opreme, 7) završetak izrade tehničke dokumentacije za proizvodne prostore i komunikacije, 8) završetak nabave standardne opreme, 9) završetak projektiranja i proizvodnje nestandardne opreme, 10) završetak izgradnje proizvodnih pogona i instalacija komunikacija, 11) završetak montaže opreme i puštanje u rad,
12) završetak projekta (završni događaj).
Događajima pridružujemo vrhove s odgovarajućim brojevima. Mrežni raspored za projekt prikazan je na sl. 1.17:
sl.1.17. Raspored mreže projekta
