Christoph Arlt
Netzwerkflußprobleme
Lösungsansätze unter Berücksichtigung von Fixkosten
Mitarbeit:Arlt, Christoph
Christoph Arlt
Netzwerkflußprobleme
Lösungsansätze unter Berücksichtigung von Fixkosten
Mitarbeit:Arlt, Christoph
- Broschiertes Buch
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
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.
Andere Kunden interessierten sich auch für
- Werner ZimmermannPlanungsrechnung und Entscheidungstechnik69,99 €
- Kurt HeidenbergerQuantitative Modelle für das Strategische Management54,99 €
- Oliver WendtTourenplanung durch Einsatz naturanaloger Verfahren49,99 €
- Alexander BradelIndustriebetrieb und Verkehrsproblematik49,95 €
- Eduard BockTelematik im Personenverkehr54,99 €
- Anne M. SchüllerDie Orbit-Organisation34,90 €
- Supply Chain Management und Advanced Planning49,99 €
-
-
-
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.
Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
Produktdetails
- 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
- Herstellerkennzeichnung Die Herstellerinformationen sind derzeit nicht verfügbar.
- 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
- Herstellerkennzeichnung Die Herstellerinformationen sind derzeit nicht verfügbar.
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.-
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.-