Dom Obložen jezik Maksimalni protok u online grafu. Metode primjene algoritma za pronalaženje maksimalnog protoka u mreži

Maksimalni protok u online grafu. Metode primjene algoritma za pronalaženje maksimalnog protoka u mreži

Algoritam proračuna maksimalni protok u mrežama

KORAK 1. Početni zadaci. Trenutna vrijednost A t Maksimalnom protoku u mreži se dodeljuje vrednost 0. KORAK 2. Odabir nezavisnih ruta u mreži i određivanje tokova u njima. Iz cjelokupnog skupa mogućih ruta u mreži od izvora do ponora biramo nezavisne rute M 1 , … , M k, nema zajednički vrhovi, osim početnog (izvor v and) i završni (odvod v sa). Za svaku odabranu rutu M i(1£ i£ k) odrediti maksimalni protok A(M i).KORAK 3. Korekcija trenutne vrijednosti maksimalnog protoka u mreži. Dodajemo one koji se nalaze na KORAK 2 vrijednosti maksimalnih protoka u nezavisnim rutama M 1 , … , M k do trenutnog ukupnog maksimalnog protoka mreže: A t:= A t + A(M 1)+ A(M 2)+…+ A(M k)KORAK 4. Korekcija mreže. Pronađeno na KORAK 2 maksimalni protoci A(M 1), … , A(M k) oduzima se od kapaciteta odgovarajućih mrežnih lukova. Lukovi sa nultim preostalim kapacitetom se uklanjaju. KORAK 5. Provjera završetka algoritma. Ako nakon ispravke u mreži nema ruta od izvora v and to stock v sa, tada je traženi maksimalni protok u mreži jednak pronađenoj struji A:= A t, algoritam se prekida jer je sav kapacitet mreže iscrpljen. Ako u prilagođenoj mreži postoje rute iz izvora v and to stock v sa, zatim idite na KORAK 2 i nastavak izvođenja algoritma . Primjer 2. Nađite maksimalni protok u mreži na slici 1.15 koristeći ovaj algoritam. Rješenje. KORAK 1. Početni zadaci. A t: = 0.

I iteracija. KORAK 2. Odabir nezavisnih ruta u mreži i određivanje tokova u njima. As M 1 put ( v i =V 1 , V 2 , V 5 , v sa =V 7), razmatran u primjeru 1. Za njega A(M 1) = 10.

Takođe je lako izolovati nezavisno M 1 ruta M 2 = (v i =V 1 , V 3 , V 6 , v sa =V 7). Izračunajmo maksimalnu propusnost za to 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. Korekcija mreže. Pronađeno na KORAK 2 maksimalni protoci A(M 1), A(M 2) u rutama M 1 , M 2 se oduzima od kapaciteta njihovih lukova. Lukovi sa nultim preostalim kapacitetom se uklanjaju. Rezultat je dat na slici 1.16 a. a) b) Slika 1.16. Rezultat mrežne korekcije nakon iteracija I I IISTEP 5. Provjera završetka algoritma. U prilagođenoj mreži (slika 1.16 a) postoje rute od izvora v and to stock v sa, Na primjer M 3 = (v i =V 1 , V 4 , V 2 , V 5 , v sa =V 7). Nastavak izvršavanja algoritma .

II iteracija. KORAK 2. Kao jedina nezavisna ruta kojom idemo M 3 = (v i =V 1 , V 4 , V 2 , V 5 , v sa =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. Korekcija mreže. Maksimalni protok A(M 3) oduzmite od lukova rute M 13. Rezultat je dat 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, to se završava uvođenjem novog zajedničkog izvora, koji je sa izvornim izvorima povezan lukovima neograničenog kapaciteta. Tada je problem riješen pomoću prema uobičajenom algoritmu. Potrebni tokovi kroz originalne izvore bit će tokovi duž novododatih lukova koji ulaze u njih iz novog zajedničkog izvora. Učinite isto ako u mreži postoji nekoliko odvoda.

Mrežno planiranje

Svaki zadatak projektovanja ili izgradnje prilično složenog objekta ( projekat) može se raščlaniti na nekoliko manjih komponentnih koraka. Od pravi izbor Redoslijed ovih koraka ovisi o vremenu cijelog projekta.

Čitav niz akcija za implementaciju projekta predstavljen je kao skup događaji I radi. Događaji se nazivaju pojedinačnim fazama projekta. Rad je proces njegovog završetka. Čitav kompleks događaja i radova neophodnih za završetak projekta može se predstaviti u obliku dvopolne mreže G =({v i, v z} , V, X), u kojem:

a) sve događaji 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 cijelog projekta), definiraju unutrašnji vrhovi mreže međudogađaji- korake koje je potrebno izvršiti u procesu implementacija projekta,

