Optimierung 1 und 2
Wintersemester 2006/07
Prof. Dr. Friedrich Eisenbrand
Die Vorlesungen am 9. und 11. Januar 2007 fallen aus.
Für Mathematiker sind beide Vorlesungen weiterführende Vorlesungen im Bereich der angewandten Mathematik. Es können für beide Vorlesungen Übungsscheine erworben werden (jeweils 2-stündig).
Für Informatiker ist die Vorlesung Optimierung 1 eine Veranstaltung im Modul II.2.1, Modelle und Algorithmen (3LP). Die Vorlesung Optimierung 2 ist eine Veranstaltung im Modul III.2.6 (3LP).
| Vorlesung | Dienstag 09:00-11:00 (H7) Donnerstag 09:00-11:00 (P1.401) |
| Übung | Donnerstag 11-13 (N5.235) Donnerstag 14-16 (J2.331) |
Prüfungen
Am Ende des Semesters wird es mündliche Prüfungen geben. Man kann sich über Optimierung 1 und Optimierung 2 sowohl getrennt (jeweils 2 Wochenstunden) als auch über den gesamten Stoff (4 Wochenstunden) prüfen lassen.
Es sind zwei Zeiträume füur die Prüfungen vorgesehen.
- Die Woche vom 15-19 Februar
- Die Woche vom 2-5 April
Zugelassen sind alle Teilnehmer der Vorlesung, die mindestens 50% der Übungspunkte erreicht haben.
Zur Terminvereinbarung wenden Sie sich bitte per e-mail an Friedrich Eisenbrand
Material
| 17. Oktober 2006 | Folien Lineare Programme, Standardform und Basisloesungen |
| 24. Oktober 2006 | Folien Schwache Dualität, Basiswechsel, reduzierte Kosten |
| 25. Oktober 2006 | Folien Simplexalgorithmus, Tableaumethode |
| 31. Oktober 2006 | Folien Perturbierung und lexikographische Pivotregel |
| 07. November 2006 | Mitschrift Der Duale Simplex Algorithmus |
| 09. November 2006 | Mitschrift Sensitivitätsanalyse |
| 14. November 2006 | Mitschrift Max (s,t)-Flüsse |
| 16. November 2006 | Mitschrift Edmonds & Karp, kürzeste Wege, Anfang kostenminimale Flüsse |
| 21. November 2006 | Mitschrift Definition MCNFP, Restnetzwerk, Zerlegung von Fluessen in Pfade und Zyklen |
| 23. November 2006 | Mitschrift Cycle cancelling, Augmentieren entlang eines Zyklus von minimalem mittleren Gewicht, erste Analyse |
| 27. November 2006 | Mitschrift Fortsetztung der Analyse des MMCCA, Beweis der starken Polynomialität |
| 30. November 2006 | Mitschrift Finden von minimalen Cost/Profit Zyklen, parametrische Suche |
| 5. Dezember 2006 | Ende Parametrische Suche. Siehe Mitschrift vom 30.11. Beginn Polyedertheorie |
| 7. Dezember 2006 | Mitschrift Polyedertheorie |
| 12. Dezember 2006 | Mitschrift Faces und ganzzahlige Polyeder |
| 14. Dezember 2006 | Unimodulare Matrizen und ganzzahlige Polyeder (siehe Mitschrift vom 12. Dezember) |
| 19. Dezember 2006 | Mitschrift TU-Systeme, und Anwendungen |
| 21. Dezember 2006 | Mitschrift Das Matching Polytop |
| 16. Januar 2007 | Mitschrift Das Ellipsoidverfahren |
| 18. Januar 2007 | Weiter mit Ellipsoidverfahren |
| 23. Januar 2007 | Ende Ellipsoidverfahren, Separationsproblem |
| 25. Januar 2007 | P und NP, siehe Skript von A. Schrijver |
| 30. Januar 2007 | NP-Vollständige Probleme, vorbereitende Sätze zu Satz von Cook |
| 1. Februar 2007 | NP-Vollständigkeit von SAT (Satz von Cook) |
| 6. Februar 2007 | NP-Vollständigkeit von: 3-SAT, Hamilton Zyklus, 3D-Matching, Subset Sum |
| 8. Februar 2007 | Ausblick auf kombinatorische Optimierung im nächsten Semester |
Übungen
Zusatzmaterial
Unter diesem Link können Sie ein Java-Programm herunterladen, mit dem das Ellipsoidverfahren an Hand zweidimensionaler Polyeder grafisch veranschaulicht werden kann. Je nach System lässt sich das Programm entweder per Doppelklick oder per "java -jar EllipsoidAlgorithm.jar" ausführen (wobei eine geeignete Java-Umgebung installiert sein sollte).
Rückfragen bzgl. Bugs etc. bitte an Thomas Rothvoß.
Literatur
- Vaek Chvátal, Linear Programming, W. H. Freeman & Company, New York, 1983.
- Dimitris Bertsimas & John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, MA, 1997.
- A. Schrijver, A Course in Combinatorial Optimization
- Martin Grötschel, Skript zur Vorlesung Lineare Optimierung (Algorithmische Diskrete Mathematik 2) (Technische Universität Berlin, WS 2003/04)
- Raimund Seidel, Skript zur Vorlesung Optimierung (Universität des Saarlandes, SS 2000)
- Friedrich Eisenbrand & Stefan Funke, Skript zur Vorlesung Optimierung (Universität des Saarlandes, SS 2003)