Vorlesung Optimierung, SS 98
Optimierung

Veranstaltung: Vorlesung, SS 98
Professur: Komplexität und Algorithmen
Dozent: Prof. Dr. Torben Hagerup
Zeit und Ort: Mo 12-14 Uhr und Di 8-10 Uhr, SR 11
Übungen: Di 14-16 Uhr, SR 307
Erster Termin: Di 2. Juni, 8-10 Uhr
Studienabschnitt: Hauptstudium
Scheinerwerb: Bei bestandener Klausur
Voraussetzungen: Vordiplom. Grundlegendes Wissen über Matrizen, insbesondere Kenntnis der Gauß-Elimination
Inhalt: Bei einem Optimierungsproblem geht es darum, eine reelle Funktion unter bestimmten Nebenbedingungen zu maximieren oder zu minimieren. Aus der Schule kennen Sie Optimierungsprobleme in einer Variablen (Beispiel: Maximiere x³-4 x²+x-2 unter der Nebenbedingung -2<x<2). In der Vorlesung behandeln wir Optimierungsprobleme in vielen Variablen. Solche Probleme sind im allgemeinen sehr schwierig, und wir beschränken uns zunächst auf Probleme, die darin bestehen, eine lineare Funktion unter linearen Nebenbedingungen (Gleichungen oder Ungleichungen) zu maximieren oder zu minimieren, sogenannte lineare Programme. Der Simplexalgorithmus zur Lösung linearer Programme ist vielleicht der für die Praxis wichtigste Algorithmus schlechthin, und wir werden uns eingehend mit ihm befassen. In dem Umfang, wie es die Zeit erlaubt, wenden wir uns gegen Ende der Vorlesung sogenannten ganzzahligen linearen Programmen zu, in deren Lösungen alle Variablen ganzzahlig sein müssen. Man könnte zunächst denken, daß diese zusätzliche Forderung das Problem leichter macht; aber genau das Gegenteil ist der Fall, wie wir sehen werden.
Literatur: V. Chvátal, Linear Programming, W. H. Freeman and Company, New York, 1983.