Maksimalni protok mreže. Algoritam za pronalaženje maksimalnog protoka

Ponavljamo ovu operaciju 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 sa neoznačenim formira minimalni rez.

3. Neka zaliha bude označena (j+, ε(t)), Onda f(j,t) zamijeniti sa f(j,t)+ε(t). Ako je zaliha označena (j-, ε(t)), To f(j,t) zamijeniti sa f(j,t)-ε(t). Idemo na vrh j. Ako j ima oznaku (i+, ε(j)), zatim zamjenjujemo f(i,j) on f(i,j)+ε(t), i ako (i-, ε(j)), f(j,i) zamijeniti sa f(j,i)-ε(t). Idemo na vrh i. Ponavljamo ovu operaciju dok ne dođemo do izvora s. Promjena protoka se zaustavlja, sve oznake se brišu i idite na korak 2

PRIMJER 3.14.

M 4 K

ZADATAK. Pronađite najveći protok na mreži

ALGORITAM

Označimo vrh s= x 0 . Svi ostali su x i.

Faza 1.

1. Odaberite bilo koju putanju čiji lukovi nisu zasićeni.

2. Povećavamo količinu protoka duž ove staze za jedan sve dok u njoj ne bude zasićenog luka.

Nastavljamo proces povećanja protoka dok se ne izgradi puni protok, tj. bilo koja putanja će sadržavati barem jedan zasićeni luk.

Faza 2.

2. Ako je h i već označeni vrh, onda označavamo (+i) sve neoznačene vrhove do kojih nezasićeni lukovi idu od h i, a indeksom (–i) sve neobilježene vrhove iz kojih idu lukovi s protokom koji nije nula 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 if, kada se krećemo od s To t orijentacija luka se poklapa sa smjerom kretanja i smanjuje se za jedan ako luk ima suprotnu orijentaciju. Idemo na korak 1.

4. Kada je vrh t nemoguće je označiti da je proces prekinut i rezultirajući tok je najveći tok mreže.

NAPOMENA. Možete ići na fazu 2 bez završetka prve faze (vidi primjer 3.16).

PRIMJER 3.15.

9

RJEŠENJE:

Na datoj transportnoj mreži je pronađen potpuni protok. Zasićeni lukovi su istaknuti

U ovoj mreži možete označiti i konačni vrh, a rezultat označavanja će biti isti. Promjenom toka dobijamo mrežu u kojoj je nemoguće označiti konačni vrh, pa je tok u njoj najveći i jednak 10.

PRIMJER 3.16.

8 2 1

Na datoj transportnoj mreži pronađen je nepotpun tok

Označimo mrežu i povećamo protok u njoj prema algoritmu. Dobili smo

U ovoj mreži možete označiti i konačni vrh, a rezultat označavanja će biti isti. Promjenom toka dobijamo mrežu u kojoj je nemoguće označiti konačni vrh, pa je tok u njoj najveći i jednak 6.

Odjeljak IV. DINAMIČKO PROGRAMIRANJE.

Dinamičko programiranje se koristi za pronalaženje optimalnih višestepenih rješenja. Na primjer, dugoročno planiranje zamjene opreme; aktivnosti industrije tokom niza godina. Koristi se principom optimalnosti, prema kojem svako novo parcijalno rješenje mora biti optimalno u odnosu na postignuto stanje.

Bolje je riješiti jedan više puta jednostavan zadatak nego jednom složeno.

PROBLEM 1. O najpovoljnijoj ruti između dvije tačke.

Potrebno je izgraditi stazu koja spaja dvije tač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 možemo se kretati bilo na sjever ili na istok. Tada je bilo koja putanja stepenasta izlomljena linija, čiji su segmenti paralelni s jednom od koordinatnih osa. Troškovi izgradnje svake od ovih dionica su poznati.

PRIMJER 4.1. Pronađite minimalni put od A do B.

Posljednji korak je postizanje T.V. Prije posljednjeg koraka, mogli bismo biti na mjestima odakle bismo u jednom koraku mogli doći do TV-a. Postoje dvije takve tačke (sistem može biti u jednom od dva stanja). Za svaku od njih postoji samo jedna opcija da dođete do TV-a: za jednog - krećite se na istok; za drugu - na sjever. Napišimo troškove 4 i 3 u svakom slučaju.

