Methoden der Ganzzahligen Optimierung

1. Front Matter

   Pages I-VIII

   PDF

2. Einführung

   • Rainer E. Burkard

   Pages 1-12

3. Grundzüge der linearen Optimierung

   • Rainer E. Burkard

   Pages 13-43

4. Dualität

   • Rainer E. Burkard

   Pages 44-53

5. Transport- und Zuordnungsprobleme

   • Rainer E. Burkard

   Pages 54-93

6. Die Ungarische Methode zur Lösung des Zuordnungsproblemes

   • Rainer E. Burkard

   Pages 94-114

7. Spezielle Zuordnungsprobleme

   • Rainer E. Burkard

   Pages 115-130

8. Die Verfahren von Gomory

   • Rainer E. Burkard

   Pages 131-169

9. Branch und Bound-Methoden

   • Rainer E. Burkard

   Pages 170-200

10. Die kombinatorischen Verfahren von Balas

    • Rainer E. Burkard

    Pages 201-224

11. Partition gemischt ganzzahliger Programme

    • Rainer E. Burkard

    Pages 225-231

12. Das Rucksackproblem

    • Rainer E. Burkard

    Pages 232-236

13. Primale Methoden

    • Rainer E. Burkard

    Pages 237-252

14. Verfahren zur nichtlinearen, konvexen Optimierung

    • Rainer E. Burkard

    Pages 253-279

15. Back Matter

    Pages 280-292

    PDF

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.

• Beweis
• Dualität
• Endlichkeit
• Optimierung
• Variable

• Institut für Angewandte Mathematik, Universität Graz, Österreich

  Rainer E. Burkard

Policies and ethics