Teaching

Einführung in die lineare Optimierung

Vorlesung im Sommersemester 2017


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.
Die Übung am Montag ist speziell für Wirtschaftsinformatiker mit verstärktem Anwendungsbezug.

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)

Bei Abgabe der Lösungen soll das Deckblatt verwendet werden.
Ü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.