4

Hajdemo sada optimizirati pretposljednji korak. Nakon prethodnog koraka, mogli bismo završiti u jednoj od tri tačke: C 1, C 2, C 3.

Za tačku C 1 postoji samo jedna kontrola (označimo je strelicom) - pomaknite 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: ići 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 uslovna optimalna kontrola ići na sjever. Označimo ga strelicom i unesemo odgovarajuće troškove.

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

GENERALIZOVANI ALGORITAM

1. Opišite sistem. Odnosno, saznajte koji parametri karakteriziraju stanje kontroliranog sistema prije svakog koraka. Važno je biti u stanju pravilno i „skromno“ postaviti zadatak, a da ga ne opterećujete nepotrebnim detaljima, pojednostavljujući što je više moguće opis kontrolisanog sistema.

2. Podijelite operaciju na korake (etape). Ovdje se moraju uzeti u obzir sva razumna ograničenja nametnuta menadžmentu. Korak mora biti dovoljno mali tako da je postupak optimizacije kontrole koraka prilično jednostavan; a korak, pritom, ne bi trebao biti premali kako se ne bi radili nepotrebni proračuni koji otežavaju proceduru pronalaženja optimalnog rješenja, ali ne dovode do značajnije promjene optimalnog ciljna funkcija.

3. Saznajte skup kontrola koraka x i za svaki korak i ograničenja koja su im nametnuta.

4. Odrediti kakvo pojačanje donosi kontrola x i na i-korak, ako je prije toga sistem bio u stanju S, tj. zapišite funkcije isplate:

w i =f i (S, x i)

5. Odrediti kako se stanje sistema mijenja pod utjecajem kontrole x i on 1. korak, tj. pisati funkcije promjene stanja.

S / =φ i (S, x i)

6. Zapišite glavnu rekurentnu jednačinu 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. Proizvodi uslovna optimizacija posljednji korak, praveći različite pretpostavke o tome kako je pretposljednji korak završio, i za svaku od ovih pretpostavki pronađite uslovnu (odabranu na osnovu uvjeta da je korak završio nečim) optimalnu kontrolu u posljednjem koraku.

W m (S)= max(f m (S, x m))

8. Izvršite uslovnu optimizaciju, počevši od pretposljednjeg koraka i završavajući s prvim korakom (povratak nazad).

9. Proizvodi bezuslovna optimizacija kontrola, "čitanje" odgovarajućih preporuka u svakom koraku: uzeti pronađenu optimalnu kontrolu u prvom koraku i promijeniti stanje sistema, pronaći optimalnu kontrolu za pronađeno stanje u drugom koraku itd. do poslednjeg koraka.

PRINCIP OPTIMALNOSTI. Bez obzira na stanje sistema prije sljedećeg koraka, potrebno je izabrati kontrolu na ovom koraku tako da pojačanje u ovom koraku plus optimalno pojačanje u svim narednim koracima bude maksimalno.

Princip dinamičkog programiranja ne podrazumeva da se svaki korak optimizuje zasebno, nezavisno od drugih. Koja je svrha biranja kontrole čija je efektivnost maksimalna u jednom konkretnom koraku, ako će nam ovaj korak uskratiti priliku da dobro pobijedimo u narednim koracima?

U praksi postoje slučajevi kada se operacija mora planirati na neograničeno dugo vremensko razdoblje. Model za takav slučaj je beskonačno kontrolirani proces, gdje su svi koraci jednaki. Ovdje dobitna funkcija i funkcija promjene stanja ne zavise od broja koraka.

Odjeljak V. SIMULACIJSKO MODELIRANJE

Ovaj priručnik je namijenjen studentima koji pohađaju predmete iz diskretne matematike i/ili teorije grafova.

Uz njegovu pomoć ćete savladati temu "Maksimalni protok i minimalni rez u mreži."

• Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru.=|Ako imate MATLAB, idite na ovu stranicu: tamo imate priliku da intervenišete u skripti (programu) proračuna. Ovdje je problem maksimalnog protoka u mreži riješen svođenjem na problem linearnog programiranja. Hajde da uvedemo sljedeću notaciju:
• n=|V| − veličina grafa (broj vrhova);
• m E Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru.× n| − kardinalnost grafa (broj ivica); A− matrica incidencije mrežnog digrafa veličine i; svaki njen element a ik=1 ako od A-vrh izlazi i k a ik-i luk; A=−1, ako je in
• s th vrh ulazi
• t-i luk; I
• =0 u drugim slučajevima; u svakoj koloni takve matrice nalazi se tačno jedan, jedan minus jedan, a ostalo su nule;− broj izvornog vrha mreže; samo lukovi bi trebali izlaziti iz ovog vrha, a bilo koji drugi vrh bi trebao biti dostupan iz izvora; − s m − broj vrha ponora mreže; samo lukovi bi trebali ući u ovaj vrh, a odvod bi trebao biti dostupan iz bilo kojeg drugog vrha;
• =0 u drugim slučajevima; u svakoj koloni takve matrice nalazi se tačno jedan, jedan minus jedan, a ostalo su nule; a − t s m ;
• m treba da sadrži samo jedan, jer iz izvora treba da izlaze samo lukovi; t m -ti red matrice incidencije mrežnog digrafa s; t treba da sadrži samo minus, jer samo lukovi trebaju ući u odvod;
• st − matrica incidencije mrežnog digrafa n sa onima koji su izbačeni iz nje th and th linije; a ik e
• − kolonski vektor dužine − matrica incidencije mrežnog digrafa n sa onima koji su izbačeni iz nje ; u svakom njegovom elementu e k a ikće biti veličina protoka u

th arc;

c

c k

• ≥0 postavlja propusnost th and th arc. th and = ; u svakom njegovom elementu Tada se problem maksimalnog protoka mreže može formulirati kao problem linearnog programiranja:
• Ukupni protok koji napušta izvor (1) je maksimiziran. Štaviše, na bilo kom srednjem vrhu ulazni tok je jednak izlaznom toku (2), a kapacitet lukova je ograničen (3).
• ako postoje dvije takve komponente, tada odbačeni lukovi daju minimalni rez;
• ako se pojavi više od dvije povezane komponente, tada mrežni digraf ima nekoliko minimalnih rezova (odgovarajući problem linearnog programiranja je degeneriran).

Za degenerisani problem, prvi minimalni rez najbliži izvoru je konstruisan na ovoj stranici.

Da biste pravilno koristili ovu stranicu, vaš pretraživač mora podržavati skripte Java Script. Uključite ih.

Unesite početne podatke u polja za unos ispod. U prvom području trebate (tačnije, možete) unijeti koordinate vrhova da nacrtate digraf mreže. Oni su specificirani u obliku matrice Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru.×2: u prvoj koloni − x te koordinate, u drugom − y-e. Brojevi se mogu specificirati kao cijeli brojevi, sa decimalnim zarezom ili u eksponencijalnom obliku. Odvojite brojeve razmacima. Ukupna količina linije u ovoj oblasti za unos određuju veličinu digrafa Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru.− broj vrhova. Ovi početni podaci (koordinate vrhova) su opcioni: ako nisu specificirani, mrežni digraf će biti nacrtan kao ispravan Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru.-gon, a broj vrhova će biti određen maksimalnim brojem vrha u sljedećem području unosa.

U sljedećem području unosa lijevoj strani− potrebno je popuniti. Definira strukturu mrežnog digrafa. n Svaki luk u digrafu povezuje dva vrha. Brojevi ovih vrhova su specificirani u obliku matrice ×2 na lijevoj strani drugog polja za unos. Na svakoj liniji prvo se specificira 1. vrh (rep, izvor) luka, a zatim, kroz razmak, 2. vrh (vrh, odvod) luka. Ove kolone treba da sadrže Direktno iz ovog priručnika možete izračunati svoj ID, čak i ako nemate MATLAB na svom računaru. prirodni brojevi n od 1 do

