Teaching

Grundlagen der linearen Optimierung

Vorlesung im Sommersemester 2018


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, Schnittebenenverfahren und die Branch-and Bound Methode.

Dozent:
Assistent:
Prof. Dr. Nicole Megow (Email)
M.Sc. Franziska Eberle (Email)
Zeit & Raum:


VL: Mo 10-12 Uhr in Raum GW1 A1260 (Megow)
UE: Di 16-18 Uhr in Raum MZH 6190 (Eberle)
UE: Do 08-10 Uhr in Raum MZH 1470 (Eberle)
Start:
Montag, 9. April 2018
Prüfung, Fachgespräch:
Zur Terminvereinbarung bitte Email an Nicole Megow senden.

Es werden zwei Übungen angeboten. Eine davon ist speziell für Wirtschaftsinformatiker konzipiert mit verstärktem Anwendungsbezug. Weiteres dazu wird in der ersten Vorlesung am 9.4.2018 besprochen.
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.
[KT] Kleinberg, Tardos: Algorithm Design, Pearson, 2006. (studip)
Datum Thema Vorlesungsunterlagen
9. April Einführung, Lineare Optimierungsprobleme, Graphische Repräsentation Orga, Notizen, Kapitel 1 in [BT], [GKT]
16. April Standardform, Geometrie linearer Programme Folien, Kapitel 2 in [BT]
23. April Grundversion des Simplex Algorithus Folien, Notizen, Kapitel 2 in [GKT], 3.1-3.2 in [BT]
3. Mai Degenerierte Basislösungen, Kreiseln des Simplex, Tableau-Methode Folien, Notizen, Kapitel 2.4, 3.3 und 3.4 in [BT]
7. Mai Zwei-Phasen Simplex, Laufzeitverhalten Folien, Notizen, Kapitel 3.5 und 3.7 in [BT]
14. Mai Dualität, Dualitätssätze, Komplementärer Schlupf Folien + Notizen, Kapitel 4.1-4.3 in [BT], 4.1-4.3 in [GKT]
28. Mai Minimale Spannbäume (Prim, Kruskal), Kürzeste Wege (Dijkstra) Kapitel 4.5 (MST), Kapitel 4.4 und 6.8 in [KT]
4. Juni Flüsse und Schnitte in Netzwerken, max-flow min-cut Theorem Folien + Notizen
11. Juni Ellipsoid Methode, Separieren und Optimieren Notizen, Details in Kapitel 8 in [BT]
18. Juni Einführung ganzzahliger LPs, Schnittebenenverfahren Kapitel 10 und 11.1 in [BT], auch 6.1 und 6.2 in [GKT]

Zur Abgabe der Übungen soll bitte folgendes Deckblatt verwendet werden.
Übungsblatt Abgabe in der VL am Besprechung
Übung 0 und Wiederholung -- 9. April
Übung 1 16. April 16. und 17. April
Übung 2 23. April 24. und 26. April
Übung 3 3. Mai 8. und 10. Mai
Übung 4 14. Mai 15. und 17. Mai
Übung 5 22. Mai 22. und 24. Mai
Übung 6 und Daten 28. Mai 29. und 31. Mai
Übung 7 4. Juni 5. und 7. Juni
Übung 8 und Netzwerk 11. Juni 12. und 14. Juni
Übung 9 18. Juni 19. und 21. Juni
Übung 10 25. Juni 26. und 28. Juni