Lineare Programmierung und Erweiterungen

Book by Dantzig G B

1. Der Begriff der linearen Programmierung.- 1-1 Einführung.- 1-2 Das Problem der Programmierung.- 1-3 Definition der linearen Programmierung.- 1-4 Klassifizierung von Programmierungsproblemen.- 1-5 Mathematische Programmierung und Automation.- 2. Ursprünge und Einwirkungen.- 2-1 Einflüsse des zweiten Weltkrieges.- 2-2 Wirtschaftsmodelle und lineare Programmierung.- 2-3 Mathematische Ursprünge und Entwicklungen.- 2-4 Industrielle Anwendungen der linearen Programmierung.- 3. Aufstellung eines linearen Programmierungsmodells.- 3-1 Grundbegriffe.- 3-2 Konstruktion des Modells.- 3-3 Ein Transportproblem.- 3-4 Beispiele von Mischungsproblemen.- 3-5 Ein Problem der Mischung von Produkten.- 3-6 Ein einfaches Lagerhaltungsproblem.- 3-7 Ausbildung auf der Arbeitsstätte.- 3-8 Das mathematische Problem der linearen Programmierung.- 3-9 Probleme.- 4. Lineare Gleichungs- und Ungleichungssysteme.- 4-1 Systeme von Gleichungen mit der gleichen Lösungsmenge.- 4-2 Kanonische Systeme.- 4-3 Lineare Ungleichungen.- 4-4 Die Eliminationsmethode von FOURIER und MOTZKIN.- 4-5 Lineare Programme in Ungleichungsform..- 4-6 Probleme.- 5. Die Simplexmethode.- 5-1 Der Simplexalgorithmus.- 5-2 Die zwei Phasen der Simplexmethode.- 5-3 Probleme.- 6. Beweis des Simplexalgorithmus und des Dualitätssatzes.- 6-1 Induktiver Beweis des Simplexalgorithmus.- 6-2 Äquivalente duale Formen.- 6-3 Beweis des Dualitätssatzes.- 6-4 Fundamentalsätze über Dualität.- 6-5 Multiplikatoren von LAGRANGE.- 6-6 Probleme.- 7. Die Geometrie linearer Programme.- 7-1 Konvexe Gebiete.- 7-2 Die Simplexmethode als steilster Anstieg entlang der Kanten.- 7-3 Die Simplexinterpretation der Simplexmethode.- 7-4 Probleme.- 8. Pivot-Operationen, Vektorräume, Matrizen und ihre Inversen.- 8-1 Theorie der Pivots.- 8-2 Vektorräume.- 8-3 Matrizen.- 8-4 Die Inverse einer Matrix.- 8-5 Der Simplexalgorithmus in Matrizenform.- 8-6 Probleme.- 9. Die Simplexmethode mit Benutzung von Multiplikatoren.- 9-1 Ein Beispiel mit Multiplikatoren.- 9-2 Die allgemeine Methode mit Benutzung von Multiplikatoren.- 9-3 Rechenregeln bei Benutzung von Multiplikatoren.- 9-4 Probleme.- 10. Endlichkeit der Simplexmethode bei Störung.- 10-1 Die Möglichkeit des Kreisens beim Simplexalgorithmus.- 10-2 Störung der Konstanten zur Vermeidung von Entartung.- 10-3 Probleme.- 11. Varianten des Simplexalgorithmus.- 11-1 Komplementäre primale und duale Basen.- 11-2 Die duale Simplexmethode.- 11-3 Ein selbstdualer parametrischer Algorithmus.- 11-4 Der primale-duale Algorithmus.- 11-5 Ein anderes Kriterium für Phase I.- 11-6 Probleme.- 12. Der Preisbegriff in der linearen Programmierung.- 12-1 Der Preismechanismus der Simplexmethode.- 12-2 Beispiele dualer Probleme.- 12-3 Die Vorzeichenvereinbarung bei Preisen.- 12-4 Erläuterung der Sensitivitätsanalyse.- 12-5 Probleme.- 13. Spiele und lineare Programme.- 13-1 Matrixspiele.- 13-2 Äquivalenz von Matrixspielen und linearen Programmen und der Minimaxsatz.- 13-3 Konstruktive Lösung eines Matrixspiels (ein anderer Beweis des Minimaxsatzes).- 13-4 Probleme.- 14. Das klassische Transportproblem.- 14-1 Geschichtliehe Übersieht.- 14-2 Elementare Transporttheorie.- 14-3 Algorithmus für das Transportproblem.- 14-4 Probleme.- 15. Optimale Zuordnung und andere Zuteilungsprobleme.- 15-1 Das Problem der optimalen Zuordnung.- 15-2 Zuordnung mit Überschuß und Defizit.- 15-3 Feste Werte und unzulässige Quadrate.- 15-4 Probleme.- 16. Das Umladeproblem.- 16-1 Eine äquivalente Formulierung des Modells.- 16-2 Die Äquivalenz von Transportproblemen und Umladeproblemen.- 16-3 Lösung eines Umladeproblems durch die Simplexmethode.- 16-4 Probleme.- 17. Netzwerke und das Umladeproblem.- 17-1 Graphen und Bäume.- 17-2 Interpretation der Simplexmethode mit Hilfe des Netzwerks.- 17-3 Das Problem des kürzesten Weges.- 17-4 Probleme.- 18. Variablen mit oberen Grenzen.- 18-1 Der allgemeine Fall.- 18-2 Das Transportproblem mit beschränkten Variablen und Verallgemeinerungen.- 18-3 Probleme.- 19. Maximaler Fluß in Netzwerken.- 19-1 Die Theorie von FORD und FULKERSON.- 19-2 Die Baummethode zur Lösung von Maximalflußproblemen.- 19-3 Probleme.- 20. Die Primale-duale Methode bei Transportproblemen.- 20-1 Einführung.- 20-2 Der Algorithmus von FORD und FULKERSON.- 20-3 Probleme.- 21. Das Problem der gewichteten Zuteilung.- 21-1 Die fast dreieckige Form der Basis.- 21-2 Die Graphenstruktur der Basis.- 21-3 Eine Teilklasse mit optimalen Basen von Dreiecksform.- 21-4 Probleme.- 22. Programme mit veränderlichen Koeffizienten.- 22-1 Das verallgemeinerte Programm von WOLFE.- 22-2 Bemerkungen über Spezialfälle.- 22-3 Probleme.- 23. Ein Dekompositionsprinzip für lineare Programme.- 23-1 Das allgemeine Prinzip.- 23-2 Gespräch über das Dekompositionsprinzip.- 23-3 Zentralplanung ohne vollständige Information am Zentrum.- 23-4 Dekomposition vielstufiger Programme.- 23-5 Probleme.- 24. Konvexe Programmierung.- 24-1 Allgemeine Theorie.- 24-2 Homogene Zielfunktionen und das Problem des chemischen Gleichgewichts.- 24-3 Konvex-separable Zielfunktionen.- 24-4 Quadratische Programmierung.- 24-5 Probleme.- 25. Ungewißheit.- 25-1 Planung unter Berücksichtigung variabler Kosten.- 25-2 Planung bei ungewisser Nachfrage.- 25-3 Über vielstufige Probleme.- 25-4 Probleme.- 26. Extremalprobleme mit diskreten Variablen.- 26-1 Überblick über die Methoden.- 26-2 GOMORYS Methode der ganzzahligen Formen.- 26-3 Über die Bedeutung der Lösung linearer Programmierungsprobleme, bei denen ganzzahlige Variablen auftreten.- 27. STIGLERs Ernährungsmodell, Beispiel einer Formulierung und Lösung.- 27-1 Probleme beim Aufstellen eines Modells.- 27-2 Numerische Lösung des Ernährungsproblems.- 27-3 Probleme.- 28. Das Aufstellen eines Flugplans bei ungewisser Nachfrage 28-1 Beschreibung und Formulierung.- 28-2 Numerische Lösung des Flugplanproblems.- Namenverzeichnis.