b) sve rad označeni su lukovima koji povezuju parove događaja - vrhove.

Grafički prikaz ove mreže se zove mrežni dijagram. Da biste naznačili redoslijed radnji, također uđite u mrežni dijagram fiktivni radovi, koji nisu povezani s izvođenjem bilo kakvih radnji. Odgovarajući radovi su označeni isprekidanim lukovima.

Kao primjer, razmotrite organizaciju neke proizvodnje. Projekat zahteva sledeće radove:

I) marketinško istraživanje, II) predprojektno istraživanje opreme, III) organizovanje prodajne mreže, IV) sprovođenje reklamna kampanja, V) razvoj tehničkih specifikacija za proizvodnu opremu, VI) razvoj tehnička dokumentacija za proizvodne prostore i komunikacije, VII) nabavka standardne opreme, VIII) projektovanje i izrada nestandardne opreme, IX) izgradnja proizvodnih prostorija i instalacija komunikacija, X) ugradnja standardne opreme, XI) ugradnja nestandardne opreme , XII) puštanje u rad.

Ove radove na mrežnom dijagramu ćemo označiti lukovima sa odgovarajućim brojevima.

Događaji u ovom projektu će biti sljedeći:

1) početak rada (početni događaj), 2) završetak marketinško istraživanje, 3) završetak predprojektnih studija, 4) organizacija prodajne mreže, 5) organizacija reklamne kampanje, 6) izrada tehničkih specifikacija za proizvodnu opremu, 7) završetak izrade tehničke dokumentacije za proizvodne prostore i komunikacije , 8) završetak nabavke standardne opreme, 9) završetak projektovanja i izrade nestandardne opreme, 10) završetak izgradnje proizvodnih objekata i instalacija komunikacija, 11) završetak montaže opreme i puštanje u rad,

12) završetak projekta (završni događaj).

Događajima povezujemo vrhove sa odgovarajućim brojevima. Mrežni dijagram Realizacija projekta prikazana je na sl. 1.17:



Sl.1.17. Mrežni raspored implementacije projekta

Hamiltonovi ciklusi

Grafikon je dat u obliku matrice, gdje ćelije specificiraju cijenu kretanja između tačaka. Simbol ∞ se postavlja na glavnu dijagonalu kako bi se eliminirao besmisleni put u sebe.

Jer Ako rezultirajuća matrica sadrži stupac bez nula elemenata, tada ćemo pronaći minimalni element u njoj i oduzeti ga od svih elemenata ovog stupca.

A B C D
A
B
C
D

Hajde da saberemo sve oduzete elemente i dobijemo donju granicu ciklusa in= 2+2+3+2+1=10

1.2. Procijenimo sve nulte elemente matrice.

Procjenu nula pogodno je prikazati u tabeli.

A B C D
A
B
C
D

θ=max γ=γ A C =2

1.3. Podijelimo skup puteva na dva podskupa: Q A.C.– putanje koje sadrže luk (AC) i Q A.C.– putanje koje ne sadrže luk (AC). Za drugi podskup donja granica će biti: in / = in + θ =10+2=12.

Da bismo izračunali granicu za prvi podskup, prelazimo na matricu jedan red veličine niže, precrtavajući A-red 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 na donju ivicu petlje. Ovaj iznos u // =10+2=12 i bit će granica za prvi podskup.

1.4. Uporedimo granice svih visećih vrhova i izaberimo vrh sa najmanjom granicom. Ako postoje dva od ovih vrhova, izaberite bilo koji od njih. Ovo je vrh Q A.C., čija je donja granica =12.



Odaberimo maksimum procjena θ=max γ=γ BD =3