Ukupan broj brojeva u svakoj od ovih kolona određuje kardinalnost digrafa − broj lukova. , Izračunaj Neka je zadan usmjereni graf G= u kojem je smjer svakog luka vÎV V označava smjer toka (na primjer, protok automobila), kapacitet svakog luka je jednak t I s d(v). t Na mnogim vrhovima s dva vrha su istaknuta t. Vertex s .

je izvor toka, - odvod. Potrebno je odrediti maksimalni protok koji se može proći iz vrha V Označimo sa x(v)

količina protoka koja se kreće duž luka (6. 1)

v . Očigledno je da 0 £ x(v) £ d(v) , vÎV .

Na svakom vrhuncu)iÎE\(t,s)

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

Za vrh t

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

za vrh s

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

Magnituda Q je veličina toka koji napušta vrh t i ulazi na vrh s.

Treba utvrditi

Q ® max(6.5)

pod ograničenjima (6.1-6.4).

Količine Q, x(v) , vÎV, zadovoljavajući ograničenja (6.1-6.4) nazvaćemo protok u mreži, a ako ona maksimiziraju vrijednost Q, zatim maksimalni protok. Lako je vidjeti da su vrijednosti Q=0, x(v)=0, vÎV, su tok u mreži.

Problem (6.1-6.5) je problem linearnog programiranja i može se riješiti korištenjem algoritama simpleks metode.

Podijelimo skup vrhova E na dva disjunktna ​​dijela E1 i E2 na način da tÎE1, sÎE2. Po rezu V(E1,E2), odvajanje t I s pozvaćemo set V(E1,E2)ÌV tako da za svaki luk v O V(E1,E2) ili h1(v)OE1 I h2(v)OE2, ili h1(v)OE2 I h2(v)OE1.

Hajde da podelimo set V(E1,E2) na dva dela V(E1,E2,+),V(E1,E2,-) kako slijedi:

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

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

Nazvat ćemo propusni kapacitet reza

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

Istina je sljedeće

Teorema 1. (O maksimalnom protoku i minimalnom rezu).

U bilo kojoj mreži, maksimalni protok iz izvora je a to stock s jednak minimalnoj propusnosti Q(E1,E2) među svim rezovima V(E1,E2), razdvajanje vrhova t I s.

Imajte na umu da u maksimalnom protoku

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

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

Neka Q, x(v), vÎV, - neki mrežni tok, sekvenca

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

je lanac koji povezuje vrhove t I s. Postavimo na ovom lancu smjer kretanja od vrha t To s. Arc v(j) iz ovog lanca naziva se prava linija ako se njegov smjer poklapa sa smjerom kretanja od t To s, a inače obrnuto. Ovaj lanac ćemo nazvati staza povećanje protoka, ako je za prave lukove Označimo sa lancima x(v)< d(v) i za obrnuto x(v) > 0. Dodatni protok može biti propušten kroz ovaj krug q od t To s veličina q = min(q1,q2), Gdje q1=min (d(v) -x(v)), minimum se uzima preko svih ravnih lukova lanca, q1=min (x(v)), minimum se preuzima na svim obrnutim lukovima lanca.

Teorema 2.

Protok Q, x(v) , vÎV, je maksimalno ako i samo ako ne postoji način da se poveća protok.

Predloženi algoritam za rješavanje problema maksimalnog protoka u mreži zasniva se na pronalaženju načina za povećanje protoka od t. Vertex s, koji se zauzvrat zasniva na procesu aranžiranja oznaka vrhova. Recimo to

vertex i označeno oznakom q(i)>0, a poznat je i pravi luk v(i), kroz koji je ovaj tok došao, ili je označen sa , ako je neki dodatni tok veličine q(i)>0, a poznat je i obrnuti luk v(i), kroz koji je ovaj tok ušao;

vrh i se gleda ako su svi njegovi susjedni vrhovi označeni.

Ako je vrh s označen, tada je pronađen put koji povećava protok po veličini q, kojim se prolazi ovom stazom. Da bismo opisali algoritam, potreban nam je i niz SPW, koji sadrži brojeve označenih vrhova redom kojim su označeni. C1- broj u nizu SPW razgledani vrh, C2- broj posljednjeg označenog vrha u ovom nizu.

Ideja ovog algoritma je pronaći staze od kraja do kraja s pozitivnim tokovima od izvora do ponora.

