Maksimalni protok

Nova tema  Odgovori 
Podelite temu sa drugarima: ZARADITE PRODAJOM SVOJIH RADOVA
 
Ocena teme:
  • 0 Glasova - 0 Prosečno
  • 1
  • 2
  • 3
  • 4
  • 5
Autor Poruka
Vesnica Nije na vezi
Posting Freak
*****

Poruka: 2,567
Pridružen: May 2010
Poruka: #1
Maksimalni protok
Maturski, seminarski i diplomski radovi iz matematike.

Problem protoka transportne mreže odnosi se na način upotrebe mreže ali tako da se dobije maksimalan iznos protoka od datog ulaza mreže do datog izlaza mreže. Ovakvi zadaci se često sreću u realnim transportnim problemima. Na primjer, ako je iz grada a potrebno prebaciti u grad b za određeno vrijeme mrežom željezničkih pruga što je moguće više tereta, dolazimo do tog zadatka. Podrazumijeva se da svaka pruga ima svoju propusnu sposobnost, tj. gornju granicu tereta koji se može po njoj prevesti za odre|eno vrijeme. Teret koji prispije na neku me|ustanicu mora odmah da se prevozi dalje, jer ne dolazi u obzir skladištenje na me|ustanicama. Isto tako, u me|ustanicama se ne smije ukrcavati novi teret za prevoz.

MATEMATIČKI MODEL

Definicije potrebnih pojmova:


Graf G je uređena trojka G = (V(G), E(G), G) ,koja se sastoji od nepraznog skupa V=V(G) ,čiji su elementi vrhovi od G ,skupa E=E(G) disjunktnog sa V(G) ,čiji su elementi ivice od G i funkcije incidencije G ,koja svakoj ivici od G pridružuje neuređeni par (ne nužno različitih) vrhova G. Ako je eE(G) ,a u,vV(G) ,tako da je G (e) = uv ,kažemo da e spaja u i v ,a u i v su krajevi od e. Ivica e s jednim jedinim vrhom u zove se petlja.

Usmjereni graf ili digraf (engl. directed graph ili digraph) D je uređena trojka (V(D), E(D), D) koja se sastoji od nepraznog skupa V(D) vrhova ,skupa A(D) lukova (ili usmjerenih ivica) i funkcije incidencije D ,koja svakom luku a pridružuje neuređeni par (ne nužno različitih) vrhova u,v koje a spaja ,tj. Ako je D (a) = (u,v) ,kažemo da a spaja u sa v ,a u i v su krajevi od a ;u je početni ,a v krajnji vrh od a. Kraće se piše a = (u,v). Preciznije ,luk a = (u,v) je orjentiran od početka vrha u prema krajnjem vrhu v. Svakom digrafu D je pridružen pripadni graf s istim skupom vrhova ,a luku iz D pridružena je ivica s istim krajevima. Digraf se crta kao i pripadni graf s time da se na svakoj ivici grafa nacrta strelica koja ide prema kraju odgovarajuće ivice digrafa.

Instupanj (ulazni stupanj) d- (v) i outstupanj (izlazni stupanj) d+(v) definiše se kao broj lukova u D s krajem ,odnosno početkom v, gdje je v vrh u D.

Transportna mreža (ili mreža,engl.network) N je povezani digraf bez petlji za koji vrijedi:
1) postoji jedinstveni vrh i s instupnjem d- (i) = 0 ,koji se zove izvor ili ulaz mreže
2) postoji jedinstveni vrh p s outstupnjem d+(p) = 0 ,koji se zove ponor ili izlaz mreže
3) svakom luku a = (u,v)A (N) pridružen je realan broj c(a) = c(u,v) 0 ,koji se zove kapacitet od a. Ako ne postoji luk (u,v), stavljamo c(u,v): = 0.

Protok (ili tok, engl. flow) mreže N je funkcija f: A(N) R+ koja svakom luku a = (u,v) pridružuje broj f(a) = f (u,v) tako da vrijedi
f (u,v) c(u,v)
Vrijednost f(a) može se interpretirati kao brzina prevoza (ili količina) artikala u odredište a za protok f.
Uslov (1) zove se ograničenje kapacitetom i znači da količina robe duž a = (u,v) ne može prelaziti kapacitet od a. A uslov (2) je uslov očuvanja i znači da je količina robe pristigla u vrh v jednaka količini robe koja izlazi iz vrha v ,osim za izvor i ponor.
Vrijednost protoka f na mreži N je:
Kažemo da je protok f * maksimalan na mreži N ako ne postoji protok f u N za koji je val ( f ) > val ( f * ).
Presjek (ili rez ,engl. cut) u N je skup oblika R = ( S, ). Kažemo da presjek R separira izvor i od ponora p, ako je iS , p. Kratko kažemo da je takav presjek i - p presjek.

MOGUĆE METODE ZA RJEŠAVANJE

U principu, postoje dvije metode. Jedna se odnosi na planarne mreže i to je metoda Forda i Fulkersona, a druga metoda se odnosi na neplanarne mreže.
Graf je planaran ili smjestiv u ravnini ako se može nacrtati tj. realizirati u ravni tako da se ivice sijeku u vrhovima. Graf koji nije planaran zove se neplanaran.

Spojimo ulaz a i izlaz b transportne mreže novom granom. Ako je dobijeni graf planaran, postupamo na sljedeći način:
Transportnu mrežu predstavljamo crtežom tako da joj se grane ne presjecaju i da se naknadno dodana grana na crtežu nalazi najniže.
Uočavamo elementarni put mreže iz čvora a u čvor b. Iz mreže izbacujemo granu tog puta koja ima najmanju propusnu sposobnost. Istovremeno propusne sposobnosti preostalih grana posmatranog puta umanjujemo za vrijednost propusne sposobnosti izbačene grane. Na taj način dobijemo novu transportnu mrežu na koju ponovo primjenjujemo opisani postupak. Postupak se ponavlja sve dok se ne prekinu svi putevi koji vode iz a u b. Tada se u polaznoj mreži uočavaju putevi koji su u bilo kom trenutku bili najviši. Granama svakog takvog puta se pripisuje propusna sposobnost grane sa minimalnom propusnom sposobnosti iz tog puta. Ukupan protok za svaku granu dobija se kao zbir djelimičnih pritoka,jer jedna grana može da se nalazi u nekoliko “najviših” puteva.

Ako transportna mreža nije planarna algoritam za nalaženje maksimalnog protoka je komplikovaniji mada je u osnovi slična onom koji se odnosi na planarne. U početku se za protok kroz mrežu uzme bilo koji dozvoljeni protok koji se u toku postupka postepeno povečava. Na primjer, može se uzeti da je protok kroz svaku granu jednak 0. Povećavanje protoka se vrši uvijek duž nekih elementarnih puteva od a do b. Sada se elementarni putevi ne mogu zgodno rangirati kao što je to bio slučaj kod planarnih mreža. Stoga se jednim postupkom traži elementaran put iz čvora a u čvor b takav da je za svaku granu tog puta protok manji od kapaciteta grane. Ako takav put postoji protok kroz svaku granu tog puta se povećava za isti iznos tako da se bar za jednu granu puta protok poklopi sa kapacitetom te grane. Ako ne postoji put sa ovom osobinom, protok kroz transportnu mrežu je maksimalan.
Kod ovog algoritma može se desiti da se proces postepenog povećavanja protoka ne okončava za konačno mnogo koraka. Da bi se to izbjeglo uzima se da protok može da ima samo nenegativne cjelobrojne vrijednosti. Ovim se ne sužava praktična primjena teorije transportnih mreža jer se pogodnim izborom jedinice protoka kontinualni problemi mogu dobro aproksimirati odgovarajućim diskretnim modelima.

OPIS ZADANE METODE ( Ford – Fulkerson metode)

Ford-Fulkersonov algoritam za nalaženje maksimalnog protoka mreže:
-Transportnu mrežu predstavljamo crtežom tako da joj se grane ne presijecaju.
-Uočavamo elementaran put mreže iz čvora a u čvor b, koji je na crtežu najviši
-Iz mreže izbacujemo granu tog puta koja ima najmanju propusnu sposobnost.
-Istovremeno propusne sposobnosti preostalih grana posmatranog puta umanjujemo
-za vrijednost propusne sposobnosti izbačene grane.
-Na taj način dobijemo novu transportnu mrežu na koju ponovno primjenjujemo opisani postupak.
-Postupak se ponavlja sve dok se ne prekinu svi putevi koji vode iz a u b.
-Tada se u polaznoj mreži uočavaju putevi koji su u bilo kom trenutku bili najviši.
-Granama svakog takvog puta se pripisuje, kao djelimični protok, propusna
sposobnost grane sa minimalnom propusnom sposobnosti iz tog puta.
-Ukupan protok za svaku granu dobija se kao zbir djelimičnih protoka, jer jedna grana može da se nalazi na nekoliko "najviših" puteva.

Na slici 1. su predstavljene sve etape rješenja jednog problema odre|ivanja maksimalnog protoka.
Neka je skup X čvorova transportne mreže podijeljen na dva disjunktna podskupa X1 i X2 i neka je a X1 i b X2. Skup svih grana koje polaze iz čvorova skupa X1 a završavaju se u čvorovima skupa X2 naziva se presjek transportne mreže. Kapacitet presjeka je jednak zbiru kapaciteta grana koje obrazuju presjek.
Ako se iz mreže udalje grane jednog presjeka, onda se, očigledno, prekidaju svi putevi izme|u ulaza a i izlaza b mreže. Stoga se iz a u b ne može da transportuje više materijala nego što to dopušta kapacitet proizvoljno izabranog presjeka. Maksimalni fluks kroz mrežu je stoga ograničen minimalnim kapacitetom presjeka mreže. U vezi sa ovim problemima navodimo teoremu Forda i Fulkersona koja predstavlja fundamentalan rezulatat u teoriji transportnih mreža.

TEOREMA (max-flow min-cut, L. Ford, D. Fulkerson, 1956).
U transportnoj je mreži vrijednost maksimalnog protoka jednaka kapacitetu minimalnog presjeka.

Ova teorema je dokazana uzimanjem u obzir algoritma za nalaženje maksimalnog fluksa.


PORUČITE RAD NA OVOM LINKU >>> SEMINARSKI
maturski radovi seminarski radovi maturski seminarski maturski rad diplomski seminarski rad diplomski rad lektire maturalna radnja maturalni radovi skripte maturski radovi diplomski radovi izrada radova vesti studenti magistarski maturanti tutorijali referati lektire download citaonica master masteri master rad master radovi radovi seminarske seminarski seminarski rad seminarski radovi kvalitet kvalitetni fakultet fakulteti skola skole skolovanje titula univerzitet magistarski radovi

LAJKUJTE, POZOVITE 5 PRIJATELJA I OSTVARITE POPUST
08:47 PM
Poseti veb stranicu korisnika Pronađi sve korisnikove poruke Citiraj ovu poruku u odgovoru
Nova tema  Odgovori 


Skoči na forum: