Forschungsinstitut für Diskrete Mathematik

Vorlesung "Lineare und Ganzzahlige Optimierung"

Wintersemester 2013/14


Klausureinsicht: Dienstag den 25.02.2014, 12--13 Uhr (c.t.), Konferenzraum der Diskreten Mathematik.
(jetzt doch alle an einem Termin). An diesem Termin werden auch Musterlösungen verteilt!

Die Abschlußklausur findet am 19.02.2014 von 9-11 Uhr im Großen Hörsaal der Mathematik statt


Diese Vorlesung eignet sich für das (3. oder) 5. Semester im Rahmen des Bachelorstudiengangs Mathematik und ist eine Wahlpflichtvorlesung im Bereich C (Diskrete Mathematik). Ferner kann die Vorlesung im Rahmen des Bachelorstudiengangs Informatik besucht werden. Nähere Informationen können hier gefunden werden.


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, 2006.
  • B. Korte, J. Vygen : Kombinatorische Optimierung: Theorie und Algorithmen. Springer, 2008.
  • 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.

Skript

Zu den Übungen


Professor Dr. S. Held


Last modified: Mon Jun 15 12:09:55 CET 2013