Ein polynominaler primaler Netzwerk Simplex Algorithmus zur Berechnung von Flüssen mit minimalen Kosten

Inhaltsangabe:Einleitung: ‘Es gibt zwei Wege, die Rentabilität der Arbeit eines Geschäfts, eines Unternehmens oder eines ganzen Industriezweiges zu vergrößern. Ein Weg besteht in verschiedenen Verbesserungen der Technik, z.B. neuem Zubehör für die einzelnen Maschinen, Änderungen der technischen Prozesse und der Entdeckung neuer, besserer Arten von Rohmaterial. Der andere Weg, der bis jetzt viel weniger genutzt wurde, besteht in der Verbesserung der Organisation der Planung’. Dieses Zitat geht auf den russischen Mathematiker Kantorowicz zurück, der im Jahre 1939 mit seinem Buch ‘Mathematische Methoden in der Organisation und Planung der Produktion” die erste Arbeit auf dem Gebiet der mathematischen Optimierung veröffentlichte und somit den Grundstein für den großen Aufschwung der linearen Optimierung in den Folgejahren legte. Als Meilenstein in der Geschichte der linearen Optimierung gilt die Entwicklung des Simplex Algorithmus durch G.B. Dantzig im Jahre 1947. Bis heute ist der Simplex Algorithmus eines der mächtigsten und das in der Praxis am weitesten verbreitete Verfahren zur Lösung linearer Programme. Komplexe Problemstellungen mit tausenden von Variablen und Restriktionen lassen sich mit modernen Implementierungen des Algorithmus (wie z.B. CPLEX) innerhalb kürzester Zeit lösen. Zahlreiche Optimierungsprobleme aus dem täglichen Anwendungsbereich, wie z.B die Ermittlung von kürzesten Wegen innerhalb von Verkehrs- und Kommunikationsnetzen (Shortest Path Problem, SPP), die Maximierung des Verkehrsflusses auf einem vorgegebenen Straßennetz (Maximum Flow Problem, MFP), oder der kostenminimale Transport von Gütern zwischen Produzenten und Käufern (Minimum Cost Flow Problem, MCFP), weisen eine spezielle Struktur auf, welche es erlaubt, diese, selbst bei komplexen Zusammenhängen, anhand von geeigneten Graphen und Netzwerken zu modellieren. Probleme dieser Art werden in der Kategorie Netzwerkprobleme zusammengefasst. Innerhalb dieser Kategorie nimmt das zuletzt aufgeführte MCFP eine zentrale Position ein, da es möglich ist, eine Vielzahl anderer Netzwerkprobleme auf dieses zurückzuführen. Obwohl die oben skizzierten Netzwerkprobleme eine spezielle Klasse linearer Programme bilden, ist eine Darstellung dieser Probleme als lineare Programme denkbar ungünstig, da die resultierenden Programme sehr groß und mit einer immensen Degeneriertheit behaftet sind. Somit ist eine Lösung dieser Netzwerkprobleme mittels des traditionellen Simplex Algorithmus nur [...]