Problema fluxului de cost minim

Problema debitului costului minim (problema costului minim-cost, abreviat MCFP) este o problemă de decizie și optimizare care constă în găsirea modului cel mai scump posibil de a trece o anumită cantitate de flux printr-o rețea de flux .

Definiție

O rețea de flux este un grafic orientat $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ cu un nod sursă $s\in V$ ${\ displaystyle s \ în V}$ ${\ displaystyle s \ în V}$ și o fântână $t\in V$ ${\ displaystyle t \ in V}$ ${\ displaystyle t \ in V}$ , în care fiecare arc $(u,v)\in E$ ${\ displaystyle (u, v) \ în E}$ ${\ displaystyle (u, v) \ în E}$ are capacitate $c(u,v)>0$ ${\ displaystyle c (u, v)> 0}$ ${\ displaystyle c (u, v)> 0}$ , curgere $f(u,v)\geq 0$ ${\ displaystyle f (u, v) \ geq 0}$ ${\ displaystyle f (u, v) \ geq 0}$ și cost $a(u,v)$ ${\ displaystyle a (u, v)}$ ${\ displaystyle a (u, v)}$ (Algoritmii MCF acceptă arce cu costuri negative). Costul transportului acestui flux printr-un arc $(u,v)$ ${\ displaystyle (u, v)}$ $(u, v)$ Și $f(u,v)\cdot a(u,v)$ ${\ displaystyle f (u, v) \ cdot a (u, v)}$ ${\ displaystyle f (u, v) \ cdot a (u, v)}$ . Problema remediază o anumită cantitate de flux $d$ ${\ displaystyle d}$ $d$ care trebuie trimise de la sursă la fântână.

Problema necesită minimizarea costului total al fluxului prin toate arcurile.

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

{\ displaystyle \ sum _ {(u, v) \ în E} a (u, v) \ cdot f (u, v)}

{\ displaystyle \ sum _ {(u, v) \ în E} a (u, v) \ cdot f (u, v)}

cu următoarele constrângeri:

Constrângerea capacității :

\,f(u,v)\leq c(u,v)

{\ displaystyle \, f (u, v) \ leq c (u, v)}

{\ displaystyle \, f (u, v) \ leq c (u, v)}

Hemimetrie :

\,f(u,v)=-f(v,u)

{\ displaystyle \, f (u, v) = - f (v, u)}

{\ displaystyle \, f (u, v) = - f (v, u)}

Conservarea fluxului :

\,\sum _{w\in V}f(u,w)=0\quad \forall u\neq s,t

{\ displaystyle \, \ sum _ {w \ in V} f (u, w) = 0 \ quad \ forall u \ neq s, t}

{\ displaystyle \, \ sum _ {w \ in V} f (u, w) = 0 \ quad \ forall u \ neq s, t}

Debitul impus :

\,\sum _{w\in V}f(s,w)=d\land \sum _{w\in V}f(w,t)=d

{\ displaystyle \, \ sum _ {w \ in V} f (s, w) = d \ land \ sum _ {w \ in V} f (w, t) = d}

{\ displaystyle \, \ sum _ {w \ in V} f (s, w) = d \ land \ sum _ {w \ in V} f (w, t) = d}

Relațiile cu alte probleme

O variantă a problemei este găsirea soluției la problema debitului maxim care are un cost minim. Poate fi util să găsiți potrivirea maximă a costului minim.

O altă problemă conexă este cea a circulației cu cel mai mic cost, care poate fi exploatată pentru a rezolva MCFP.

În plus, următoarele probleme pot fi considerate cazuri speciale ：

prin eliminarea constrângerii de capacitate, MCFP este redus la cea mai scurtă problemă de cale ,
dacă toate costurile sunt stabilite la zero, MCFP este redus la problema debitului maxim .

Soluții

Problema fluxului de cost minim poate fi rezolvată prin programare liniară . Există, de asemenea, mulți algoritmi combinatori. ^[1] Unele dintre ele sunt generalizări ale algoritmilor de flux maxim , altele folosesc abordări complet diferite.

Cei mai cunoscuți algoritmi:

Anularea ciclului . ^[2]
Anularea ciclului mediu minim : algoritm puternic polinomial . ^[3]
Cea mai scurtă cale succesivă și scalarea capacității : metode care pot fi văzute ca o generalizare a algoritmului Ford-Fulkerson . ^[4]
Scalarea costurilor : metodă care poate fi privită ca o generalizare a algoritmului push-relabel . ^[5]
Algoritmul simplex pe rețele : ^[6] specializarea algoritmului simplex . ^[7]
Algoritm în afara greutății , conceput de DR Fulkerson

Notă

^ (EN) Ravindra K. Ahuja , Thomas L. Magnanti și James B. Orlin , Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc., 1993, ISBN 0-13-617549-X .
^ (EN) Morton Klein, O metodă primară pentru fluxuri de costuri minime cu aplicații la problemele de atribuire și transport , în Management Science, vol. 14, 1967, pp. 205-220, DOI : 10.1287 / mnsc.14.3.205 .
^ (EN) Andrew V. Goldberg și Robert E. Tarjan , Găsirea circulațiilor cu cost minim prin anularea ciclurilor negative în Jurnalul ACM, vol. 36, n. 4, 1989, pp. 873–886, DOI : 10.1145 / 76359.76368 .
^ (EN) Jack Edmonds și Richard M. Karp , Îmbunătățiri teoretice în eficiența algoritmică pentru problemele fluxului de rețea , în Jurnalul ACM, vol. 19, nr. 2, 1972, pp. 248-264, DOI : 10.1145 / 321694.321699 .
^ (EN) Andrew V. Goldberg și Robert E. Tarjan , Găsirea circulației costurilor minime prin aproximare succesivă , în matematică. Oper. Rez. , Vol. 15, nr. 3, 1990, pp. 430–466, DOI : 10.1287 / moor.15.3.430 .
^ Alessandro Agnetis, Fluxul de costuri minim și simplex pe rețele ( PDF ), pe dii.unisi.it , Universitatea din Siena , Departamentul de Inginerie informațională. Adus la 4 septembrie 2016 ( arhivat la 20 septembrie 2010) .
^ (EN) James B. Orlin , Un algoritm simplex primar polinomial pentru fluxuri de rețea cu cost minim , în Mathematical Programming, Vol. 78, 1997, pp. 109-129, DOI : 10.1007 / bf02614365 .

Elemente conexe

linkuri externe

Marco Locatelli, Probleme cu fluxul de costuri minime ( PDF ), pe di.unito.it , Universitatea din Torino , Departamentul de informatică. Accesat la 4 septembrie 2016 ( arhivat la 4 septembrie 2016) .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[AMO93-1] (EN) Ravindra K. Ahuja , Thomas L. Magnanti și James B. Orlin , Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc., 1993, ISBN 0-13-617549-X .

[K67-2] (EN) Morton Klein, O metodă primară pentru fluxuri de costuri minime cu aplicații la problemele de atribuire și transport , în Management Science, vol. 14, 1967, pp. 205-220, DOI : 10.1287 / mnsc.14.3.205 .

[GT89-3] (EN) Andrew V. Goldberg și Robert E. Tarjan , Găsirea circulațiilor cu cost minim prin anularea ciclurilor negative în Jurnalul ACM, vol. 36, n. 4, 1989, pp. 873–886, DOI : 10.1145 / 76359.76368 .

[EK72-4] (EN) Jack Edmonds și Richard M. Karp , Îmbunătățiri teoretice în eficiența algoritmică pentru problemele fluxului de rețea , în Jurnalul ACM, vol. 19, nr. 2, 1972, pp. 248-264, DOI : 10.1145 / 321694.321699 .

[GT90-5] (EN) Andrew V. Goldberg și Robert E. Tarjan , Găsirea circulației costurilor minime prin aproximare succesivă , în matematică. Oper. Rez. , Vol. 15, nr. 3, 1990, pp. 430–466, DOI : 10.1287 / moor.15.3.430 .

[6] Alessandro Agnetis, Fluxul de costuri minim și simplex pe rețele ( PDF ), pe dii.unisi.it , Universitatea din Siena , Departamentul de Inginerie informațională. Adus la 4 septembrie 2016 ( arhivat la 20 septembrie 2010) .

[O97-7] (EN) James B. Orlin , Un algoritm simplex primar polinomial pentru fluxuri de rețea cu cost minim , în Mathematical Programming, Vol. 78, 1997, pp. 109-129, DOI : 10.1007 / bf02614365 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]