Netzwerkflußprobleme (eBook, PDF)

Lösungsansätze unter Berücksichtigung von Fixkosten

• Format: PDF

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.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Deutscher Universitätsverlag
• Seitenzahl: 212
• Erscheinungstermin: 9. März 2013
• Deutsch
• ISBN-13: 9783322995506
• Artikelnr.: 53105425

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