„Minimum-Cost Flow Problem“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
Keine Bearbeitungszusammenfassung |
Der Artikel wurde substantiell erweitert, aber ich habe gerade keine Zeit mehr den Abschnitt Komplexität und Struktur der Kostenfunktion auszuweitern und die beiden noch geplanten Abschnitte Anwendungen und Beispiele einzufügen |
||
| Zeile 1: | Zeile 1: | ||
Das '''Minimum-Cost Flow Problem''' oder '''Min-Cost-Flow-Problem''' |
Das '''Minimum-Cost Flow Problem''' oder '''Min-Cost-Flow-Problem''' ist ein [[Optimierung (Mathematik)|Optimierungs]]- und [[Entscheidungsproblem]] aus der Klasse der [[Flüsse_und_Schnitte_in_Netzwerken|Netzwerkfluss]]<nowiki/>probleme und ist ein allgemeine Methode für die [[Modell|Modellierung]] und Lösung des [[Umladeproblem|Umlade-]] bzw. des [[Transportproblem]]<nowiki/>s.<ref>Leena Suhl, Taieb Mellouli: ''Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen''. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 169</ref> Probleme dieser Art wurden bereits 1781 von dem französischen Mathematiker [[Gaspard Monge]] formuliert <ref name="Monge">G. Monge. ''Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année.'' 1781, S. 666–704.</ref> und erhielten während der [[Aufrüstung]] im [[Kalter Krieg|Kalten Krieg]] auf Grund der militärischen Relevanz der Transport[[logistik]] des [[Nachschub|Nachschubs]] eine verstärkte Aufmerksamkeit.<ref name=":0">{{Literatur |Autor=Ravindra K. Ahuja, Thomas Magnanti, James Orlin|Titel=Network flows : theory, algorithms, and applications |Verlag=Prentice Hall |Ort=Englewood Cliffs, N.J. |Datum=1993 |ISBN=978-0-13-617549-0 }}</ref> Das Ziel ist es, gegeben eine Kostenfunktion für den [[Güternahverkehr (Deutschland)|Transport von Gütern]], die günstigste Möglichkeit für den [[Transport]] von einem oder Mehren Startpunkten (Quellen) durch ein Netzwerk zu einem oder mehreren Zielpunkten (Senken) zu bestimmen. Je nach Struktur der Kostenfunktion ist der Problem [[NP-Schwere|np-hart]] oder es existieren [[Polynomialzeit|polynomiell]] exakte Algorithmen. Im Allgemeinen ist die Lösung von Min-Cost-Flow Problemen nicht eindeutig. |
||
== Problem Formulierung == |
|||
Ein Fluss Netzwerk ist ein [[gerichteter Graph]] <math>G=(V,E)</math> zusammen mit einen Startknoten <math>s \in V</math> mit dem Angebot <math>a\in\R^+</math> und einen Zielknoten <math>t \in V</math> mit einer, dem Angebot entsprechenden Nachfrage <math>-a</math>, sowie 2 Funktionen, die auf der Kantenmenge definiert sind: |
|||
# Die '''Kapazitätsfunktion''' <math>\kappa: E \rightarrow \R^+</math> weist jeder Kante zu, wie viel Güter maximal entlang der Kante transportiert werden können. |
|||
# Die '''Flussfunktion''' <math>f : E \rightarrow \R_0^+</math> weist jeder Kante zu wieviel Güter tatsächlich für den Transport allokiert werden. Daher gilt auch die '''Kapazitätsbeschränkung''' <math>f(u,v) \leq \kappa(u,v) </math> für alle <math>v,u \in V</math> . |
|||
Darüber hinaus müssen für die Flussfunktion die folgenden 2 Eigenschaften gelten: |
|||
# Die '''Flusserhaltung''', welche sich für alle <math>u \neq s, t</math> durch <math>\,\sum_{w \in V} f(u,w) = 0</math> ausdrücken lässt. |
|||
# Die '''Flusserfüllung''' von Angebot und Nachfrage, die sich für den Startknoten durch <math>\,\sum_{w \in V} f(s,w) = d </math> und den Zielknoten durch <math>\, \sum_{w \in V} f(w,t) = d</math> ausdrücken lässt. |
|||
Führt man zusätzlich eine (trennbare) '''Kostenfunktion''' <math>c : E \times \R \rightarrow \R_0^+</math> ein, die jeder Kante in Abhängigkeit des allokierten Flusswertes einen Wert für die Transportkosten zuweist berechnet man die '''Gesamtkosten''' des Flusses <math>f</math> mit Hilfe der '''Kostenformel''' <math>\,C(f) = \sum_{(u,v) \in E} c(u,v,f(u,v)) </math>. |
|||
Bei einem Min-Cost Flow Problem sucht man eine Flussfunktion, welche die Kostenformel minimiert. |
|||
== Komplexität und Struktur der Kostenfunktion == |
|||
Die Kapazitätsbeschränkung, Flusserhaltung und Flusserfüllung machen das Auffinden einer Flussfunktion, die die Kostenformel minimiert zu einem Optimierungsproblem mit Zwangsbedingungen. Daher könnte man das Problem zumindest in der Theorie [[Numerische Mathematik|numerisch]] mit der Mode der [[Lagrange-Multiplikator|Lagrange-Multiplikatoren]] lösen. In der Praxis entstehen dabei jedoch in der Regel Funktionen, die so stark nicht linear sind, dass das Finden einer Lösung mit numerischen Methoden oft impraktikabel wird. Im Bereich der [[Informatik]] und des [[Operations Research|Operation Research]] wurden seit den späten 1960er Jahren [[Algorithmus|Algorithmen]] und Verfahren für die exakte Lösung dieser Problemklasse entwickelt.<ref>{{Literatur |Autor=Morton Klein |Titel=A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems |Sammelwerk=Management Science |Band=14 |Nummer=3 |Datum=1967-11-01 |ISSN=0025-1909 |DOI=10.1287/mnsc.14.3.205 |Seiten=205–220 |Online=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.14.3.205 |Abruf=2021-09-05}}</ref> Diese Lösungen existieren häufig in dem weitere Annahmen an das Problem gestellt werden. So wird das Problem im diskreten Fall, bei dem die Kapazitäts- und Fluss Funktion nur [[Natürliche Zahl|natürliche Zahlen]] oder den Wert 0 annimmt deutlich leichter zu berechnen. |
|||
=== Lineare Kostenfunktion === |
|||
Im Fall einer [[Lineare Abbildung|linearen]] Kostenfunktion lässt sich das Problem durch Techniken der [[Lineare Optimierung|Linearen Programmierung]] und mit Hilfe des [[Simplex-Verfahren|Simplex Verfahren]] lösen. |
|||
=== Konvexe Kostenfunktion === |
|||
1986 zeigte Minoux, dass für den [[Diskrete Mathematik|diskreten Fall]] sich polynomiell exakte Lösungen für das Problem im Falle einer [[Konvexe Optimierung|konvexen]] Kostenfunktion existieren.<ref>{{Literatur |Autor=M. Minoux |Titel=Solving integer minimum cost flows with separable convex cost objective polynomially |Sammelwerk=Netflow at Pisa |Verlag=Springer |Ort=Berlin, Heidelberg |Datum=1986 |Reihe=Mathematical Programming Studies |ISBN=978-3-642-00923-5 |DOI=10.1007/bfb0121104 |Seiten=237–239}}</ref> Diese können zum Beispiel gefunden werden, in dem die Kostenfunktion in den einzelnen Delta-Phasen des Capacity-Scaling Algorithmus stückweise [[Linearisierung|linearisiert]] wird.<ref name=":0" /> |
|||
=== Allgemeine nichtlineare Kostenfunktion === |
|||
Für allgemeine nichtlineare Kostenfunktionen ist das Finden einer Lösung np-hart.<ref>{{Literatur |Autor=G. M. Guisewite, P. M. Pardalos |Titel=Minimum concave-cost network flow problems: Applications, complexity, and algorithms |Sammelwerk=Annals of Operations Research |Band=25 |Nummer=1 |Datum=1990-12-01 |ISSN=1572-9338 |DOI=10.1007/BF02283688 |Seiten=75–99}}</ref> |
|||
== Siehe auch == |
|||
* ''[[Flüsse und Schnitte in Netzwerken|Maximum-Flow-Problemen]]'' |
|||
* [[Kürzester Pfad]] |
|||
*[[Zuordnungsproblem]] |
|||
* [[Operations Research]] |
|||
== Literatur == |
== Literatur == |
||
Version vom 5. September 2021, 12:41 Uhr
Das Minimum-Cost Flow Problem oder Min-Cost-Flow-Problem ist ein Optimierungs- und Entscheidungsproblem aus der Klasse der Netzwerkflussprobleme und ist ein allgemeine Methode für die Modellierung und Lösung des Umlade- bzw. des Transportproblems.[1] Probleme dieser Art wurden bereits 1781 von dem französischen Mathematiker Gaspard Monge formuliert [2] und erhielten während der Aufrüstung im Kalten Krieg auf Grund der militärischen Relevanz der Transportlogistik des Nachschubs eine verstärkte Aufmerksamkeit.[3] Das Ziel ist es, gegeben eine Kostenfunktion für den Transport von Gütern, die günstigste Möglichkeit für den Transport von einem oder Mehren Startpunkten (Quellen) durch ein Netzwerk zu einem oder mehreren Zielpunkten (Senken) zu bestimmen. Je nach Struktur der Kostenfunktion ist der Problem np-hart oder es existieren polynomiell exakte Algorithmen. Im Allgemeinen ist die Lösung von Min-Cost-Flow Problemen nicht eindeutig.
Problem Formulierung
Ein Fluss Netzwerk ist ein gerichteter Graph zusammen mit einen Startknoten mit dem Angebot und einen Zielknoten mit einer, dem Angebot entsprechenden Nachfrage , sowie 2 Funktionen, die auf der Kantenmenge definiert sind:
- Die Kapazitätsfunktion weist jeder Kante zu, wie viel Güter maximal entlang der Kante transportiert werden können.
- Die Flussfunktion weist jeder Kante zu wieviel Güter tatsächlich für den Transport allokiert werden. Daher gilt auch die Kapazitätsbeschränkung für alle .
Darüber hinaus müssen für die Flussfunktion die folgenden 2 Eigenschaften gelten:
- Die Flusserhaltung, welche sich für alle durch ausdrücken lässt.
- Die Flusserfüllung von Angebot und Nachfrage, die sich für den Startknoten durch und den Zielknoten durch ausdrücken lässt.
Führt man zusätzlich eine (trennbare) Kostenfunktion ein, die jeder Kante in Abhängigkeit des allokierten Flusswertes einen Wert für die Transportkosten zuweist berechnet man die Gesamtkosten des Flusses mit Hilfe der Kostenformel .
Bei einem Min-Cost Flow Problem sucht man eine Flussfunktion, welche die Kostenformel minimiert.
Komplexität und Struktur der Kostenfunktion
Die Kapazitätsbeschränkung, Flusserhaltung und Flusserfüllung machen das Auffinden einer Flussfunktion, die die Kostenformel minimiert zu einem Optimierungsproblem mit Zwangsbedingungen. Daher könnte man das Problem zumindest in der Theorie numerisch mit der Mode der Lagrange-Multiplikatoren lösen. In der Praxis entstehen dabei jedoch in der Regel Funktionen, die so stark nicht linear sind, dass das Finden einer Lösung mit numerischen Methoden oft impraktikabel wird. Im Bereich der Informatik und des Operation Research wurden seit den späten 1960er Jahren Algorithmen und Verfahren für die exakte Lösung dieser Problemklasse entwickelt.[4] Diese Lösungen existieren häufig in dem weitere Annahmen an das Problem gestellt werden. So wird das Problem im diskreten Fall, bei dem die Kapazitäts- und Fluss Funktion nur natürliche Zahlen oder den Wert 0 annimmt deutlich leichter zu berechnen.
Lineare Kostenfunktion
Im Fall einer linearen Kostenfunktion lässt sich das Problem durch Techniken der Linearen Programmierung und mit Hilfe des Simplex Verfahren lösen.
Konvexe Kostenfunktion
1986 zeigte Minoux, dass für den diskreten Fall sich polynomiell exakte Lösungen für das Problem im Falle einer konvexen Kostenfunktion existieren.[5] Diese können zum Beispiel gefunden werden, in dem die Kostenfunktion in den einzelnen Delta-Phasen des Capacity-Scaling Algorithmus stückweise linearisiert wird.[3]
Allgemeine nichtlineare Kostenfunktion
Für allgemeine nichtlineare Kostenfunktionen ist das Finden einer Lösung np-hart.[6]
Siehe auch
Literatur
- Oliver Zlotowski: Design, Implementierung und Evaluierung von Netzwerkdatenstrukturen und Netzwerkalgorithmen zum Lösen des Minimum-Cost Flow Problems. Logos Berlin (20. September 2010). ISBN 978-3832526009
Einzelnachweise
- ↑ Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 169
- ↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, S. 666–704.
- ↑ a b Ravindra K. Ahuja, Thomas Magnanti, James Orlin: Network flows : theory, algorithms, and applications. Prentice Hall, Englewood Cliffs, N.J. 1993, ISBN 978-0-13-617549-0.
- ↑ Morton Klein: A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. In: Management Science. Band 14, Nr. 3, 1. November 1967, ISSN 0025-1909, S. 205–220, doi:10.1287/mnsc.14.3.205 (informs.org [abgerufen am 5. September 2021]).
- ↑ M. Minoux: Solving integer minimum cost flows with separable convex cost objective polynomially. In: Netflow at Pisa (= Mathematical Programming Studies). Springer, Berlin, Heidelberg 1986, ISBN 978-3-642-00923-5, S. 237–239, doi:10.1007/bfb0121104.
- ↑ G. M. Guisewite, P. M. Pardalos: Minimum concave-cost network flow problems: Applications, complexity, and algorithms. In: Annals of Operations Research. Band 25, Nr. 1, 1. Dezember 1990, ISSN 1572-9338, S. 75–99, doi:10.1007/BF02283688.