Sommersemester 2005
Im ersten Teil der Vorlesung haben wir uns hauptsächlich mit linearen Programmen beschäftigt, d.h. solchen Optimierungsproblemen, bei denen eine lineare Zielfunktion über einem Polyeder maximiert oder minimiert werden sollte. Viele praktisch relevante Probleme lassen sich aber nur unzureichend durch eine lineare Zielfunktion und lineare Restriktionen alleine beschreiben. Bei vielen kombinatorischen Problemen sind z.B. nur ganzzahlige Lösungen sinnvoll. Dies motiviert als erstes Thema der Vorlesung die sogenannten ganzzahligen linearen Programme (ILP). Wir behandeln ganzzahlige Polyeder und beschreiben verschiedene Lösungsverfahren für ILPs. Danach betrachten wir allgemeine Optimierungsprobleme mit Nebenbedingungen und untersuchen zunächst Optimalitätskriterien. Wir werden sehen, unter welchen Voraussetzungen sich wesentliche Hauptergebnisse aus dem ersten Teil der Vorlesung (wie z.B. der Dualitätssatz) auf allgemeine restringierte Optimierungsprobleme übertragen lassen. Leider ist das Lösen ganzzahliger linearer Programme und natürlich auch allgemeiner restringierter Optimierungsprobleme algorithmisch wesentlich schwieriger als das Lösen linearer Programme. Daher thematisieren wir verschiedene Lösungsverfahren, die ggf. nur für Probleme mit spezieller Gestalt entwickelt wurden.
Es ist durchaus möglich, diese Vorlesung zu hören, ohne zuvor die ``Mathematische Optimierung I'' besucht zu haben.
Literaturhinweise:
- A. Schrijver, ``Theory of Linear and Integer Programming'', Wiley, Chichester, 1986.
- B. Korte, J. Vygen, ``Combinatorial Optimization: Theory and Algorithms'', Springer, 2002.
- C. Papadimitriou, K. Steiglitz, ``Combinatorial Optimization: Algorithms and Complexity'', Prentice Hall, 1982.
- H. Jongen, K. Meer, E. Triesch, ``Optimization Theory'', Kluwer, 2004.
- U. Faigle, W. Kern, G. Still, ``Algorithmic Principles of Mathematical Programming'', Kluwer, 2002.
- F. Jarre, J. Stoer, ``Optimierung'', Springer, 2004.
- A. Schrijver, ``Combinatorial Optimization: Polyhedra and Efficiency'', Springer, 2002.
- M. Bazaraa, H. Sherali, C. Shetty, ``Nonlinear Programming'', Wiley, 1993.
| Vorkenntnisse: | Grundstudium |
|
| Ort: | Gerhard-Konow-Hörsaal (im Arithmeum, Lennéstr. 2) | |
| Zeit: | Dienstags 14:15-15:45 Uhr |
|
|
|
Freitags 12:15-13:45 Uhr | |
| Beginn: | 12.04.2005 | |
| Übung: |
Dienstags 10:15-11:45 Uhr (Beginn: 19.04.2005) |
Übungsblätter
| Blatt 1: | ps,pdf | Abgabe: Freitag, 15. April 2005, vor der Vorlesung |
| Blatt 2: | ps,pdf | Abgabe: Freitag, 22. April 2005, vor der Vorlesung |
| Blatt 3: | ps,pdf | Abgabe: Freitag, 29. April 2005, vor der Vorlesung |
| Blatt 4: | ps,pdf | Abgabe: Freitag, 6. Mai 2005, vor der Vorlesung |
| Blatt 5: | ps,pdf | Abgabe: Freitag, 13. Mai 2005, vor der Vorlesung |
| Blatt 6: | ps,pdf | Abgabe: Freitag, 27. Mai 2005, vor der Vorlesung |
| Blatt 7: | ps,pdf | Abgabe: Freitag, 3. Juni 2005, vor der Vorlesung |
| Blatt 8: | ps,pdf | Abgabe: Freitag, 17. Juni 2005, vor der Vorlesung |
| Blatt 9: | ps,pdf | Abgabe: Freitag, 17. Juni 2005, vor der Vorlesung |
| Blatt 10: | ps,pdf | Abgabe: Freitag, 24. Juni 2005, vor der Vorlesung |
| Blatt 11: | ps,pdf | Abgabe: Freitag, 1. Juli 2005, vor der Vorlesung |
| Blatt 12: | ps,pdf | Abgabe: Freitag, 8. Juli 2005, vor der Vorlesung |
| Blatt 13: | ps,pdf | Abgabe: Freitag, 15. Juli 2005, vor der Vorlesung |