Viele praktische Fragestellungen lassen sich als lineare Optimierungsprobleme formulieren, bspw. in der Logistik (Warenfluss und Planung von Produktionsprozessen) oder in der Finanzwelt (Portfoliotheorie und Risikomanagement). In einem linearen Optimierungsproblem sind sowohl die Zielfunktion als auch die Nebenbedingungen, die die Menge der zulässigen Lösungen beschreiben, linear. Die Vorlesung gibt eine Einführung in die Theorie und Praxis der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Vorlesungsthemen sind u.a.: Modellierung und Struktur linearer Programme, Polyedertheorie, Optimalitätskriterien, Dualität, Simplex-Algorithmus, die Ellipsoid-Methode, und die Branch-and Bound Methode.
Dozent: Assistent: |
Prof. Dr. Nicole Megow (Email) M.Sc. Franziska Eberle (Email) |
---|---|
Zeit & Raum: |
VL: Di 14-16 Uhr in Raum MZH 1090 (Megow) ab 16.5. in Raum MZH 6210 (zu erreichen über den verlängerten Flur vorbei an Raum 6240) UE: Mo 12-14 Uhr in Raum MZH 1090 (Eberle) UE: Di 16-18 Uhr in Raum MZH 1100 (Eberle) |
Start: |
Mittwoch, 11. April 2017 Die erste Übung dient der Wiederholung und findet am 11. April 2017 statt. |
Prüfung/Fachgespräch: |
Terminvereinbarung bitte per Email. |
Datum | Thema | Vorlesungsunterlagen |
---|---|---|
11. April | Einführung, Graphische Repräsentation und Lösungen, Standardform | Orga, Kapitel 1 in [BT], [GKT] |
18. April | Konvexe Mengen, Extrempunkte, Polyeder | Kapitel 2 in [BT] |
25. April | Basis, Basislösung, eine Iteration des Simplexalgorithmus | Kapitel 2.3, 2.4 in [GKT], 2.2, 2.3 in [BT] |
2. Mai | Simplexalgorithmus | Kapitel 3.2 in [BT] |
9. Mai | Implementationen des Simplexalgorithmus, Tableau Methode | Kapitel 3.3 in [BT] |
16. Mai | Kreiseln, degenerierte Basislösungen, Finden einer zulässigen Lösung, 2-Phasen-Simplex | Kapitel 2.4, 3.4, 3.5 in [BT] |
23. Mai | Laufzeitverhalten des Simplex, duale Programme, Dualitätssätze | Kapitel 4.1-4.3 in [BT] |
30. Mai | Farkas Lemma, Satz vom komplementären Schlupf, weighted vertex cover | Kapitel 4.3-4.4 in [GKT] |
6. Juni | Primal-dualer Algorithmus für vertex cover, Max-Fluss-Min-Schnitt Theorem | Kapitel 5.1, 5.3 in [GKT] |
13. Juni | Keine Lehrveranstaltung. | |
20. Juni | Ford-Fulkerson Algorithmus, Ellipsoid Methode (Überblick), total unimodulare Matrizen | Kapitel 7.5, 8 in [BT] |
27. Juni | Branch- und Bound Algorithmen, Knapsack problem und TSP | |
4. Juli | Greedy und Lokale Suche für TSP, Schnittebenenverfahren (Chvatal-Gomory Cuts) |
Übungsblatt | Abgabe in der VL am | Besprechung |
---|---|---|
Wiederholung | -- | 11. April |
Übung 1 | 18. April | 18. und 24. April |
Übung 2 | 25. April | 25. April |
Übung 3 | 2. Mai | 2. und 15. Mai |
Übung 4 | 9. Mai | 15. und 16. Mai |
Übung 5 (neu 11. Mai) | 16. Mai | 16. und 22. Mai |
Übung 6 | 23. Mai | 23. und 29. Mai |
Übung 7
Daten für Übung 7 Modell aus dem Tutorium | 30. Mai | 30. Mai und 1. Juni |
Übung 8 | 6. Juni | 6. und 19. Juni |
Übung 9 | 20. Juni | 27. Juni |
Übung 10 Netzwerk für Übung 10 | 27. Juni | 3. Juli |
Übung 11 | 4. Juli | nach Absprache |
Literatur: | [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997. [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014. |
---|