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