Razmotrimo ivicu (i, j) sa (početnim) kapacitetom. Tokom izvršavanja algoritma, delovi ovog kapaciteta se „oduzimaju“ tokovima koji prolaze kroz datu ivicu, kao rezultat toga, svaka ivica će imati preostali kapacitet. Write - preostala propusnost. Mreža u kojoj sve ivice imaju rezidualni kapacitet će se zvati rezidualna.

Za proizvoljni čvor j koji prima tok od čvora i, definiramo oznaku, gdje je vrijednost toka koji teče od čvora j do čvora i. Da bismo pronašli maksimalni protok, izvodimo sljedeće korake.

Za sve ivice postavljamo preostali kapacitet jednak početnom kapacitetu, tj. izjednačimo =. Dodijelimo i označimo čvor 1 oznakom. Pretpostavljamo da je i=1.

Skup čvorova j do kojih možete ići od čvora I duž ivice s pozitivnim preostalim kapacitetom >0 za sve j. Ako izvršimo 3. fazu, u suprotnom idemo na 4.

U nalazimo čvor k takav da. Postavimo i označimo čvor k oznakom. Ako je k=n, nalazi se put od kraja do kraja i idemo na fazu 5, u suprotnom postavljamo i=k i vraćamo se na fazu 2.

Rollback. Ako je i=1, nije moguća putanja od kraja do kraja i idite na 6. Ako, nalazimo označeni čvor r neposredno ispred čvora i i uklanjamo ga iz skupa čvorova koji su susjedni čvoru r. Postavljamo i=r i vraćamo se na fazu 2.

Definicija rezidualne mreže. Označimo skupom čvorova kroz koje p_th pronađeni put od kraja do kraja prolazi od izvornog čvora (čvor 1) do čvora ponora (čvor n).

Preostali kapacitet ivica koje čine put od kraja do kraja smanjuje se za iznos u smjeru protoka i povećava se za istu količinu u suprotnom smjeru.

To. za ivicu (i, j) uključenu u putanju od kraja do kraja, trenutni preostali kapaciteti se mijenjaju:

1) ako tok ide od čvora i do j,

2) ako tok ide od čvora j do i.

a) sa m putanja od kraja do kraja, maksimalni protok je izražen sa

b) Imajući vrijednosti početnog i krajnjeg kapaciteta ruba (i, j), možemo izračunati optimalni protok kroz ovu ivicu na sljedeći način. Hajde da to stavimo. Ako je >0, protok koji prolazi kroz rub (i, j) je jednak. Ako je >0, onda je protok jednak. (slučaj kada je i >0 i >0 nemoguće).

Primjer 1. Pronađite maksimalni protok u mreži Sl. 1

Iteracija 1. =

3) k=3, pošto. Dodjeljujemo i označavamo čvor 3 oznakom. i=3 i vratite se na 2)

5) k=5 i. Čvor 5 označavamo oznakom. Dobijamo prolaz.

6) odredimo putanju od kraja do kraja pomoću oznaka, počevši od čvora 5 i završavajući sa čvorom 1: . I. Izračunavamo preostale kapacitete duž puta:

Iteracija 2.

1) i označite čvor 1 oznakom. i=1

2") (tako da čvor 5 nije uključen u

3") k=4 i označite čvor 4 oznakom. i=4 i vratite se na 2)

2""") (pošto su čvorovi 1 i 3 označeni, oni nisu uključeni u)

3""") k=5 i. Čvor 5 označavamo oznakom. Dobija se putanja od kraja do kraja. Idite na 5)

Iteracija 3.

1) i označite čvor 1 oznakom. i=1

3) k=2 i označite čvor 2 oznakom. i=2 i vratite se na 2)

3") k=3 i. Označite čvor 3 oznakom. i=3 i vratite se na 2)

2") (od) idite na 4)

4) oznaka čvora 3 pokazuje broj prethodnog čvora. U ovoj iteraciji, čvor 3 se u budućnosti ne uzima u obzir; i vratite se na 2)

2""") (budući da je čvor 3 uklonjen sa moguće staze od kraja do kraja)

3""") i. Čvor 5 označavamo oznakom. Dobija se putanja od kraja do kraja. Idite na 5)