u / =12+3=15.

1.6. Sve naredne tačke izvodimo na sličan način kao i prethodne.

Odaberimo maksimum procjena θ=max γ=γ C B =

u / =in+ θ=∞

A
D

Svi redovi i stupci ove matrice sadrže nule. Prema tome, granica ostaje jednaka 12.

ZADATAK. Pronađite vrijednost maksimalnog protoka na transportnoj mreži.

IZJAVA PROBLEMA.

Razmotrite problem transporta na mreži ( I,D,G) sa datim kapacitetima luka c(i,j).

Odaberimo dva fiksna vrha: s- izvor i t– odvod. Stream na mreži s→t nazovimo numeričku funkciju f, definiran na skupu lukova i zadovoljava sljedeće linearne jednačine i nejednakosti:

0≤ f(i,j) ≤c(i,j) za bilo koji (i,j)

Potrebno za maksimiziranje varijable x

Rez L u mreži koja razdvaja vrhove s t nazvan skup lukova

Bilo kako bilo s→t sadrži najmanje jedan isečeni luk.

KRITERIJUMI OPTIMALNOSTI: na realnoj mreži, vrijednost proizvoljnog protoka ne prelazi propusnost reza, a vrijednost maksimalnog protoka jednaka je minimalnoj propusnosti reza.

PRIMJER 3.12.

M 9 K

M 8 K

PRIMJER 3.13.

M 2 K

RJEŠENJE :

Kapacitet izlaznog luka (T,B) je veći od ukupnog kapaciteta lukova koji ulaze u odgovarajući vrh. Da bi mreža postala realna, zamjenjujemo c(T,B)=5.

Pronađimo i izračunajmo vrijednost propusnih kapaciteta svih rezova. (K,V) – (T,V) rez sa minimalnim protokom =6. Dakle, maksimalni protok =6.

Mreža sa više izvora i ponora može se svesti na mrežu sa jednim izvorom i ponorom.

PRIMJER. Neka postoji nekoliko izvora S i ponora T ( transportni problem). Proširimo mrežu dodavanjem dva čvora s*, t* i svih lukova (s*, S) , (T,t*). Definirajmo funkciju kapaciteta postavljanjem

NAČIN POSTAVLJANJA ZNAKOVA.

1. Početni tok f(i,j) = 0.
Dodijelimo oznake vrhovima ove mreže koji će imati oblik (i+, ε) ili
(i - , ε). Označimo izvor (-, ∞), one . ε(s)= ∞.

2. Za bilo koji označeni vrh i odaberite sve neoznačene vrhove j za koje f(i,j) i dodajte im bilješke (i+, ε(j)), Gdje ε(j)=min[ε(i), f(i,j)]. Oni vrhovi koji će ostati neoznačeni, ali za koje f(i,j)>0, pripisati bilješku (i-, ε(j)).

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

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,V)=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
Korak 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
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: MT-MR-MTO

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, tada označavamo (+i) sve neoznačene vrhove do kojih nezasićeni lukovi idu od h i, a indeksom (–i) sve neoznač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 princip 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 svakog od njih postoji jedna opcija da se stigne do TV-a: za jednog - kreći 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.

2 4

ZADATAK 2. O utovaru automobila (o ruksaku).

Postoji N stavki. Poznata težina a i i vrijednost φi svaku stavku. Potreban za punjenje ranca koji može izdržati ≤ težinu R , takav skup predmeta koji bi imao najveću vrijednost.

Proces punjenja ranca 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 sistema prije sljedećeg koraka karakterizira težina S, koja nam i dalje ostaje na raspolaganju do kraja punog opterećenja nakon što su prethodni koraci završeni (neki artikli su već učitani), tj. količina slobodnog prostora u rancu.

ALGORITAM.

1. Počnimo od posljednjeg koraka. Hajde da napravimo različite pretpostavke o slobodnom prostoru u rancu: S=0,1,…R. Stavimo zadnji predmet u ranac ako ima dovoljno prostora za pohranu.

