Christoph Arlt

Netzwerkflußprobleme

Lösungsansätze unter Berücksichtigung von Fixkosten
Mitarbeit:Arlt, Christoph

• Broschiertes Buch

Produktbeschreibung

Netzwerkmodelle erleichtern aufgrund ihrer symbolhaften Darstellbarkeit in Form von Diagrammen das Verständnis von Problemzusammenhängen und sind gleichzeitig durch spezialisierte Optimierungsverfahren besonders schnell lösbar.

Produktdetails

• Gabler Edition Wissenschaft
• Verlag: Deutscher Universitätsverlag
• Artikelnr. des Verlages: 978-3-8244-6004-5
• 1994
• Seitenzahl: 228
• Erscheinungstermin: 15. Februar 1994
• Deutsch
• Abmessung: 210mm x 148mm x 13mm
• Gewicht: 280g
• ISBN-13: 9783824460045
• ISBN-10: 3824460041
• Artikelnr.: 24754358

Inhaltsangabe

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.-