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

Diplomarbeit von Timm Pliefke

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 mit sehr hohem Zeit- und Rechenaufwand möglich und folglich nicht diskutabel.

Hier gelang es Dantzig 1951 das Kernkonzept des von ihm entwickelten Simplex Algorithmus auf die strukturellen Besonderheiten von Netzwerken zu transformieren und somit eine graphentheoretische Spezialisierung des Verfahrens, den sogenannten Netzwerk Simplex Algorithmus, zu entwickeln. Obwohl sich dieser in zahlreichen Varianten in der Praxis bewährt hat, blieb es über lange Zeit ein offenes Problem, die polynomiale Beschränktheit der Komplexität eines Netzwerk Simplex Algorithmus für das MCFP nachzuweisen. Dieses Problem wurde 1995 von Orlin gelöst, der mit dem so genannten Premultiplier Algorithmus eine Spezialform des Netzwerk Simplex Algorithmus entwickelte, welcher für ein MCFP mit polynomialer Komplexität eine Optimallösung generiert.

Das Ziel der vorliegenden Arbeit besteht darin, durch systematisches Vorgehen ein weit reichendes Verständnis für die Problematik des Netzwerk Simplex Algorithmus zur Lösung eines MCFP zu schaffen, die Einflussgrößen der Komplexität des Verfahrens darzulegen und aufbauend auf den erzielten Befunden die Polynomialität des Premultiplier Algorithmus nachzuweisen. Ferner soll auf Grundlage geeigneter Datenstrukturen eine Implementierung der Algorithmen auf Basis der in der Literatur gebräuchlichen, an PASCAL orientierten Pseudocodes dokumentiert werden.

Hierfür werden wir im ersten Kapitel zunächst die grundlegenden Begrifflichkeiten und Ergebnisse der algorithmischen Graphentheorie und der Flusstheorie bereitstellen.

Eine Einführung in die Problematik des Minimum Cost Flow Problems werden wir im zweiten Kapitel dieser Arbeit aufführen und überdies bereits erste Grundgedanken zur Optimierung des Problems entwickeln.

Im dritten Kapitel werden wir den Netzwerk Simplex Algorithmus in seiner allgemeinen Form vorstellen und die wesentlichen Einflussgrößen der Laufzeit des Verfahrens diskutieren.

Aufbauend auf diesen Erkenntnissen werden wir im vierten Kapitel dieser Arbeit mit dem Premultiplier Algorithmus eine Spezialform des Netzwerk Simplex Algorithmus kennen lernen und durch eine detaillierte Laufzeitanalyse die theoretische Effizienz des Verfahrens nachweisen.

Eine ausführlich dokumentierte Implementierung der vorgestellten Netzwerk Simplex Algorithmen auf Grundlage von Pseudocodes werden wir in Kapitel fünf dieser Arbeit darlegen.

Mit einer komprimierten Zusammenstellung der entwickelten Ergebnisse, sowie mit Vorschlägen zur Verbesserung bestehender Implementierungen werden wir diese Arbeit abschließen.

Inhaltsverzeichnis:

Textprobe:

Kapitel 4., Der Premultiplier Algorithmus:

Obwohl sich der im letzten Kapitel diskutierte Netzwerk Simplex Algorithmus aufgrund seiner Einfachheit und Schnelligkeit in der Praxis bewährt hat, konnten für zahlreiche etablierte Pivot Regeln Beispiele konstruiert werden, für die der Algorithmus im schlechtesten Falle eine exponentielle Anzahl an Pivot Schritten beansprucht und somit eine nicht polynomiale Komplexität aufweist. Insbesondere für Dantzigs Pivot Regel sind einige dieser pathologischen Beispiele in den Veröffentlichungen von Zadeh und zu finden. Für einige Spezialfälle des MCFP, wie z.B. das Assignment Problem, das kürzeste Wege Problem und das Maximum Flow Problem konnte bereits die polynomiale Komplexität spezieller Netzwerk Simplex Algorithmen nachgewiesen werden.

In diesem Kapitel werden wir nun den von Orlin entwickelten Premultiplier Algorithmus vorstellen. Dieser ist der erste primale Netzwerk Simplex Algorithmus, der für ein MCFP mit polynomialer Komplexität eine Optimallösung generiert.

An Stelle des Vektors von Simplex Multiplikatoren operiert der Premultiplier Algorithmus in jedem Iterationsschritt mit Knotenpotentialen, welche so genannte Vektoren von Premultiplikatoren darstellen. Die an einen Vektor von Premultiplikatoren gestellten Bedingungen bilden hierbei eine Relaxierung der Anforderungen, die ein Vektor von Simplex Multiplikatoren zu erfüllen hat. Die Verwendung von Premultiplikatoren macht zunächst einige Modifikationen in der Notation notwendig, besitzt aber den entscheidenden Vorteil, dass die Knotenpotentiale nicht nach jedem Pivot Schritt aktualisiert werden müssen. Vielmehr werden die Premultiplikatoren nur dann modifiziert, wenn innerhalb des Netzwerkes bezüglich des aktuellen Knotenpotentials keine zulässige Eingangskante aufgespürt werden kann. Eine weitere Besonderheit des Premultiplier Algorithmus ist darin zu sehen, dass in jedem Pivot Schritt die Wurzel des aufspannenden Baumes variiert.

Im ersten Abschnitt dieses Kapitels werden wir den Premultiplier Algorithmus in seiner allgemeinen Form vorstellen. Hierfür werden wir zunächst Vektoren von Premultiplikatoren als spezielle Knotenpotentiale charakterisieren und die Definition zulässiger Eingangskanten in den Kontext des Premultiplier Algorithmus einbetten. Anschließend werden wir eine explizite Beschreibung des Premultiplier Algorithmus aufführen und veranschaulichen, inwiefern dieser als eine Spezialform des Netzwerk Simplex Algorithmus betrachtet werden kann. Letztlich erfolgt eine Diskussion über die Terminierung des Verfahrens.

Im zweiten Abschnitt dieses Kapitels werden wir das Kernkonzept des Kosten- Skalierungs-Algorithmus von Goldberg und Tarjan in Kombination mit einer effektiven Strategie zur Selektion der Eingangskante auf den allgemeinen Premultiplier Algorithmus übertragen und auf diese Weise zur skalierten Version des Premultiplier Algorithmus gelangen. Hierfür werden wir zunächst die nötigen Begrifflichkeiten bereitstellen und anschließend den skalierten Premultiplier Algorithmus explizit formulieren. Schließlich werden wir anhand einer detaillierten Komplexitätsanalyse die Terminierung des Verfahrens in polynomialer Zeit bestätigen.