Fluxul minim de costuri

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 22 ianuarie 2017; verificările necesită 6 modificări .

Problema fluxului de cost minim este de a găsi cea mai ieftină modalitate de a transfera un flux de o anumită cantitate printr-o rețea de transport .

Definiții

Având în vedere o rețea de transport cu sursă și chiuvetă , unde marginile au capacitate , debit și preț . Costul de redirecționare a fluxului pentru margine este egal cu . Este necesar să găsiți un flux cu o valoare de unități. $G(V,E)$ $s\în V$ $t\in V$ $e\in E$ $c(e)$ $f(e)$ $a(e)$ $e$ $f(e)\cdot a(e)$ $d$

Esența problemei este de a găsi un flux f ( u , v ) care să minimizeze costul total :

\sum _{{u,v\in V}}a(u,v)\cdot f(u,v)

Se aplică următoarele condiții:

Limită de lățime de bandă :	$0\leqslant f(u,v)\leqslant c(u,v)$ . Fluxul nu poate depăși lățimea de bandă.
Antisimetrie :	$\f(u,v)=-f(v,u)$ . Fluxul de la până trebuie să fie opus fluxului de la până la . $u$ $v$ $v$ $u$
Flux de economisire :	$\ \sum _{{w\in V}}f(u,w)=0$ .
Flux necesar :	$\sum _{w\in V}f(s,w)=d$

Relația cu alte sarcini

O alta varianta a acestei probleme este gasirea debitului maxim care are pretul minim dintre cele maxime.

O problemă mai generală este circulația fluxului de cost minim , care poate fi folosit pentru a rezolva această problemă. Setăm limita inferioară pentru toate muchiile egale cu zero și trasăm o margine suplimentară de la chiuvetă la sursă cu o capacitate și o limită inferioară . $t$ $s$ $c(t,s)=d$ $l(t,s)=d$

Este de remarcat că pentru , problema găsirii fluxului minim de cost corespunde problemei găsirii căii celei mai scurte . În cazul în care costul este pentru toate marginile graficului, problema poate fi rezolvată prin algoritmi adaptați pentru găsirea debitului maxim: $d=1$ $a(e)=0$

De îndată ce prima dată, opriți algoritmul. $|f|\geqslant d$
Fie valoarea ultimului complement al fluxului. $p$
Înlocuiți ultimul flux cu un flux cu valoare . $p-(|f|-d)$

Există, de asemenea, o soluție alternativă la problema cu costul limită zero:

