Minimalkostenflussproblem – Wikipedia
Mathematisches Optimierungsproblem
Die Minimum-Cost-Flow-Problem (MCFP) ist ein Optimierungs- und Entscheidungsproblem, um den günstigsten Weg zu finden, eine bestimmte Menge an Fluss durch ein Flussnetz zu senden. Eine typische Anwendung dieses Problems besteht darin, den besten Lieferweg von einer Fabrik zu einem Lager zu finden, wo das Straßennetz eine gewisse Kapazität und damit verbundene Kosten hat. Das Minimalkostenflussproblem ist eines der grundlegendsten unter allen Fluss- und Zirkulationsproblemen, da die meisten anderen dieser Probleme als Minimalkostenflussproblem betrachtet werden können und auch effizient unter Verwendung des Netzwerksimplexalgorithmus gelöst werden können.
Definition[edit]
Ein Flussnetzwerk ist ein gerichteter Graph
g=(V,E){displaystyle G=(V,E)}mit einem Quellknoten
S∈V{displaystyle sin V}
und ein Senkenscheitel
T∈V{displaystyle tin V}
, wobei jede Kante
(du,v)∈E{displaystyle (u,v)in E}
hat Kapazität
F(du,v)≥0{displaystyle f(u,v)geq 0}
und kosten
ein(du,v){displaystyle a(u,v)}
, wobei die meisten Flow-Algorithmen mit minimalen Kosten Kanten mit negativen Kosten unterstützen. Die Kosten für das Senden dieses Flusses entlang einer Kante
(du,v){displaystyle (u,v)}
ist
F(du,v)⋅ein(du,v){displaystyle f(u,v)cdot a(u,v)}
. Das Problem erfordert eine Menge an Durchfluss
D{displaystyle d}
von Quelle gesendet werden
S{displaystyle s}
sinken
T{displaystyle t}
.
Die Definition des Problems besteht darin, die Gesamtkosten der Strömung über alle Kanten:
- Σ(du,v)∈Eein(du,v)⋅F(du,v){displaystyle sum _{(u,v)in E}a(u,v)cdot f(u,v)}
mit den Einschränkungen
-
Kapazitätsengpässe: F(du,v)≤C(du,v){displaystyle ,f(u,v)leq c(u,v)} Symmetrie verzerren: F(du,v)=−F(v,du){displaystyle ,f(u,v)=-f(v,u)} Strömungserhaltung: Σw∈VF(du,w)=0 für alle du≠S,T{displaystyle ,sum _{win V}f(u,w)=0{text{ für alle }}uneq s,t} Erforderlicher Durchfluss: Σw∈VF(S,w)=D und Σw∈VF(w,T)=D{displaystyle ,sum _{win V}f(s,w)=d{text{ und }}sum _{win V}f(w,t)=d}
Bezug zu anderen Problemen[edit]
Eine Variation dieses Problems besteht darin, einen maximalen Durchfluss zu finden, der jedoch die niedrigsten Kosten unter den Lösungen mit maximalem Durchfluss aufweist. Dies könnte ein Minimum-Cost-Maximum-Flow-Problem genannt werden und ist nützlich, um Minimum-Cost-Maximum-Matchings zu finden.
Bei einigen Lösungen ist es stattdessen einfach, den minimalen Kosten-Maximum-Flow zu finden. Wenn nicht, kann man den maximalen Durchfluss finden, indem man eine binäre Suche nach durchführt
D{displaystyle d}.
Ein verwandtes Problem ist das Minimalkostenzirkulationsproblem, das zur Lösung des Minimalkostenflusses verwendet werden kann. Dies wird erreicht, indem die untere Grenze an allen Kanten auf Null gesetzt wird und dann eine zusätzliche Kante aus der Senke erstellt wird
T{displaystyle t}zur Quelle
S{displaystyle s}, mit Kapazität
C(T,S)=D{displaystyle c(t,s)=d}und untere Grenze
l(T,S)=D{displaystyle l(t,s)=d}
, erzwingt den Gesamtfluss von
S{displaystyle s}
zu
T{displaystyle t}auch sein
D{displaystyle d}.
Die folgenden Probleme sind Spezialfälle des Minimalkostenflussproblems (wir geben der Reihe nach kurze Skizzen zu jeder anwendbaren Reduktion):[1]
- Kürzeste-Weg-Problem (Single-Source). Erfordern, dass eine praktikable Lösung für das Problem des minimalen Kostenflusses eine Flusseinheit von einer bestimmten Quelle sendet
S{displaystyle s} zu einem ausgewiesenen Waschbecken T{displaystyle t} . Gib allen Kanten unendliche Kapazität. - Problem des maximalen Durchflusses. Alle Knoten haben eine Nachfrage von Null und die Kosten, die mit dem Durchqueren einer beliebigen Kante verbunden sind, seien Null. Führen Sie nun eine neue Kante ein
(T,S){displaystyle (t,s)} aus der aktuellen Spüle T{displaystyle t} zur aktuellen Quelle S{displaystyle s} . Legen Sie fest, dass die Kosten pro Einheit für das Senden über die Kante fließen (T,S){displaystyle (t,s)} gleich −1{displaystyle -1} , und erlauben (T,S){displaystyle (t,s)} unendliche Kapazität. (Diese Reduzierung wird auch im Kreislaufproblem erwähnt). - Zuordnungsproblem. Angenommen, jede Teilmenge in der Bipartition hat
n{displaystyle n} Scheitelpunkte und bezeichnen die Bipartition mit (x,Ja){displaystyle (X,Y)} . Gib jedem x∈x{displaystyle xin X} liefern 1/n{displaystyle 1/n} und gib jedem ja∈Ja{displaystyle yin Y} Anforderung 1/n{displaystyle 1/n} . Jede Kante soll eine Einheitskapazität haben.
Lösungen[edit]
Das Problem des minimalen Kostenflusses kann durch lineare Programmierung gelöst werden, da wir eine lineare Funktion optimieren und alle Nebenbedingungen linear sind.
Darüber hinaus existieren viele kombinatorische Algorithmen, für einen umfassenden Überblick siehe [1]. Einige von ihnen sind Verallgemeinerungen von Maximum-Flow-Algorithmen, andere verwenden völlig andere Ansätze.
Bekannte fundamentale Algorithmen (sie haben viele Variationen):
Anwendung[edit]
Bipartite Matching mit minimalem Gewicht[edit]
Gegeben einen bipartiten Graphen g = (EIN ∪ B, E), das Ziel ist es, das maximale Kardinalitätsmatching in zu finden g das hat minimale kosten. Lassen w: E → R sei eine Gewichtsfunktion auf den Kanten von E. Das bipartite Matching- oder Zuweisungsproblem mit minimalem Gewicht besteht darin, ein perfektes Matching zu finden m ⊆ E deren Gesamtgewicht minimiert wird. Die Idee ist, dieses Problem auf ein Netzwerkflussproblem zu reduzieren.
Lassen G’ = (V′ = EIN ∪ B, E′ = E). Weisen Sie die Kapazität aller Kanten in . zu E′ zu 1. Fügen Sie einen Quell-Scheitelpunkt hinzu S und verbinde es mit allen Scheitelpunkten in EIN’ und füge einen Senkenscheitelpunkt hinzu T und verbinde alle Scheitelpunkte innerhalb der Gruppe B’ zu diesem Scheitelpunkt. Die Kapazität aller neuen Kanten ist 1 und ihre Kosten sind 0. Es ist bewiesen, dass es in . ein perfektes bipartites Matching mit minimalem Gewicht gibt g genau dann, wenn ein Mindestkostenstrom einfließt G’. [9][dead link]
Siehe auch[edit]
Verweise[edit]
- ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Netzwerkflüsse. Theorie, Algorithmen und Anwendungen. Lehrlingssaal.
- ^ Ravindra K. Ahuja; Thomas L. Magnanti & James B. Orlin (1993). Netzwerkflüsse: Theorie, Algorithmen und Anwendungen. Prentice-Hall, Inc. ISBN 978-0-13-617549-0.
- ^ Morton Klein (1967). “Eine Urmethode für minimale Kostenflüsse mit Anwendungen auf die Zuordnungs- und Transportproblematik”. Managementwissenschaft. 14 (3): 205–220. CiteSeerX 10.1.1.228.7696. mach:10.1287/mnsc.14.3.205.
- ^ Refael Hassin (1983). “Das minimale Kostenflussproblem: Ein vereinheitlichender Ansatz für bestehende Algorithmen und ein neuer Baumsuchalgorithmus”. Mathematische Programmierung. 25: 228–239. mach:10.1007/bf02591772.
- ^ Thomas R. Ervolina & S. Thomas McCormick (1993). “Zwei stark polynomiale Cut-Cancelling-Algorithmen für minimalen Netzwerkfluss”. Diskrete Angewandte Mathematik. 4: 133–165. mach:10.1016/0166-218x(93)90025-j.
- ^ Andrew V. Goldberg & Robert E. Tarjan (1989). “Ermittlung von Auflagen mit minimalen Kosten durch Aufhebung negativer Zyklen”. Zeitschrift der ACM. 36 (4): 873–886. mach:10.1145/76359.76368.
- ^ Jack Edmonds & Richard M. Karp (1972). “Theoretische Verbesserungen der algorithmischen Effizienz für Netzwerkflussprobleme”. Zeitschrift der ACM. 19 (2): 248–264. mach:10.1145/321694.321699.
- ^ Andrew V. Goldberg & Robert E. Tarjan (1990). “Ermittlung der kostenminimierten Auflagen durch sukzessive Approximation”. Mathematik. Oper. Auflösung. fünfzehn (3): 430–466. mach:10.1287/moor.15.3.430.
- ^ James B. Orlin (1997). “Ein Polynomialzeit-Primal-Network-Simplexalgorithmus für minimale Kostenflüsse”. Mathematische Programmierung. 78 (2): 109–129. mach:10.1007/bf02614365. hdl:1721.1/2584.
Recent Comments