Minimum-Cost Flow Problem

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. Probleme dieser Art wurden bereits 1781 von dem französischen Mathematiker Gaspard Monge formuliert und erhielten während der Aufrüstung im Kalten Krieg auf Grund der militärischen Relevanz der Transportlogistik des Nachschubs eine verstärkte Aufmerksamkeit. 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 mehreren Startpunkten (Quellen) durch ein Netzwerk zu einem oder mehreren Zielpunkten (Senken) zu bestimmen. Je nach Struktur der Kostenfunktion ist das Problem NP-schwer oder es existieren polynomiell exakte Algorithmen. Im Allgemeinen ist die Lösung von Min-Cost-Flow Problemen nicht eindeutig.