kennen verschiedene Arten von Optimierungsproblemen und können sie im Anwendungskontext identifizieren
können praktische Probleme formal beschreiben und als lineare oder ganzzahlige Programme formulieren
kennen Techniken/Methoden (exakt, heuristisch, Polynomialzeit) zur Lösung von Optimierungsproblemen und können diese erklären und anwenden
können geeignete Lösungsmethoden inkl. Standardsoftware zum Lösen linearer und ganzzahliger Programme anwenden
kennen methodische Ansätze um die Güte von Lösungsverfahren zu bewerten
verstehen die analytische und geometrische Struktur linearer Programme sowie die Optimalitäts- und Dualitätstheorie
Lerninhalte
Das Modul gibt eine Einführung in die Methoden der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Vorlesungsthemen sind u.a.:
Mathematische Modellierung praktischer Fragestellungen (Transportprobleme, Zuweisungsprobleme, Packungs- und Überdeckungsprobleme, Netzwerkfluss- und Netzwerkdesignprobleme)
Lineare Programme, Struktur linearer Programme, Einblick in Polyedertheorie
Simplex-Algorithmus (Normalform, Basivariablen und Basislösungen, Optimalitätskriterium, Simplex Tableau, Zweiphasen-Simplex)
Sensitivitätsanalyse und Dualitätstheorie
Ganzzahlige lineare Programme, Komplexität, totale Unimodularität
Kombinatorische Lösungsmethoden (exakte Polynomialzeitalgorithmen) für ausgewählte Problemklassen wie bipartites Matching, minimaler Spannbaum, kürzester Weg
Branch-and Bound Methode
Schnittebenen-Verfahren
Optimierungssoftware CPLEX, FICO Xpress, GAMS
Prüfungsformen
Mündliche Prüfung; Notenbonus bei erfolgreicher Bearbeitung von Übungsaufgaben
Dokumente (Skripte, Programme, Literatur, usw.)
Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014
Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997
Informatik-Format