2. U svakom prethodnom koraku, za sva moguća stanja S, razmatramo 2 opcije: uzeti ili ne uzeti objekat. Nađimo dobit u svakom slučaju kao zbir dobitaka u trenutnom koraku i na sljedećem već optimiziranom koraku. Rezultate ćemo unijeti u pomoćnu tabelu.

3. U prvom koraku razmatramo samo jedino moguće stanje S=R.

4. Pronađimo rješenje „kretanjem unazad“, tj. Uzimajući optimalnu kontrolu u prvom koraku, mijenjamo stanje sistema u drugom koraku: S=R– x 1 a 1 i izaberite optimalnu kontrolu x 2 za ovo stanje. itd.

PRIMJER 4.2.

Početni podaci

P1 P2 P3 P4
težina a i
costj i

Glavni sto

S i=4 i=3 i=2 i=1
x 4 W 4 x 3 W 3 x 2 W 2 x 1 W 1

Pomoćni sto.

stanje x A S- A j i (x) W i+1 (S- A) j i (x)+ W i+1 (S- A)
i=3 S=5
S=6
S=7
S=8
S=9
S=10
i=2 S=5
S=6
S=7
S=8
S=9
S=10
i=1 S=10

Odgovor: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15

ZADATAK 3. O raspodjeli resursa.

Postoji N preduzeća P 1, P 2,… P N, od kojih svako ostvaruje prihod φ k (x) ako mu se dodeli resurs u iznosu od x. Potrebno je raspodijeliti raspoloživi resurs u količini A između objekata tako da ukupan prihod bude maksimalan.

Neka je x k količina resursa dodijeljena k-tom preduzeću. Tada se problem koji se razmatra svodi na uobičajeni problem linearno programiranje.

Hajde da formulišemo problem kao problem dinamičkog programiranja.

Za prvi korak ćemo preduzeti ulaganje sredstava u preduzeće P 1, za drugi - u P 2 itd. Upravljani sistem u u ovom slučaju– sredstva koja se distribuiraju. Stanje sistema prije svakog koraka karakteriše jedan parametar - raspoloživa zaliha sredstava koja još nisu uložena. U ovom problemu, korak kontrole su sredstva koja se dodeljuju preduzećima. Potrebno je pronaći optimalnu kontrolu (x 1, x 2,...x N), pri kojoj je ukupan 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

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, za pronađeno stanje pronaći optimalnu kontrolu 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

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 prolazi p_th pronađena putanja od kraja do kraja 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 isti iznos 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

Količina protoka

smjer

(20,0) - (0,20)=(20, - 20)

(30,0) - (0,30)=(30, - 30)

(10,0) - (0,10)=(10, - 10)

(40,0) - (40,0)=(0,0)

(30,0) - (10,20)=(20, - 20)

(10,5) - (0,15)=(10, - 10)

(20,0) - (0,20)=(20, - 20)

(20,0) - (0,20)=(20, - 20)

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 specificirati 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

Polazna tačka

Odredište

Plan transporta

Bandwidth

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), čini odnos ravnoteže za sistem kao celinu („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).

Prilikom planiranja racionalne distribucije proizvoda u distributivnoj mreži potrebno je uskladiti kapacitet kanala sa potrebama kupaca i kapacitetom proizvodnog pogona. Ova klasa problema se rješava pronalaženjem maksimalnog protoka.

Razmotrimo distributivnu mrežu (slika 4.21), u kojoj su tačke 0 (ulaz, na primjer, u skladište gotovih proizvoda proizvođača) i n (izlaz, distributivni centri, skladišta veleprodajnih i maloprodajnih organizacija, potrošači) i svaki luk (segment) spojne tačke i I j, broj dij > 0 je pridružen, pozvan propusnost lukovi. Vrijednost propusnosti karakterizira maksimum dozvoljena količina protok materijala koji može proći duž odgovarajućeg luka u jedinici vremena.

Rice. 4.21.

Količina proizvoda koja prolazi duž luka od i to j , nazvaćemo to protok duž luka ( i ,j ) i označeno sa . Očigledno je da

Ako uzmemo u obzir da ceo materijalni tok koji ulazi u međutačku mreže mora u potpunosti izaći iz nje, dobijamo

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 u skladu s gornjim uvjetima.

Pronalaženje maksimalnog protoka svodi se na pronalaženje propusnosti minimalnog rezanja.

