Vorlesung Lineare Optimierung (3 Vo + 2 Ü) - WS 1999/2000

Günter Rote, Nicole Morawe

Inhalt:

Bei vielen Anwendungsproblemen geht es nicht darum, etwas auszurechnen, sondern man möchte unter mehreren Möglichkeiten die beste auswählen. Auch die meisten algorithmischen Fragestellungen in der Informatik sind oder enthalten Optimierungsprobleme. Lineare Optimierungsprobleme sind hierbei die einfachsten Modelle, und für die lineare Optimierung gibt es verschiedene gute Algorithmen, hinter denen auch eine schön entwickelte Theorie steht.
Ich werde die theoretischen Grundlagen (polyedrische Mengen, Basislösungen, Dualität) erarbeiten, Algorithmen darstellen (Simplex-Algorithmus, innere-Punkte-Verfahren, Ellipsoid-Methode), und eine Reihe von Anwendungen (Transportprobleme, Tschebyscheff-Approximation) diskutieren.

Einen Ausflug möchte ich in die diskrete Optimierung machen, die die ganzzahlige Optimierung und die kombinatorische Optimierung umfasst. Zur kombinatorischen Optimierung gehören die meisten interessanten Optimierungsprobleme, die in der Informatik auftreten, und die ganzzahlige Optimierung ist ein sehr mächtiges Werkzeug für viele angewandte Problemstellungen. Lineare Optimierung ist auch die Grundlage von vielen Näherungsalgorithmen für schwierige Probleme.
Die ganzzahlige Optimierung wird im darauffolgenden Semester in einer eigenen Vorlesung von Christoph Helmberg vertieft.

Vor allen in den Übungen möchte ich einen Aspekt betonen, der im Studium oft zu kurz kommt, nämlich die mathematische Modellbildung von Anwendungsproblemen. Sie geht der Problemlösung voraus. Dazu werden wir die Modellierungssprache AMPL einsetzen, mit der kleine und mittlere Optimierungsaufgaben formuliert und gelöst werden können. Im Lauf der Vorlesung wird die Benutzung von AMPL erläutert. Für die Benutzung des Systems sind keine Programmierkenntnisse erforderlich.

Zeit und Ort:

Vorlesung: Dienstag 10-12 Uhr, Donnerstag 16-18 Uhr. Seminarraum 055, Takustraße 9. Beginn: 19. Öktober 1999. Übung nach Vereinbarung.

Voraussetzungen:

Grundlegendes über Matrizen aus der linearen Algebra.

Literatur:

weiteres Material