Problem protoka sa minimalnom cenom

Problem protoka sa minimalnom cenom je optimizacioni problem i problem odlučivanja kako bi se našlo najeftiniji mogući način slanja protoka kroz transportnu mrežu. Rešavanje ovog problema je korisno za životne situacije koje sadrže mreže sa cenama (npr. telekomunikacione mreže), kao i za druge situacije gde analogija nije toliko očigledna, na primer, gde naći stovarište.

Definicija

Transportna mreža je orijentisani graf $G=(V,E)$ sa izvornom tačkom $s\in V$ i završno tačkom $t\in V$, gde svaka ivica $(u,v)\in E$ ima popusnost $c(u,v)>0$, protok $f(u,v)\geq 0$ i cenu $a(u,v)$ (većina algoritama minimalne cene protoka podržavaju grane sa negativnim cenama). Cena slanja ovakvog protoka je $f(u,v)\cdot a(u,v)$. Potrebno je poslati $d$ protoka od $s$ do $t$.

Definicija problema je minimizirati ukupnu cenu protoka:

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

sa ovim ograničenjima

Ograničenje popusnosti:	$\,f(u,v)\leq c(u,v)$
Kosa simetrija:	$\,f(u,v)=-f(v,u)$
Čuvanje toka:	$\,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t$
Potreban protok:	$\,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d$

Relacije sa drgim problemima

Jedna varijacija ovog problema je da se nađe protok koji je maksimalan, ali ima najmanju cenu među maksimalnim. Ovaj problem bi se mogao nazvati poblem maksimalnog potoka minimalne cene. Ovo je korisno za nalaženje minimalne cene maksimalnog uparivanja.

Sa nekim rešenjima, nalaženje minimalne cene maksimalnog protoka je direkno. Ako nije, može se uraditi binarna pretraga po d.

Povezan problem je problem minimalna cene cirkulacije, koji može da se koristi za rešavanje minimalne cene protoka. Ovo se radi tako što se donja granica na svim granama stavi na nulu, a onda se dodaje nova grana od čvora $t$ do čvora $s$, sa propušnošću $c(t,s)=d$, Prisiljavajući ukupan protok od $s$ do $t$ da takođe bude $d$.

Problem može biti specijalizovan u druga dva problema:

• Ako je ograničenje propustnosti izbačeno, problem se svodi na problem najkraće putanje.
• Ako se sve cene postave na nule, problem se svodi na problem maksimalnog protoka.

Rešenja

Problem minimalne cene protoka može biti rešen korišćenjem linearnog programiranja, pošto možemo da optimizujemo linearnu funkciju i sva ograničenja su linearna.

Osim toga postoji mnogo kombinatornih algoritama za opširniji. Neki od njih su generalizacije algoritama maksimalnog protoka, drugi koriste u potpunosti drugačije pristupe rešavanju problema.

Dobro poznati fundementalni algoritmi (imaju mnogo varijacija):

• Izbacivanje ciklusa, generalno osnovni metod.
• Izbacivanje minimalnih ciklusa, jednostavan strogo polinomijalni algoritam.
• Uzastopni najkraći putevi, proporcionisanje propustnosti: dualne metode, koje se mogu posmatrati kao generalizacije Ford-fulkersonovog algoritma.
• Proporcionisanje cena, Osnovni dualni pristup koji može biti posmatran kao generalizaija algoritma push-relabel.
• Simpleks mreže: Specijalizovana verzija linearnog programiranja simpleks metode, koja se izvršava u polinomijalnom vremenu.