Razmotrimo univerzalni algoritam pretraživanja u matričnom obliku.

Početna faza algoritma sastoji se od konstruisanja matrice D 0, u koje se unose vrijednosti propusnosti (za neorijentirani luk uzimamo simetrične vrijednosti elemenata matrice).

Glavni koraci algoritma su pronalaženje određene putanje i korekcija toka duž ove staze.

Prilikom pronalaženja staze koristimo proces označavanja. Označavamo simbolom * nulti red i stupac matrice (mrežni ulaz). U 0. redu tražimo , označite odgovarajuće stupce indeksima

i premjestite oznake kolona u redove. Zatim uzimamo i-ti označeni red, tražimo neoznačenu kolonu u njemu sa , s kojim povezujemo oznake indeksa

Prenosimo oznake kolona u redove i nastavljamo ovaj proces dok se ne označi n-ti stupac.

onda " obrnuto"pomoću indeksa saznajemo put koji je vodio do η-tog vrha, smanjujemo kapacitet lukova puta (matričnih elemenata) za V n i povećati simetrične elemente za isti iznos.

Ovaj postupak se nastavlja do označavanja n -topovi neće postati nemogući.

Maksimalni fluks se može naći oduzimanjem od originalne matrice D 0, dobijeno nakon gornje korekcije matrice kapaciteta:

Primjer 4.4

Proizvodnja se nalazi u Moskvi. Za distribuciju proizvoda, kompanija privlači posrednike koji rade sa kompanijom preko distributivnih centara na različitim nivoima. U evropskom delu Rusije postoji veleprodajno preduzeće 1, koje opslužuje centralni distributivni centar. Veleprodaja 2 posluje u bliskom inostranstvu (Ukrajina, Bjelorusija) i opslužuje ga regionalni distributivni centar. Kompanija ima svoje klijente na lokalnom tržištu (Moskva i Moskovska regija) - trgovce na malo koji proizvode dobijaju iz gradskog distributivnog centra. Regionalni i gradski distributivni centri obnavljaju se iz centralnog distributivnog centra.

Istaknimo fragment distributivne mreže:

  • skladište gotovih proizvoda proizvodnog preduzeća;
  • centralni distributivni centar;
  • regionalni distributivni centar;
  • gradski distributivni centar;
  • dva veleprodajna preduzeća;
  • maloprodajni objekat u vlasništvu kompanije;
  • potrošači.

Rice. 4.22.

Označimo svaki link distributivne mreže brojem, a kapacitet stavimo iznad lukova. Kapacitet propusnosti, u zavisnosti od vrste veze, može se izraziti u vidu obima proizvodnog kapaciteta, planirane potrebe (tražnje) potrošača i kapaciteta tržišta.

Grafikon mreže distribucije proizvoda prikazan je na Sl. 4.23. Hajde da napravimo matricu D 0, u koje unosimo vrijednosti propusnih kapaciteta veza distributivne mreže (slika 4.24).

Rice. 4.23.

Rice. 4.24.

Iz nultog reda označavamo vrhove (redove-kolone) 1, 2 i 3 indeksima μ = 0 i V, jednako 30,10 i 10.

Iz označene linije 1 označite vrhove 4 i 5 indeksima μ = 1 i V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Iz linije 3 označavamo vrh 6 i, konačno, iz linije 4 – vrh 7 (slika 4.25).

Rice. 4.25.

Vraćajući se duž μ nalazimo put: do temena 7 od 4, do temena 4 od 1, do vrha 1 od 0; elementi za podešavanje D 0 po vrijednosti protoka V7 = 15.

Sljedeći korak daje putanju sa protokom 5 (slika 4.26).

Rice. 4.26.

Sljedeći korak daje rezultat prikazan na sl. 4.27.

Rice. 4.27.

Nije moguće dalje označavanje. Odavde dobijamo matricu maksimalnog protoka (slika 4.28).

Rice. 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 u mrežu.

Zbir protoka kroz upadne lukove v, 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 v V 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 v nije više izvor, već ponor.

Korak 3. Ako u mreži N’ možemo pronaći protok koji nije nula v 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



Novo na sajtu

>

Najpopularniji