tatsächlicher Inhalt der Vorlesung Lineare Optimierung

• Dienstag, 19.10.1999
• Begriff der mathematischen Optimierung
• Standort der mathematischen Optimierung im Umfeld des Problemlösens von Anwendungsaufgaben
• Standort der linearen Optimierung innerhalb der mathematischen Optimierung
• lineare Programme
• Transformation linearer Programme in Standardform
• Donnerstag, 21.10.1999
• Schlupfvariablen
• Verzeichnisse, Basisvariablen und Nichtbasisvariablen
• Pivotschritt im Simplex-Algorithmus als Äquivalenzumformung von Verzeichnissen
• Basislösungen
• Optimalitätstest
• Donnerstag, 28.10.1999
• Trennung von Modell und Daten
• Optimierungsmodelle
• Parameter
• Variablen
• Nebenbedingungen (Restriktionen)
• Modellieren und Lösen einfacher Probleme mit AMPL (Vorführung am Computer)
• Der Simplex-Algorithmus mit dem simplex-Paket in MAPLE (Vorführung am Computer)
• unbeschränkte lineare Programme
• Entartung
• Kreisen im Simplex-Algorithmus
• Dienstag, 2.11.1999
• Pivotschritt als Äquivalenzumformung von Verzeichnissen
• explizite Formeln für die Pivotoperation
• Basislösung in Matrixschreibweise
• Eindeutigkeit der Basislösung für eine gegebene Basis
• Endlichkeit des Simplexalgorithmus im nicht entarteten Fall
• Behandlung von Entartung:
• symbolische Störung
• lexikographische Zeilenauswahlregel
• Donnerstag, 4.11.1999
• Behandlung von Entartung:
• kleinste-Index-Regel
• Donnerstag, 11.11.1999
• duale lineare Programme
• schwache Dualität
• Dienstag, 16.11.1999
• starke Dualität
• Donnerstag, 18.11.1999 - entfällt
• Donnerstag, 25.11.1999
• geometrische Interpretation linearer Programme
• Polytope und Polyeder
• Ecken und Basislösungen
• Dienstag, 7.12.1999
• Beziehung zwischen Ecken und Basislösungen
• Donnerstag 9.12.1999
• Schrittzahl des Simplex-Algorithmus
• der Klee-Minty-Würfel
• Dienstag, 14.12.1999
• der Klee-Minty-Würfel
• Donnerstag, 16.12.1999 (entfallen)
• Donnerstag, 6. 1. 2000
• verschiedene Pivotregeln
• die Hirsch-Vermutung über den Durchmesser von Polytopen
• Dienstag, 11. 1. 2000
• Überblick über andere Ansätze zur linearen Optimierung
• die Ellipsoid-Methode
• innere-Punkte-Verfahren
• das revidierte Simplexverfahren
• Faktorisierung der Basis in Eta-Matrizen
• Simplexmultiplikatoren
• Donnerstag, 13. 1. 2000
• das revidierte Simplexverfahren
• Simplexmultiplikatoren als duale Variablen
• Spaltengenerierung
• Beispiel: Das Verschnittproblem
• Donnerstag, 20. 1. 2000
• das duale Simplexverfahren
• Herleitung aus der primalen Simplex-Algorithmus
• unabhängige direkte Interpretation
• Sensitivitätsanalyse; Ändern und Hinzufügen von Variablen und Restriktionen
• Dienstag, 25. 1. 2000
• ganzzahlige lineare Optimierung
• Branch-and-bound
• Relaxation
• Schranken
• Barbeitungsstrategien
• das Rucksackproblem
• Lösung der linearen Relaxation
• Donnerstag, 27. 1. 2000
• Flussprobleme
• Formulierung
• Flüsse und Schnitte
• Modellierung mit AMPL
• Dienstag, 1. 2. 2000
• Modellierung mit ganzzahligen linearen Programmen
• logische Probleme
• Standortprobleme
• Probleme mit Fixkosten
• NP-Vollständigkeit der ganzzahligen Optimierung
• Schnittebenen
• Chvátal-Gomory-Schnitte
• Gomory-Schnitte
• Donnerstag, 3. 2. 2000 - entfällt
• Dienstag, 8. 2. 2000
• die Ellipsoidmethode
• Beziehung zwischen Separation und Optimierung
• Donnerstag, 10. 2. 2000 - entfällt
• Dienstag, 15. 2. 2000
• vollständige Unimodularität
• Charakterisierung von linearen Programmen mit ganzzahligen Lösungen
• Der Satz von Heller und Tompkins
• Donnerstag, 17. 2. 2000
• randomisierte Algorithmen:
• Algorithmus von Seidel
• Algorithmus von Matousek, Sharir, Welzl