Seminarankündigung
Lineare Optimierung
Termin: Montags 16.15-17.45 / Ort: GB IV - SR 318
Beginn: 20.4.1998
Veranstalter: Paul Fischer, GB IV, Raum 332, Tel.4684
Bei Optimierungsproblemen geht es darum, durch Wahl geeigneter
,,Handlungen'' den erreichbaren ,,Gewinn'' zu maximieren
(bzw. den ,,Verlust'' zu minimieren)
und dabei gewisse Restriktionen einzuhalten.
Wenn der Zusammenhang zwischen den Handlungen, dem Gewinn und den Restriktionen
komplex genug ist, wird die Lösung dieser Aufgabe beliebig schwierig.
Selbst wenn dieser Zusammenhang und die Restriktionen durch lineare
Funktionen beschreibbar sind (Lineares Optimierungsproblem),
bleibt die Aufgabe schwer.
Da dieses Problem aber von herausragender praktischer Bedeutung
ist, gibt es eine Reihe von Lösungsmethoden, die sich in der Praxis
bewährt haben.
In diesem Seminar soll die wahrscheinlich erfolgreichste dieser Methoden
erarbeitet werden. Es folgt im wesentlichen dem Buch Primal-Dual
Interior-Point Methods von Stephen J. Wright, SIAM Press, 1997,
Signatur b531/Wrig in der Mathematik-Bibliothek. Interessenten
mögen sich bitte bei mir melden.
Vortragsthemen:
- Einführung I: Was ist Lineare Optimierung? Problemstellung,
zentrale Begriffe, Lösungsmethoden, Beispiele.
Quellen: Wright S.1-4 und andere. ( Vergeben )
- Einführung II: Das Duale Problem, Problemformulierung, Beispiele.
Quellen: Wright S.5-20 und andere. ( Vergeben )
- Lineare Optimierung und Interior-Point-Methoden I.
Quelle: Wright S.21-35. ( Vergeben )
- Lineare Optimierung und Interior-Point-Methoden II.
Quelle: Wright S.36-48. ( Vergeben )
- Komplexitätstheoretische Aspekte. Quelle: Wright S.49-64.
- Die Methode der Potential-Reduktion. Quelle: Wright S.64-82. ( Vergeben )
- Pfad-Methoden. Quelle: Wright 83-106. ( Vergeben )
- Methoden mit unzulässigen inneren Punkten. Quelle: Wright S.107-126.
( Vergeben )
- Konvergenz und Endlichkeit der Methoden I.
Quelle: Wright S.127-138. ( Vergeben )
- Konvergenz und Endlichkeit der Methoden II.
Quelle: Wright S.139-156. ( Vergeben )
Weitere Literatur:
- Alexander Schrijver, Theory of Linear and Integer Programming,
Wiley, 1986.
- Ingo Wegener, Skript Operations Research, Kapitel 2, Uni Dortmund.
Fragen an: Paul Fischer
Last Update, 03-03-1998, Paul Fischer.