Netzwerkflußprobleme

1 Einleitung.- 1.1 Einführung.- 1.2 Anwendungen aus der Praxis.- 1.3 Übersicht.- 2 Das lineare Netzwerkflußproblem.- 2.1 Mathematische Formulierung und Eigenschaften.- 2.1.1 Formulierung.- 2.1.2 Äquivalente Formulierungen.- 2.1.2.1 _ Formulierung in Matrixform.- 2.1.2.2 Formulierung als q-s-Flußproblem.- 2.1.2.3 Formulierung als Zirkulationsflußproblem.- 2.1.3 Eigenschaften.- 2.1.3.1 Zulässigkeit und Lösbarkeit.- 2.1.3.2 Ganzzahligkeit der Extremalpunkte des Lösungspolyeders.- 2.1.3.3 Rang der Koeffizientenmatrix.- 2.1.3.4 Optimalitätsbedingungen.- 2.2 Spezialfälle.- 2.2.1 Das Transportproblem.- 2.2.2 Das Zuordnungsproblem.- 2.2.3 Das Kürzeste-Wege-Problem.- 2.2.4 Das Maximalflußproblem.- 2.3 Mögliche Lösungsverfahren.- 2.3.1 Primale Verfahren.- 2.3.2 Primal-duale Verfahren.- 2.3.3 Out-of-Kilter-Verfahren.- 2.3.4 Duale Verfahren.- 2.3.5 Inkrementgraphen-Verfahren.- 2.3.6 Zusammenfassende Bewertung.- 3 Zwei neue primale Verfahren zur Lösung linearer Netzwerkflußprobleme.- 3.1 Das primale Netzwerk-Simplex-Verfahren.- 3.1.1 Konzeption des primalen Netzwerk-Simplex-Verfahrens.- 3.1.1.1 Das Eröffnungsverfahren.- 3.1.1.2 Pricing-Strategien.- 3.1.2 Implementation des primalen Netzwerk-Simplex-Verfahrens.- 3.1.2.1 Datenstrukturen zur Speicherung der Problemdaten..- 3.1.2.2 Datenstrukturen zur Speicherung der Basis.- 3.1.2.3 Implementationen des primalen Netzwerk-Simplex-Verfahrens.- 3.2 Das Lösungsverfahren LPArc-I.- 3.2.1 Datenstrukturen und globale Variable.- 3.2.2 Der Algorithmus.- 3.2.2.1 Die Darstellung im Pseudo-Code.- 3.2.2.2 Das Pricing.- 3.2.2.3 Die Wahl des die Basis verlassenden Pfeils.- 3.2.2.4 Der Basiswechsel.- 3.2.2.5 Das Eröffnungsverfahren.- 3.2.2.6 Das Programm LPArc-I.- 3.2.2.7 Reellwertige Kostenkoeffizienten.- 3.3 Das Lösungsverfahren LPArc-II.- 3.3.1 Datenstrukturen und globale Variable.- 3.3.2 Der Algorithmus.- 3.3.2.1 Die Wahl des die Basis verlassenden Pfeils.- 3.3.2.2 Der Basiswechsel.- 3.3.2.3 Alternative Updates beim Basiswechsel.- 3.3.2.4 Das Eröffnungsverfahren.- 3.3.2.5 Das Programm LPArc-II.- 3.4 Analyse des Laufzeitverhaltens.- 3.4.1 Die Durchführung der Laufzeitvergleiche.- 3.4.2 Verwendete Testprobleme.- 3.4.3 Vergleich der alternativen Updates beim Basiswechsel von LPArc-II.- 3.4.4 Neue Standardwerte für den Frequenz-Parameter.- 3.4.5 Laufzeitvergleiche.- 3.4.6 Zusammenfassende Bewertung.- 4 Das Fixkosten-Netzwerkflußproblem.- 4.1 Mathematische Formulierung und Eigenschaften.- 4.2 Der Spezialfall des Fixkosten-Transportproblems.- 4.3 Mögliche Lösungsverfahren.- 4.3.1 Implizite Enumerationsverfahren.- 4.3.2 Branch-and-Bound-Verfahren.- 4.3.3 Zusammenfassende Bewertung.- 4.4 Die lineare Relaxation.- 5 Ein neues Branch-and-Bound-Verfahren zur Lösung von Fixkosten-Netzwerkflußproblemen.- 5.1 Die Konzeption von Branch-and-Bound-Verfahren.- 5.1.1 Die Verzweigung.- 5.1.2 Die Ermittlung von unteren und oberen Schranken.- 5.1.2.1 Untere Schranke für das Problem (Pk).- 5.1.2.2 Obere Schranke für das Problem (Pk).- 5.1.2.3 Obere Schranke für das Ausgangsproblem (Po).- 5.1.3 Die Streichung und Auslotung.- 5.1.3.1 Streichung.- 5.1.3.2 Auslotung.- 5.1.4 Die Suchstrategie.- 5.1.5 Das Verfahren im Überblick.- 5.2 Das Lösungsverfahren FixArc.- 5.2.1 Die Verzweigung.- 5.2.2 Die Ermittlung von unteren und oberen Schranken.- 5.2.2.1 Untere Schranke für das Problem (FCNFPk).- 5.2.2.2 Obere Schranke für das Problem (FCNFPk).- 5.2.3 Die Suchstrategie.- 5.2.4 Die Penalties.- 5.2.4.1 Die Lagrange-Relaxation.- 5.2.4.2 Penalties für Basisvariable.- 5.2.4.3 Penalties für Nichtbasisvariable.- 5.2.4.4 Implementation der Penalty-Berechnung.- 5.2.5 Separationsregeln.- 5.2.6 Verzweigungsregeln.- 5.2.7 Weitere Einsatzmöglichkeiten der Penalties.- 5.2.7.1 Verschärfung der unteren Schranken für Teilprobleme.- 5.2.7.2 Erste untere Schranken für die Teilprobleme.- 5.2.7.3 Die optimale Basis von (NFRkUp).- 5.2.8 Das Verfahren im Überblick.- 5.2.9 Beispielrechnung.- 5.2.10 Approximative Lösung.- 5.3 Analyse des Laufzeitverhaltens.- 5.3.1 Die Durchführung der Laufzeitvergleiche.- 5.3.2 Verwendete Testprobleme.- 5.3.3 Ermittlung günstiger Separations- und Verzweigungsregeln.- 5.3.4 Vergleich der Penalties.- 5.3.5 Laufzeitvergleiche.- 5.3.5.1 Vergleiche mit allgemeinen Problemlösern.- 5.3.5.2 Vergleiche mit Problemlösern für Fixkosten-Transportprobleme.- 5.3.6 Die Lösung großer Probleme.- 5.3.7 Zusammenfassende Bewertung.- 6 Die Implementation unter Microsoft Windows.- 6.1 Microsoft Windows als Zielplattform.- 6.2 Die Implementation.- 6.2.1 Die Konzeption.- 6.2.2 Die Wahl der Entwicklungsumgebung.- 6.2.3 Die Benutzeroberfläche.- 6.2.3.1 Die Problemgenerierung.- 6.2.3.2 Der Editor für große Netzwerke.- 6.2.3.3 Die Problemlösung.- 6.2.3.4 Kontextsensitive Hilfe.- 6.2.4 Einsatz in Client/Server-Modellen.- 6.2.4.1 Datenaustausch.- 6.2.4.2 Makrosprache.- 7 Zusammenfassung.- A Spezifikationen der Testprobleme.- A.1 NETGEN.- A.2 FIXGEN.- Symbolverzeichnis.