Minimum-Cost Flow Problem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

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:

  1. Die Kapazitätsfunktion weist jeder Kante zu, wie viel Güter maximal entlang der Kante transportiert werden können.
  2. 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:

  1. Die Flusserhaltung, welche sich für alle durch ausdrücken lässt.
  2. 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Im Fall einer linearen Kostenfunktion lässt sich das Problem durch Techniken der Linearen Programmierung und mit Hilfe des Simplex-Verfahrens lösen.

Konvexe Kostenfunktion[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Für allgemeine nichtlineare Kostenfunktionen ist das Finden einer Lösung NP-schwer.[6]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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[Bearbeiten | Quelltext bearbeiten]

  1. Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3642015793. Seite 169
  2. 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.
  3. 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.
  4. 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]).
  5. 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.
  6. 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.