Methoden der Ganzzahligen Optimierung, Softcover reprint of the original 1st ed. 1972

Optimierungsaufgaben spielen in Wirtschaft und Technik eine immer wichtigere Rolle. Dabei gewinnen Probleme, in denen gewisse Variable nur diskrete Werte annehmen können, zunehmend an Bedeutung. Führen doch Optimierungsaufgaben, in denen Stückzahlen vorkommen oder in denen die Alternative "wahr" oder "falsch" auftritt, in natürlicher Weise auf ganzzahlige Optimierungsprobleme. Historisch gesehen waren es die Transport-und Zuordnungsprobleme, zu deren Lösung die ersten Verfahren entwickelt wurden. Diese Klasse von ganzzahligen linearen Programmen besitzt die wichtige Eigenschaft, daß sich bei Lösung des zugehörigen gewöhnlichen linearen Programmes bei ganzzahligen Ausgangswerten von selbst eine ganzzahlige Lösung ergibt. Bei anderen Typen von ganzzahligen Optimierungsaufgaben ist dies nicht der Fall. Das erste effektive Lösungsverfahren für allgemeine lineare ganz­ zahlige Optimierungsprobleme geht auf Gomory (1958) zurück. Seither wurden die verschiedensten Techniken angewendet, um solche Probleme möglichst gut zu lösen. Dazu gehören Enumerationsverfahren, kombina­ torische, geometrische und gruppentheoretische Überlegungen wie auch die Anwendung der dynamischen Optimierung. Welches dieser Verfahren für ein spezielles Problem das günstigste ist, ist bis heute noch ungeklärt. Im vorliegenden Buch werden nach Behandlung der mathematischen Grundlagen ganzzahliger Optimierungsprobleme sowie nach einer kurzen Einführung in die Theorie linearer Programme und in die Theorie der Dualität zunächst Transport-und Zuordnungsprobleme behandelt. Dabei werden auch neueste Entwicklungen berücksichtigt, wie etwa das Optimum­ Mix-Problem oder die Erstellung von Schulstundenplänen. Daran schließt sich eine Diskussion der Verfahren von Gomory an, wobei im besonderen auf das reinganzzahlige (zweite) Verfahren von Gomory Wert gelegt wurde.

1. Einführung.- 1.1 Mathematische Grundbegriffe.- 1.2 Optimierungsaufgaben.- 1.3 Graphen.- 2. Grundzüge der linearen Optimierung.- 2.1 Problemstellung und geometrische Interpretation.- 2.2 Theorie des Simple xalgorithmus.- 2.3 Der Simplexalgorithmus.- 2.4 Bestimmung einer zulässigen Ausgangslösung.- 2.4.1 Mehrphasenmethode.- 2.4.2 M-Methode.- 2.5 Das revidierte Simplexverfahren.- 3. Dualität.- 3.1 Duale lineare Programme.- 3.2 Ein dualer Algorithmus zur Lösung linearer Optimierungsaufgaben.- 4. Transport- und Zuordnungsprobleme.- 4.1 Problemstellung.- 4.2 Anwendung des Simplexverfahrens auf Transportprobleme.- 4.3 Aufsuchen einer Ausgangslösung.- 4.4 Der Transportalgorithmus.- 4.5 Varianten des Transportproblems.- 4.5.1 Transportaufgaben mit Defizit oder Überschuß.- 4.5.2 Transportaufgaben mit unzulässigen Feldern.- 4.6 Graphen und Transportprobleme.- 4.7 Kapazitierte Transportprobleme.- 5. Die Ungarische Methode zur Lösung des Zuordnungsproblemes.- 5.1 Die Ungarische Methode.- 5.2 Beweis des Satzes von König-Egerváry.- 5.3 Die Konstruktion minimaler Überdeckungen.- 5.4 Algorithmus und Beispiel zur Ungarischen Methode.- 5.5 Eine Variante der Ungarischen Methode.- 6. Spezielle Zuordnungsprobleme.- 6.1 Zuordnung mit Restriktionen.- 6.2 Ein nichtlineares Zuordnungsproblem.- 7. Die Verfahren von Gomory.- 7.1 Gomorys erster Algorithmus.- 7.2 Algorithmische Durchführung des ersten Verfahrens von Gomory.- 7.3 Der ganzzahlige Algorithmus von Gomory.- 7.4 Der gemischt-ganzzahlige Algorithmus von Gomory.- 7.5 Bemerkungen zum asymptotischen Algorithmus von Gomory.- 8. Branch und Bound-Methoden.- 8.1 Allgemeine Beschreibung der Branch und Bound-Methode.- 8.2 Das Verfahren von Land und Doig.- 8.3 Das Verfahren von Dakin.- 8.4 Das Verfahren von Driebeek.- 8.5 Eine Branch und Bound-Methode zur Lösung des Rundreiseproblemes.- 9. Die kombinatorischen Verfahren von Balas.- 9.1 Der additive Algorithmus.- 9.2 Die Filtermethode.- 10. Partition gemischt ganzzahliger Programme.- 10.1 Der Partitionsansatz von Benders.- 11. Das Rucksackproblem.- 11.1 Problemstellung und das Lösungsverfahren von Gilmore-Gomory.- 12. Primate Methoden.- 12.1 Die primale Methode von Young.- 12.2 Endlichkeitsbeweis zum primalen Verfahren von Young.- 13. Verfahren zur nichtlinearen, konvexen Optimierung.- 13.1 Das Schnittebenenverfahren von Kelley.- 13.2 Ein Verfahren zur gemischt-ganzzahligen, konvexen Optimierung.- 13.3 Das Verfahren von Künzi-Oettli.