Menu

• Team
  • Prof. Dr. Nicole Megow
  • Dr. Syamantak Das
  • Dr. Ruben Hoeksma
  • Franziska Eberle
  • Lukas Nölke
• Teaching
  • Scheduling Theory
  • Optimizing w. Uncertainty
  • Project: Shared Mobility
• Projects
• Research Seminar
• Offers

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.