Creați un nou vârf sursă . $s'$
Adăugați o margine cu capacitate . $e'=(s',s)$ $c(e')=d$
Astfel debitul maxim va fi limitat . $d$

Hotărâri

Problema fluxului de cost minim poate fi rezolvată folosind programarea liniară .
Găsiți orice flux de o valoare dată, apoi scăpați de toate ciclurile de cost negative din graficul rezidual. Pentru a scăpa de ciclu, trebuie să lăsați maximum posibil să curgă prin el. Ciclurile sunt căutate de algoritmul Bellman-Ford . Pentru a demonstra funcționarea algoritmului, arătăm că fluxul grafic nu este un flux de cost minim atâta timp cât rețeaua reziduală a graficului conține un ciclu negativ . Fie un flux grafic astfel încât și, prin urmare, ambele fluxuri sunt diferite unul de celălalt. Pentru toate marginile notăm și obținem - un flux ciclic. Deoarece este format dintr-un maximum de cicluri , este adevărat: , ceea ce înseamnă că există astfel încât . Pentru a optimiza algoritmul, puteți alege fiecare ciclu de iterație cu costul mediu minim . Pentru a demonstra timpul de rulare al algoritmului, împărțim cursul execuției acestuia în faze, fiecare dintre acestea fiind formată din iterații separate. Fie fluxul către începutul fazei -a. Faza este considerată încheiată atunci când se găsește un flux astfel încât sau , unde . La , algoritmul se termină. Mai mult, fie - valoarea de la începutul primei faze și - valoarea de la începutul fazei --a ( ). Astfel într-adevăr: , și de asemenea . Datorită proprietății de integralitate rezultă că și . Iterațiile pot fi împărțite condiționat în mai multe tipuri: Tip 1 - ciclul conține doar margini cu cost negativ și Tip 2 - ciclul conține cel puțin o margine cu cost pozitiv. La fiecare iterație a primului tip, cel puțin o margine va fi „saturată” și îndepărtată. În acest caz, toate muchiile formate vor avea un cost pozitiv (deoarece au direcția opusă în rețeaua reziduală). Astfel, algoritmul se va termina după cel puțin iterații consecutive de primul tip. Dacă faza conține mai mult de iterații, după iterațiile maxime se va efectua o iterație de al doilea tip. Să arătăm, totuși, că acest lucru este imposibil: Să fie un flux al primei iterații de al doilea tip. Rețineți că într-adevăr , adică fără margini noi cu cost negativ. Fie un ciclu în cu minim și muchii cu cost negativ în : . Din urmează . Astfel . O contradicție - am ajuns deja la sfârșitul fazei, ceea ce înseamnă că nu există iterații de al doilea tip și fiecare fază se termină după iterații de primul tip. Ciclul cu greutatea medie minimă poate fi găsit în . Dovada: Să fie costul celei mai profitabile căi către exact margini, apoi într-adevăr și . Se pare că toate valorile pot fi calculate folosind programarea dinamică . Lema: Valoarea ciclului cu costul mediu minim este . Fie ciclul cu costul mediu minim. Dacă creșteți costul tuturor marginilor cu , atunci rămâne un ciclu cu costul mediu minim, dar valoarea ciclului crește cu . astfel este posibil să crească toate costurile marginale astfel încât . Să arătăm că : Alegeți orice vârf și cale care se termină la și având cost . trebuie să conțină o buclă . Fie o cale care nu conține un ciclu și are lungime . Apoi există margini în ciclu. Deoarece este adevărat și pentru fiecare vârf există astfel încât . Să arătăm că : Pentru a face acest lucru, demonstrăm că există un vârf pentru care este adevărat pentru toți . Fie vârful ciclului cu costul mediu minim , fie cea mai scurtă cale care se termină cu și care nu conține un ciclu. fie numărul de vârfuri în . Introducem, de asemenea, un vârf care se află la distanța vârfurilor de la . Să numim calea de la la . Fie o cale de la la , și fie o cale de lungime minimă de la sursa graficului la . Atunci este adevărat: , și tot din ele rezultă că . Calea are un cost de 0, deoarece . Astfel pentru toată lumea . Ținând cont de lemă, obținem . Timpul de execuție a unor astfel de algoritmi va fi de , deoarece în timpul execuției algoritmului vor trece faze, în fiecare dintre acestea fiind iterații care necesită timp. Pe baza estimării anterioare a timpului se pot face următoarele: . $f$ $G$ $G_f$ $C$ $f^{*}$ $G$ $l(f^{*})<l(f)$ $e\in E$ $f'(e)=f^{*}(e)-f(e)$ $f'$ $f'$ $m'<m$ $f'_{i)$ $(1\leqslant i\leqslant m')$ $l(f')=l(f^{*})-l(f)=\sum _{1\leqslant i\leqslant m'}l(f'_{i})$ $j$ $l(f'_{j})<0$ ${\overline {l}}(C)={\frac {l(C)}{|C|}}={\frac {\sum _{e\in C}l(e)}{| C|}}$ $f$ $i$ $i$ $g$ $\mu (g)\leqslant (1-1/n)\cdot \mu (f)$ $\mu (g)\leqslant 0$ $\mu (f)=-{\overline {l))(C)$ $\mu (g)\leqslant 0$ $\mu_{0}$ $\mu$ $\mu _{i}$ $\mu$ $i$ $1\leqslant i\leqslant T$ $\mu _{i}\leqslant (1-1/n)\cdot \mu _{i-1}\leqslant {\frac {\mu _{i-1}}{e^{1/n }}}$ $\mu _{0}\leqslant L=\sum _{e\in E}|l(e)|$ $\mu _{T-1}\geqslant 1/n$ $T-1\leqslant \log _{e^{1/n}}(nL)={\frac {\ln(nL)}{\ln(e^{1/n}})))= n \ln(nL)$ $T\leqslant n\ln(nL)+1$ $C$ $C$ $m$ $m$ $m-1$ $g$ $\forall e\in E(G_{g}):l(e)\geqslant -\mu (f)$ $C$ $G_{g)$ ${\overline {l}}(C)$ $H$ $C$ $\mu (g)=\sum _{e\in C}{\frac {-l(e)}{|C|}}\leqslant \sum _{e\in H}{\frac {- l(e)}{|C|}}\leqslant |H|\cdot {\frac {\mu (f)}{|C|}}$ $|H|\leqslant |C|-1$ $|H|/|C|\leqslant 1-1/|C|\leqslant 1-1/n$ $\mu (g)\leqslant (1-1/n)\cdot \mu (f)$ $m-1$ $O(|V||E|)$ $d_{k}(v)$ $v\în V$ $k$ $d_{0}(v)=0$ $d_{k+1}(v)=\min _{e=(w,v)\in E_{f))(d_{k}(w)+l(e))$ $d_{k}(v)$ $O(nm)$ ${\overline {l}}(C)$ $\alpha =\min _{v\in V}\max _{j=0}^{n-1}({\frac {d_{n}(v)-d_{j}(v)} {nj)))$ $C$ $\delta$ $C$ $\delta$ ${\overline {l}}(C)=0$ $\alpha \geqslant 0$ $v$ $P$ $v$ $d_{n}(v)$ $P$ $C$ $P'$ $P$ $C$ $j$ $nj$ $l(C)\geqslant 0$ $d_{n}(v)=l(P)=l(C)+l(P')\geqslant l(P')\geqslant d_{j}(v)$ $v$ $j\in \{1,...,n-1\)$ $d_{n}(v)\geqslant d_{j}(v)$ $\alpha \leqslant 0$ $w$ $d_{n}(w)\leqslant d_{j}(w)$ $j\in \{1,...,n-1\)$ $v$ $C$ $P$ $v$ $p<n$ $P$ $w$ $C$ $n.p.$ $v$ $v$ $w$ $Q$ $R$ $w$ $v$ $S$ $j$ $w$ $d_{n}(w)\leqslant l(P)+l(Q)=d_{p}(v)+l(Q)$ $d_{p}(v)\leqslant d_{j+r}(v)\leqslant d_{j}(w)+l(R)$ $d_{n}(w)\leqslant d_{j}(w)+l(R)+l(Q)$ $Q\odot R$ $l(C)=0$ $d_{n}(w)\leqslant d_{j}(w)$ $j\in \{1,...,n-1\)$ $\alpha \leqslant 0$ $O(m^{2}\cdot n^{2}\cdot \log(nL))$ $n\log(nL)+1$ $m$ $O(nm)$ $O(m^{3}\cdot n^{2}\cdot \log(n))$
Utilizați o modificare a algoritmului Ford-Fulkerson , în care la fiecare pas este aleasă o cale incrementală a prețului minim. Pentru a selecta calea, puteți utiliza algoritmul Bellman-Ford.
Îmbunătățirea algoritmului anterior: folosind potențiale, puteți reduce problema la o problemă fără margini negative, după care, în loc de algoritmul Bellman-Ford, utilizați algoritmul lui Dijkstra . Algoritmul Bellman-Ford va trebui aplicat doar la primul pas.

Link -uri

Vizualizator al algoritmului pentru găsirea fluxului maxim de cost minim

Vezi și

Problema de debit maxim

Literatură

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .