Mindste omkostningsflowproblem

Det Problemet med minimale omkostninger flow er en algoritmisk problem af grafteori , som er at finde den mest effektive måde at bruge et transportnetværk mens opfylder de begrænsninger af produktion og anvendelse af netværksnoder. Det giver mulighed for at modellere et helt sæt praktiske problemer, hvor det drejer sig om at finde en optimal måde at overføre en ressource (f.eks. En væske, elektricitet) fra et sæt kilder til et sæt dræn.

Problemet med det minimale omkostningsflow er grundlæggende, da de fleste andre flowproblemer, såsom det maksimale flowproblem , kan ses som specielle tilfælde. Derudover er det muligt at løse problemet i nogle tilfælde effektivt ved hjælp af simpleksalgoritmen til netværk.

Problemdefinition

Overvej et transportnetværk , dvs. en rettet graf, som defineres: $G = (N, A)$

$d: N \ rightarrow \ mathbb {R}$ en funktion, der tager positive værdier for kildeknuderne ( dvs. producerer ressourcer), negative for sinknoderne ( dvs. bruger ressourcer) og nul for de såkaldte transitknudepunkter;
$f_ {max}: A \ rightarrow \ mathbb {R}$ en funktion, der forbinder hver kant det maksimale flow, som den kan understøtte;
$c: A \ rightarrow \ mathbb {R}$ en funktion, der måler transportomkostningerne pr. strømningsenhed for en given kant.

Under forudsætning af, at der er en mulig strøm, er det minimale omkostningsflowproblem at finde en strøm, der minimerer de samlede omkostninger: $f: A \ rightarrow \ mathbb {R}$ $\ sum_ {a \ i A} c (a) f (a)$

under begrænsningerne:

strøm bevarelse: $\ forall n \ i N, \ sum_ {a = (n, s) \ i A} f (a) - \ sum_ {a = (s, n) \ i A} f (a) = d (n)$
kapacitetsbegrænsning: $\ forall a \ i A, 0 \ leq f (a) \ leq f_ {max} (a)$

Eksistensen af en løsning

Det er muligt at vise, at der eksisterer en tilladelig strøm, hvis og kun hvis, for et hvilket som helst klip af grafen : $N = N_1 \ kop N_2$

\ sum_ {a \ in (N_1 \ times N_2) \ cap A} f_ {max} (a) \ geq \ sum_ {n \ in N_1} d (n)

Løsning

Problemet kan løses ved lineær programmering , da funktionen, der skal minimeres, og de forskellige begrænsninger er lineære. Der findes flere andre algoritmer, hvoraf nogle kan betragtes som generaliseringer af Ford-Fulkerson algoritmen , andre som generaliseringer af push / relabel algoritmen eller endda varianter af simplex algoritmen .

Relaterede problemer

Ved at indstille visse parametre opnår man andre flowproblemer .

Maksimalt flowproblem

Løsning af problemet med den maksimale strømning mellem en enkelt kilde og en enkelt sink i en graf svarer til at løse forekomsten af det minimale omkostningsflowproblem i grafen, hvor:

s

s

G = (N, A)

G '= (N, A \ cup \ {(p, s) \})

$\ forall n \ i N, d (n) = 0$
Der er ingen kapacitetsbegrænsning på den nye kant :; ${\ displaystyle f_ {max} ((p, s)) = + \ infty}$
den nye kant har en negativ pris og . $c ((p, s)) = - 1$ $\ forall a \ i A, c (a) = 0$

Da prisen mellem og er negativ, svarer minimeringsbetingelsen til at maksimere flowet.

s

s

Find den korteste sti mellem to noder

At finde den korteste vej mellem og svarer til at løse forekomsten af det minimale omkostningsflowproblem, hvor:

s \ i N

p \ i N

$s$ er den eneste kilde og den enkelte brønd: , og for de andre knuder; $s$ $d (s) = 1$ $d (p) = - 1$ $d (n) = 0$
Der er ingen kapacitetsbegrænsning ; $\ forall a \ i A, f_ {max} (a) = + \ infty$
enhedsomkostningerne er faste: $\ forall a \ i A, c (a) = 1$

At finde den korteste sti fra en node til alle de andre

At finde den korteste sti mellem en kilde og de andre noder svarer til at løse forekomsten af det minimale omkostningsflowproblem, hvor:

s \ i N

$s$ er den eneste kilde ( ), der fodrer alle andre noder ( ); $d (s) = | N | -1$ $\ forall n \ i N, d (n) = - 1 \ tekst {si} n \ neq s$
Der er ingen kapacitetsbegrænsning ; $\ forall a \ i A, f_ {max} (a) = + \ infty$
enhedsomkostningerne er fast: . $\ forall a \ i A, c (a) = 1$

Noter og referencer

Jungnickel 2013 .
Ahuja, Magnanti & Orlin 1993 .
(i) Morton Klein, " En primær metode til minimalt omkostningsflow med applikationer til opgave- og transportproblemer ," Management Science , bind. 14, 1967, s. 205-220 ( DOI 10.1287 / mnsc.14.3.205 )
(i) Jack Edmonds og Richard M. Karp, " Teoretisk algoritmiske forbedringer i effektivitet for net flow-problemer ," Journal of ACM , vol. 19, nr . 2 1972, s. 248-264 ( DOI 10.1145 / 321694.321699 )
(i) Andrew V. Goldberg og Robert E. Tarjan, " minimale omkostninger omløb Finding ved successiv tilnærmelse ", Math. Oper. Res. , Vol. 15, nr . 3, 1990, s. 430–466 ( DOI 10.1287 / hede.15.3.430 )
(i) James B. Orlin, " En polynomiel tid primal netværk simplex algoritme til minimale omkostninger flow ," Mathematical Programming , Vol. 78, 1997, s. 109–129 ( DOI 10.1007 / bf02614365 )

Bibliografi

(en) Dieter Jungnickel , grafer, netværk og algoritmer , Springer,2013, 4 th ed. ( ISBN 978-3-642-32277-8 , læs online ) , kap. afsnit 11.1
(en) Ravindra K. Ahuja , Thomas L. Magnanti og James B. Orlin , Network Flows: Theory, Algorithms, and Applications , Prentice-Hall, Inc.,1993, 846 s. ( ISBN 0-13-617549-X )
(fr) Denne artikel er helt eller delvist hentet fra Wikipedia-artiklen på engelsk med titlen " Minimum-cost flow problem " ( se listen over forfattere ) .

eksterne links

Relaterede artikler