Modulcode:	WI18
Englische Bezeichnung:	Linear and integer linear Optimization
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	unregelmäßig (WS09/10)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübungen, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (Sonstige)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Die lineare Programmierung ist ein wichtiges Hilfsmitel bei der Modellierung kombinatorischer Optimierungsprobleme. Diese Veranstaltung bietet eine Einführung in die Theorie, geht aber auch auf klassische, effiziente und approximative Lösungsalgorithmen und ihre Anwendbarkeit in der Praxis, insbesondere auch für Approximationsalgorithmen, ein.

Lernziele:

Die Studenten werden in die Lage versetzt, Optimierungsprobleme oder ihre Relaxierungen als lineare Programme darzustellen. Sie kennen mehrere Algorithmen zur Lösung linearer Programme (z.B. Ellipsoid, Simplex) mit ihren Vor- und Nachteilen und sind in der Lage, kleine Progamme mit dem Zwei-Phasen-Simplecalgorithmus manuell zu lösen. Sie könnenn aus dem Simplextableau auch Informationen über das Duale ablesen und kennen grundlegende Aussagen über den Zusammenhang von primalem und dualem Programm.

Lehrinhalte:

Grundformen linearer Programme; geometrische Interpretation; Simplexalgorithmus; primales und duales Programm; Ellipsoid-Algorithmus; approximative LP-Löser

Weitere Voraussetzungen:

Elementare Kenntnisse der Linearen Algebra sind hilfreich.

Prüfungsleistung:

Klausur oder mündliche Prüfung am Semsterende. Am Ende des WS 2009/2010 wird eine mündliche Prüfung stattfinden.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Christos H.Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity; Dover Pubn Inc, 2000. Klaus Jansen, Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit; de Gruyter, 2008. Bernhard Korte, Jens Vygen: Combinatorial Optimization: Theory and Algorithms; Springer, 2008.

Verweise:

Kommentar: