Forschungsinstitut für Diskrete Mathematik

Vorlesung "Mathematische Optimierung II"

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