Forschungsinstitut für Diskrete Mathematik

Proseminar Diskrete Optimierung

Sommersemester 2003


Thema: Lineare Optimierung


In der Linearen Optimierung betrachtet man die folgende Aufgabenstellung: Zu einem gegebenen n-dimensionalen Kostenvektor c, einer m×n-dimensionalen Matrix A und einem m-dimensionalen Vektor b sucht man einen n-dimensionalen Vektor x, der unter der Nebenbedingung Ax <= b das Skalarprodukt cx minimiert.
Zahlreiche Optimierungsprobleme (z.B. viele Netzwerkfluß-Probleme) lassen sich in dieser allgemeinen Form darstellen. Daher ist die algorithmische Behandlung von linearen Optimierungsproblemen von großem praktischem Interesse. Die Untersuchung dieser Probleme führte aber auch zu theoretisch bedeutsamen Erkenntnissen über die Struktur von Polyedern. Das Proseminar will einen Einblick in die theoretischen Grundlagen und in die wichtigsten algorithmischen Konzepte der Linearen Optimierung geben. Behandelt werden dazu Teile des Buches Linear Programming von Vašek Chvátal (Freeman 1983, ISBN 0-7167-1587-2).
Termin: freitags 12-14 im Seminarraum des Instituts

Nr. Datum Name Thema Betreuung
1 2. 5. Immo Krupke Kapitel 1 und 2 sowie Auszüge aus 11 und 12
Dirk Müller
2 9. 5. Abdulsalam Al-Azazi Kapitel 3
Jürgen Werber
3 16. 5. Anette Lang Kapitel 5
Stephan Held
4 23. 5. Fabian Klingbeil Kapitel 7
Matthias Müller-Hannemann
5 30. 5. Steffen Stern Kapitel 9
Sven Peyer
6 6. 6. Daniel Gruhlke Kapitel 10 und Auszüge aus 11
Ulrich Brenner

Scheinkriterien:

2-seitige Ausarbeitung, erfolgreicher Seminarvortrag, regelmäßige Teilnahme an den Veranstaltungen und aktive Mitarbeit
Prof. Dr. B. Korte
Dr. M. Müller-Hannemann
Dr. J. Vygen