WS 00/01
Vorlesung: Lineare und kombinatorische Optimierung
Die Vorlesung wendet sich an Studierende der Mathematik, Informatik, Softwaretechnik,
Operations Research und Ingenieurwissenschaften, die sich mit Optimierungsproblemen und
ihren Lösungen vertraut machen wollen. Der Dozent ist Mathematiker, der sich mit
entsprechenden Fragen in der Industrie befasst.
| Vorlesung | 2V |
|---|
| Dozent: |
Dr. Manfred Schmelzer |
|---|
| Termin: |
Montags 8:30 - 10:00 Uhr, Beginn am 16.10.00 |
|---|
| Raum: |
Seminarsaal 1.026, Informatikgebäude, Breitwiesenstraße 20-22 |
|---|
Inhalt
Es wird eine Einführung in die lineare Programmierung (Simplexalgorithmus, Dualität) und
deren Zusammenhang zu kombinatorischen Optimierungsverfahren gegeben. Folgende Punkte
sollen insbesondere behandelt werden:
- Lineare Programmierung:
- schwache/starke Dualität von LP's, komplementärer Schlupf
- Lemma von Farkas
- Basislösungen/Polyeder
- Simplexalgorithmus (Optimalität, Simplextableau, Pivotschritt)
- Kreisen, "Blands rule"
- Primal-dualer Algorithmus
- Kombinatorik:
- Netzwerk/Fluss Probleme
- Kürzeste Wege Probleme (Netzplantechnik)
- Assignmentproblem (totale Unimodularität)
- Algorithmen (u.a. Kuhn-Munkres, Ungarischer Algorithmus)
Literatur:
Chvatal: Linear Programming, Freeman and Company. (1998)
Jungnickel: Graphen, Netzwerke und Algorithmen, BI. (1994)
Schrijver: Theory of linear and integer Programming, Wiley. (1998)
Papadimitriou, Steiglitz: Combinatorial Optimization: Algorithms and Complexity,
Prentice Hall. (1998)
Vorkenntnisse:
Kenntnisse in der linearen Algebra (Matrizenrechnung) werden vorausgesetzt.
Prüfung nach Absprache. Abhängig von der jeweiligen Prüfungsordnung.
Skript
Endversion vom 04.02.2001
als PS-File
Endversion vom 04.02.2001
als PDF-File
Impressum
Last modified: Fri Oct 6 15:45:59 CEST 2000
