Methoden Der Ganzzahligen Optimierung

ISBN-13: 9783709182987 / Niemiecki / Miękka / 2012 / 292 str.

Rainer E. Burkard

Spis treści

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.