5) i. Izračunavamo preostale kapacitete duž puta:

Iteracija 4. U ovoj iteraciji, putanja sa

Iteracija 5. U ovoj iteraciji, putanja sa

Iteracija 6: Nisu moguće nove staze od kraja do kraja jer sve ivice koje potiču iz čvora 1 imaju nulti preostali kapacitet. Idite na 6) da odredite rješenje

6) maksimalni protok u mreži je jednak jedinicama.

Vrijednosti protoka za različite rubove se izračunavaju oduzimanjem najnovijih vrijednosti preostalog kapaciteta od početnih vrijednosti kapaciteta.

Rezultati proračuna: tabela. 1

Grafičko sekvencijalno izvođenje algoritma za pronalaženje maksimalnog protoka (primjer 1)

e) f) Nema prolaznih puteva

Rice.

Početni podaci o transportnom sistemu, na primjer, unutar postrojenja, prikazani na sl. 2, može se odrediti i tabelom (Tablica 2).

Tabela 2. Početni podaci za problem maksimalnog protoka

Očigledno, maksimalni kapacitet transportnog sistema ne prelazi 6, jer se ne može poslati više od 6 jedinica tereta sa početne tačke 0, odnosno 2 jedinice do tačke 1, 3 jedinice do tačke 2 i 1 jedinice do tačke 3 Dalje, potrebno je osigurati da svih 6 jedinica tereta napusti tačku 0 dođe do krajnje tačke 4. Očigledno, 2 jedinice tereta koje su stigle u tačku 1 mogu se direktno poslati u tačku 4. Teret koji je stigao u tačku 2 će. moraju se podijeliti: 2 jedinice se odmah šalju u tačku 4, a 1 jedinica - u međutačku 3 (zbog ograničenog kapaciteta dionice između tačaka 2 i 4). U tačku 3 je dostavljen sljedeći teret: 1 jedinica iz tačke 0 i 1 jedinica iz tačke 3. Šaljemo ih u tačku 4. Dakle, maksimalna propusnost predmetnog transportnog sistema je 6 jedinica tereta. U ovom slučaju se ne koriste unutrašnji dijelovi (grane) između tačaka 1 i 2, kao i između tačaka 1 i 3. Grana između tačaka 1 i 4 nije u potpunosti opterećena - uz nju se šalju 2 jedinice tereta propusnost od 3 jedinice. Rješenje se može predstaviti u obliku tabele (tabela 3)

Tabela 3. Rješavanje problema maksimalnog protoka

Problem linearnog programiranja za maksimizaciju protoka. Hajde da formulišemo problem maksimalnog protoka u terminima linearnog programiranja. Neka je X KM obim transporta od tačke K do tačke M. Prema sl. 2 K = 0,1,2,3, M = 1,2,3,4, a transport je moguć samo do tačke sa većim brojem. To znači da postoji ukupno 9 varijabli X KM, odnosno X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Problem linearnog programiranja ima za cilj maksimiziranje tok ima oblik:

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

Ovdje je F funkcija cilja, uslov (0) opisuje ulazak robe u transportni sistem. Uslovi (1) - (3) postavljaju odnose ravnoteže za čvorove 1-3 sistema. Drugim riječima, za svaki od internih čvorova, dolazni tok robe jednak je odlaznom toku robe se ne akumulira unutar sistema i ne „rađa“ se u njemu. Uslov (4) je uslov za „izlazak“ opterećenja iz sistema. Zajedno sa uslovom (0), on čini odnos ravnoteže za sistem u celini („ulaz“ je jednak „izlazu“). Sljedećih devet nejednakosti postavljaju ograničenja na kapacitet pojedinih „grana“ transportnog sistema. Zatim se ukazuje na nenegativnost obima saobraćaja i funkcije cilja. Jasno je da posljednja nejednakost proizlazi iz oblika funkcije cilja (odnos (0) ili (4)) i nenegativnosti obima saobraćaja. Međutim, posljednja nejednakost nosi nešto opšte informacije- kroz sistem se može proći ili pozitivna količina tereta, ili nula (na primjer, ako postoji kretanje u krugu unutar sistema), ali ne negativna (nema ekonomskog smisla, već formalno matematički model"ne zna" za to).

