• Home
• News
• People
• Open Positions
• Research
• Software
• Workshops
• Teaching
• Contact

Vorlesung "Lineare Optimierung"

Sommersemester 2011

Dozent

Dr. Stefan Körkel, Sprechstunde: nach Vereinbarung

Inhalt

• Lineare Optimierungsprobleme
• Beschreibung und Eigenschaften von Polyedern
• Dualitätstheorie
• Simplex-Algorithmus
• Polynomiale Algorithmen für LP
• Innere-Punkte-Methoden

Einordnung

Modul MD3 für Bachelor Mathematik und Master Anwendungsorientierte Informatik,
Kursusvorlesung für Diplom Mathematik

Voraussetzungen

Grundvorlesung Lineare Algebra

Zeit und Ort

Mittwoch, 9-11 und Freitag, 11-13
IWR, INF 368, SR 432
Beginn: Mittwoch, 13.4.2011

Übungsgruppen

Gruppe 1: Mittwoch, 11-13, IWR, INF 368, SR 248
Gruppe 2: Donnerstag, 14:00-15:30, Math. Inst, INF 288, HS 1
Erste Übungen: 4. bzw. 5.5.2011

Tutorin: Magdalena Gottfried

Scheinkriterien

• Regelmäßige Teilnahme an der Übungsgruppe
• 50% der Punkte aus den Übungsaufgaben
• Bestehen der Klausur am 27.7.2011, 9:00-11:00

Die Note setzt sich je zur Häfte zusammen aus den Übungspunkten und der Klausurnote, genauer siehe hier.

Klausurergebnisse und Noten

Personalisierte Abfrage hier.

Übungsaufgaben

• Blatt 1 vom 15.4.2011
• Blatt 2 vom 27.4.2011
• Blatt 3 vom 4.5.2011
• Blatt 4 vom 11.5.2011
• Blatt 5 vom 18.5.2011
• Blatt 6 vom 25.5.2011
• Blatt 7 vom 1.6.2011
• Blatt 8 vom 8.6.2011
• Blatt 9 vom 15.6.2011
• Blatt 10 vom 22.6.2011
• Blatt 11 vom 29.6.2011
• Blatt 12 vom 6.7.2011
• Blatt 13 vom 13.7.2011
• Alle Aufgabenblätter in einer Datei

Manuskript

• Kapitel 1: Lineare Optimierungsprobleme
• Kapitel 2: Polyeder
• Kapitel 3: Dualitätstheorie
• Kapitel 4: Struktur von Polyedern – Zusammenfassung
• Kapitel 5: Die Simplex-Methode (geometrische Version)
• Kapitel 6: Die Grundversion der Simplex-Methode
• Kapitel 7: Der duale Simplex-Algorithmus
• Kapitel 8: Postoptimale Analyse und Re-Optimierung
• Kapitel 9: Polynomiale Algorithmen zur linearen Optimierung
• Kapitel 10: Innere-Punkte-Verfahren
• Komplett in einer Datei (89 MB)

Literaturempfehlungen

• M. Padberg, Linear Optimization and Extensions, Springer
• V. Chvátal, Linear Programming, Freeman
• M. Grötschel, Skript Lineare und Ganzzahlige Programmierung, z.B. WS 2009/10, TU Berlin
• E. Kostina, Skript Lineare Optimierung, WS 06/07, Universität Marburg
• S. Wright: Primal-Dual Interior-Point Methods, siam
• Weitere Literatur wird im Verlauf der Vorlesung angegeben.