geplanter Inhalt der Vorlesung Lineare Optimierung

• Einführung in die Theorie der linearen Optimierung und Simplexalgorithmus
• lineare Programme
• Standardform
• Simplexalgorithmus
• Entartung
• lexikographische Zeilenauswahlregel
• kleinste-Index-Regel
• Zwei-Phasen-Methode
• geometrische Interpretation linearer Programme und des Simplex-Algorithmus
• polyedrische Mengen
• Laufzeit des Simplexalgorithmus
• Dualität
• duale lineare Programme
• schwache und starke Dualität
• komplementärer Schlupf
• Erweiterungen des Simplexalgorithmus
• revidierter Simplexalgorithmus
• "Produktform der Inversen"
• das duale Simplexverfahren
• Sensitivitätsanalyse
• Spaltengenerierung
• Varianten des Simplexalgorithmus, andere Pivotregeln
• Die Criss-Cross-Methode
• randomisierte Algorithmen:
• Algorithmus von Seidel
• Algorithmus von Matousek, Sharir, Welzl
• die Algorithmen von Clarkson
• lineare Programme in kleiner Dimension
• Algorithmus von Megiddo
• Ganzzahlige lineare Programmierung
• branch-and-bound
• innere-Punkte-Methoden zur linearen Optimierung
• die Ellipsoid-Methode zur linearen und konvexen Optimierung
• Anwendungen
• Fluss- und Transportprobleme
• Tschebyscheff-Approximation

• Modellierung von Optimierungsaufgaben mit der Modellierungssprache AMPL
• Trennung von Modell und Daten