Zbir protoka kroz upadne lukove Označimo sa, jednak je zbiru protoka kroz lukove koji upadaju w; ovaj zbir se naziva vrijednost fluksa. Nas će prvenstveno zanimati tokovi koji imaju najveću moguću veličinu – tzv. maksimalni tokovi. IN opšti slučaj mreža može imati nekoliko različitih maksimalnih protoka, ali njihove vrijednosti moraju biti iste. (4)

Proučavanje maksimalnih protoka kroz mrežu N = (V,D,a) usko je povezano sa konceptom rezanja, tj. takav skup A lukova digrafa D koji ima svojstvo bilo kojeg jednostavnog lanca Označimo sa. Vertex prolazi kroz luk koji pripada A. Kapacitet reza je zbir kapaciteta lukova koji mu pripadaju. Rezovi koji imaju najmanju moguću propusnost nazivaju se minimalnim rezovima.

Veličina bilo kog protoka ne premašuje kapacitet nijednog rezanja, pa prema tome, veličina bilo kog maksimalnog protoka ne prelazi kapacitet bilo kojeg minimalnog rezanja. Međutim, nije odmah jasno da li su to dvoje zadnji brojevi uvijek jednaki jedni drugima; Ovaj rezultat su dobili američki matematičari Ford i Fulkerson 1955. godine i nazvali ga teorem o maksimalnom protoku i minimalnom rezu.

Teorema (o maksimalnom protoku i minimalnom rezu). U bilo kojoj mreži, veličina svakog maksimalnog protoka jednaka je kapacitetu bilo kojeg minimalnog rezanja.

Teorema o maksimalnom protoku i minimalnom rezu omogućava vam da provjerite da li je dati tok maksimalan ili ne, ali samo za prilično jednostavne mreže. Naravno, u praksi imamo posla sa velikim i složenim mrežama, a generalno je teško jednostavnom selekcijom pronaći maksimalni protok. Hajde da opišemo jedan algoritam za pronalaženje maksimalnog protoka u bilo kojoj mreži sa cjelobrojnim protokom.

Korak 1. Prvo, izaberimo tok koji ima vrijednost različitu od nule (ako takav tok postoji). Na primjer, ako je N mreža prikazana na sl. 29.3, zatim protok prikazan na sl. 29.4. Vrijedi napomenuti da što je veća vrijednost početnog protoka koju smo odabrali, to će sljedeći koraci biti lakši.

Korak 2. Na osnovu N gradimo novu mrežu N’ promjenom smjera toka na suprotan. Preciznije, svaki luk a za koji (a) = 0 ostaje u N' sa svojim prvobitnim kapacitetom, a svaki luk a za koji je , zamijenjen je lukom a kapaciteta i suprotnim lukom kapaciteta (a). Mreža N’ u našem primjeru prikazana je na sl. 29.5. Vertex Označimo sa nije više izvor, već ponor.

Korak 3. Ako u mreži N’ možemo pronaći tok različit od nule Označimo sa c, onda se može dodati originalnom toku i dobiti novi tok veće vrijednosti u N. Sada možete ponoviti korak 2, koristeći novu nit N’ umjesto N’ prilikom konstruiranja mreže. Ponavljanjem ove procedure, na kraju ćemo doći do mreže N' koja ne sadrži tokove koji nisu nula; tada će odgovarajući protok biti maksimalni protok. Na primjer, na sl. 29.5 postoji tok različit od nule u kojem teče kroz lukove ( v,u), (u,z), (z,x), (x,y) I ( y,) jednaki su jedan, a tokovi kroz preostale lukove jednaki su nuli. Dodajući ovaj tok toku na sl. 29.4, dobijamo tok prikazan na Sl. 29.6; ponavljajući korak 2, lako je pokazati da je ovo maksimalni protok.

Korišćena literatura:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) Asanov M.O., Baranski V.A., Rasin V.V. Diskretna matematika: matroidni grafovi, algoritmi

(3) Basaker R., Saati T. Konačni grafovi i mreže.

(4) Wilson R. Uvod u teoriju grafova