Forschungsinstitut für Diskrete Mathematik
Vorlesung "Lineare und Ganzzahlige Optimierung"
Wintersemester 2013/14
Diese Vorlesung eignet sich für
- das (3. oder) 5. Semester als Wahlpflichtvorlesung im Rahmen des Bachelorstudiengangs Mathematik im Bereich C (Diskrete Mathematik),
- als Foundations in Discrete Mathematics im Masterstudiengang Mathematik,
- als Wahlpflichtvorlesung im Rahmen des Bachelorstudiengangs Informatik.
Nähere Informationen können
hier gefunden werden.
Bei Bedarf wird die Vorlesung auf Englisch gehalten!
Zeit und Ort: Di, Do 12-14, Gerhard-Konow-Hörsaal,
Forschungsinstitut für Diskrete Mathematik,
Lennéstr. 2
Ziele: Verständnis der grundlegenden Zusammenhänge
der Polyedertheorie und der Theorie der linearen und ganzzahligen
Optimierung. Kenntnis der wichtigsten Algorithmen, Fähigkeit
zur geeigneten Modellierung praktischer Probleme als mathematische
Optimierungsprobleme und deren Lösung, Computerimplementierung.
Inhalte: Modellierung von Optimierungsproblemen als (ganzzahlige)
lineare Programme, Polyeder, Fourier-Motzkin-Elimination, Farkas' Lemma,
Dualitätssätze, Simplexverfahren, Netzwerksimplex, Ellipsoidmethode,
Bedingungen für Ganzzahligkeit von Polyedern, TDI-Systeme,
vollständige Unimodularität, Schnittebenenverfahren.
Voraussetzungen: Lineare Algebra und Algorithmische Mathematik
Literaturhinweise:
-
A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York,
1986.
-
V. Chvátal, Linear Programming, Freeman, New York, 1983.
-
B. Gärtner, J. Matousek, Understanding and Using Linear
Programming, Springer, Berlin, 2007.
- B. Korte, J. Vygen :
Kombinatorische Optimierung: Theorie und Algorithmen.
Springer, 2. deutsche Auflage, 2012.
- R. Ahuja, T. Magnanti, J. Orlin : Network Flows. Prentice-Hall 1993
Alle genannten Bücher sind in der
Bibliothek
des Forschungsinstituts für Diskrete Mathematik vorhanden
und auch ausleihbar.
Übungen: 2st., n.V.
Skript: vorläufiges altes Skript aus dem WS 11/12
Professor Dr. S. Held
Last modified: Tue Jun4 17:29:06 2013