Vorlesung "Optimierung" - SS 2006

DozentInnen

Dr. Rene Beier		Bau 46 (MPI), Raum 312		"rbeier" ät "mpi-sb.mpg.de"
Dr. Bodo Manthey		E1 3, Raum 422		"manthey" ät "cs.uni-sb.de"

Termine

Vorlesung: Dienstag und Donnerstag, jeweils 14 - 16 Uhr, HS 003, Geb. E1 3

Erste Vorlesung im Semester:	Dienstag, 18. April 2006
Letzte Vorlesung im Semester:	Donnerstag, 20. Juli 2006


Mittsemesterklausur:	Donnerstag, 8. Juni 2006
Endklausur:
Nachklausur:

Benotung

Für die Vorlesung gibt es 9 benotete Leistungspunkte. Bedingung für die Vergabe ist die erfolgreiche Teilnahme an den Übungen sowie an den beiden Klausuren.
Vorläufiges Benotungsschema:

35 % Note der Mittsemesterklausur
65 % Note der Klausur nach der Vorlesung

Voraussetzung für die Teilnahme an den Klausuren ist das Erreichen von mindestens 50% der Punkte in den der entsprechenden Klausur vorangegangenen Übungen.

Inhalt

18.4.2006	Einleitung Einführung in die lineare Optimierung Anwendungen von linearen Optimierungsproblemen (LPs): Maximaler Fluss Minimaler Schnitt
20.4.2006	Anwendungen von LPs: Minimaler Schnitt Matching in bipartiten Graphen Standardform, kanonische Form von LPs, Umwandlungsregeln Basislösungen: Definition
25.4.2006	Basislösungen: Definition, Beispiele, Eigenschaften Geometrie linearer Optimierungsprobleme: Vektorräume Unterräume
27.4.2006	Geometrie linearer Optimierungsprobleme: Polytope
2.5.2006	Geometrie linearer Optimierungsprobleme: Polytope Äquivalenz von Basislösungen und Knoten Existenz optimaler BFS Simplex-Algorithmus, Finden besserer BFS
4.5.2006	Finden besserer BFS Tableaus Pivotieren
9.5.2006	Tableaus Phase 2 des Simplex-Algorithmus Degeneriertheit und Zyklen Pivotregel von Bland Phase 1 (Finden einer ersten BFS)
11.5.2006	Phase 1 (Finden einer ersten BFS) Simplex-Algorithmus im Überblick Geometrische Betrachtung des Pivotierens Dualität: Beispiele
16.5.2006	Dualität Schwache Dualität und Dualitätssatz Satz vom komplementären Schlupf Anwendungen: Kürzeste-Wege-Problem
18.5.2006	Anwendungen der Dualiät: Kürzeste-Wege-Problem Maximaler Fluss und Minimaler Schnitt Matching in bipartiten Graphen Primal-Dual-Algorithmus
23.5.2006	Primal-Dual-Algorithmus Primal-Dual-Algorithmus für das Kürzeste-Wege-Problem
30.5.2006	Primal-Dual-Algorithmus für das Kürzeste-Wege-Problem Primal-Dual-Algorithmus für das Fluss-Problem
2.6.2006	Bemerkungen zu Primal-Dual-Algorithmen Matching in allgemeinen und bipartiten Graphen Knotenüberdeckungen Heiratssatz (Satz von Hall) Satz von Kőnig und Egerváry
6.6.2006	Übung
08.6.2006	Mittsemesterklausur
13.6.2006	Primal-Dual-Algorithmus für das Matching-Problem Ungarischer Algorithmus
15.6.2006	Fronleichnam
20.6.2006	Ungarischer Algorithmus (Analyse)
22.6.2006	Laufzeit, Pivotregeln und Implementierung des Simplex-Algorithmus
27.6.2006	Die Ellipsoidmethode
29.6.2006	Die Ellipsoidmethode Ganzzahlige Programmierung NP-Vollständigkeit des ILP-Entscheidungsproblems Das Rucksackproblem
04.7.2006	Relaxation Perfektes Matching in allgemeinen Graphen Minimaler Spannbaum (Cutset- und Subtour-Formulierung)
06.7.2006	Das Problem des Handelsreisenden Totale Unimodularität
11.7.2006	Gomory-Cuts Branch and Bound (siehe Bertsimas/Tsitsiklis, Kap. 11.2, 11.2)
13.7.2006	Approximationsalgorithmen PCS - Precedence Constrained Scheduling SIT - Scheduling of Independent Tasks
18.7.2006	Das Rucksackproblem Pseudopolynomieller Algorithmus FPTAS Nemhauser/Ullman Algorithmus
20.7.2006	tba

Skript

Verkürztes Skript ohne Beweise und Beispiele (PDF, PS)

Hauptseite | Literatur | Übungen