Teaching

Operations Research

Sommersemester 2019, 6CP
03-BB-699.01


Moderne betriebliche Informationssysteme nutzen verschiedene quantitative Verfahren aus der Informatik und Mathematik um Planungs- und Entscheidungsprozesse zu unterstützen. So lassen sich viele praktische Fragestellungen als (ganzzahlige) lineare Optimierungsprobleme formulieren: z.B. Warenfluss und Planung von Produktionsprozessen in der Logistik, Portfoliotheorie und Risikomanagement in der Finanzwelt sowie Netzwerkdesign und Routing in der Telekommunikation.

Die Vorlesung gibt eine Einführung in die grundlegenden Methoden der linearen und ganzzahligen linearen Optimierung. Themen sind: Mathematische Modellierung praktischer Fragestellungen (Entscheidungs-, Planungs- und Optimierungsprobleme), Struktur und Geometrie linearer Programme, Simplexverfahren, Komplexität, Dualität, Sensitivitätsanalyse; Methoden zum Lösen ganzzahliger linearer Probleme: Branch-and Bound Methode, Schnittebenen-Verfahren, Dynamische Programmierung und Greedy Verfahren; gundlegende kombinatorische Algorithmen für Graphen- und Netzwerkflussprobleme.

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


Vorlesung: Di 10-12 Uhr in Raum MZH 6210 (Megow)
Übung: Do 12-14 Uhr in Raum MZH 6340 (Eberle)
Betreute Rechnerübung: Do 14-16 Uhr in Raum MZH 3510 (Eberle) ab Ende April
Start:
Dienstag, 2. April 2019
In der Übung donnerstags von 12-14 Uhr werden die Übungsblätter besprochen. Der Termin von 14-16 Uhr ist die betreute Rechnerübung, in der die Studenten die Möglichkeit haben, die Programmieraufgaben zu lösen und gezielte Fragen zu stellen.
Die Übung am 27. Juni findet von 14:15 bis 15:45 in Raum MZH 3150 statt.
Datum Thema Vorlesungsunterlagen
2. April Einführung, Lineare Optimierungsprobleme, Graphische Repräsentation Orga, Folien
9. April Standardnormalform, Konvexität und Geometrie linearer Programme Folien, Notizen
16. April -- Osterferien --
23. April Simplex Algorithmus, Tableau Methode, Pivotregeln (Kreiselvermeidung) Folien, Notizen
30. April Zweiphasen-Simplex, Dualität Folien, Notizen
7. Mai Interpretation und Anwendungen zur Dualität, Einführung Begriffe zur Graphentheorie Folien, Notizen
14. Mai Ganzzahlige Lineare Programme, Primal-duale Algorithmen, totale Unimodularität, Netzwerkdesign (Min. Spannbaum) Folien, Notizen
21. Mai Kürzeste Wege Folien, Notizen
28. Mai Dynamische Programmierung: Kürzeste Wege und Rucksackproblem Folien, Notizen
4. Juni -- keine VL --
11. Juni Netzwerkflüsse, Ford-Fulkerson Alg, Max-Fluss Min-Schnitt Theorem Folien
18. Juni Kardinalitätsmaximale Matchings in bipartiten Graphen, stabile Matchings Folien, , Notizen
25. Juni Branch & Bound Verfahren, Beispiele: ILP, Knapsack, TSP Notizen
2. Juli Schnittebenen, Gomory-Chvatal, Schnittebenen-Verfahren Notizen
9. Juli Ausblick, Zusammenfassung, Prüfungsvorbereitung Folien

Geben Sie bitte bei Abgabe der Übungsblätter die Namen und Matrikelnummern aller Mitwirkenden ab.
Übungsblatt Abgabe in der VL am Besprechung
Übung 0 - 4. April
Übung 1, Chipsfabrik 9. April 11. April
Übung 2 23. April 25. April
Übung 3 30. April 2. Mai
Übung 4, Daten 7. Mai 9. Mai
Übung 5 14. Mai 16. Mai
Übung 6, Graph für Aufgabe 6.3 21. Mai 23. Mai
Übung 7 28. Mai 29. Mai
Übung 8 11. Juni 13. Juni
Übung 9 18. Juni 20. Juni
Übung 10, Daten 25. Juni 27. Juni
Übung 11 2. Juli 4. Juli
Übung 12 -- 11. Juli

Literatur:
  • [W] Winston, A.: Operations Research, Algorithms and Applications, Whiley & Sons, Duxbury Press, 2003.
  • [NSW] Nickel, Stein, Waldmann: Operations Research, Springer Gabler, 2. Auflage, 2014.
  • [DDKS] Domschke, W.; Drexl, A.; Klein, R.; Scholl, A.: Einführung in Operations Research, 5. Auflage, Springer, 2015.
  • [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
  • [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.