Veranstaltung: Lineare Optimierung

Nummer:
141219
Lehrform:
Vorlesung und Übungen
Verantwortlicher:
Prof. Dr.-Ing. Aydin Sezgin
Dozenten:
Prof. Dr.-Ing. Aydin Sezgin (ETIT), Dennis Michaelis (ETIT)
Sprache:
Deutsch
SWS:
3
LP:
3
Angeboten im:
Sommersemester

Termine im Sommersemester

  • Beginn: Freitag den 13.04.2018
  • Vorlesung Freitags: ab 12:30 bis 14.00 Uhr im ID 04/471
  • Vorlesung Freitags: ab 12:30 bis 14.00 Uhr im ID 04/459
  • Übung Freitags: ab 14:15 bis 15.00 Uhr im ID 04/471
  • Übung Freitags: ab 14:15 bis 15.00 Uhr im ID 04/459

Prüfung

Schriftlich

studienbegleitend
Prüfungsanmeldung: FlexNow
Beschreibung der Prüfungsleistung:

Es wird 5 Aufgabenblätter mit jeweils 3 theoretischen Aufgaben zu je 4 Punkten und zusätzlich 3 Programmieraufgaben zu je 10 Punkten geben. Die Prüfungsleistung ist erbracht, wenn bei den theoretischen Aufgaben 30 Punkte und bei den Programmieraufgaben 15 Punkte erreicht sind.


Ziele

In vielen technischen (aber auch nichttechnischen) Bereichen werden Lösungen für Probleme gesucht, bei denen auch immer gewisse Vorgaben oder Nebenbedingungen erfüllt werden müssen. Die Optimierung dient hierbei als systematisches Werkzeug zur effizienten Lösungsbestimmung. Die Studierenden beherrschen die Behandlung zentraler Aspekte der Linearen Optimierung. Dies sind:

  • die Modellierung von Problemen im Bereich der Informationstechnik (z.B. Leistungsallokation) sowie im Alltag (z.B. Rucksackproblem, Sudoku, Ernährung) als lineare Optimierungsprobleme
  • die Dualität sowie notwendige und hinreichende Bedingungen
  • Verfahren, die zur effizienten Bestimmung von Lösungen führen.

Inhalt

  1. Einleitung und Überblick
    • Motivation, Formulierung von linearen Problemen, Varianten, Beispiele, stückweise lineare Zielfunktionen
    • Graphische Darstellung und Lösung
    • Lineare Algebra: Überblick und Notation
  2. Geometrie der linearen Optimierung
    • Konvexe Mengen, Polyhedra, Extrempunkte
  3. Die Simplex-Methode
    • Optimalitätsbedingungen, Entwicklung, Implementierung
  4. Dualitätstheorie
    • Motivation, Duales Problem, Dualitätstheorem
  5. Spieltheorie
  6. Sensitivitätsanalyse (Lokale)
  7. Netzwerk-Fluss-Probleme
    • Formulierung, Probleme: Kürzester Pfad/Maximaler Fluss, Netzwerk-Simplex Algorithmus
  8. Innere-Punkt-Methoden
    • Affiner Skalierungsalgorithmus
  9. Ganzzahlige Optimierung
    • Formulierung
    • Methoden: Brunch and bound, cutting plane
  10. Anwendungen

Voraussetzungen

keine

Empfohlene Vorkenntnisse

Inhalte der Veranstaltung Mathematik 1

Materialien

Sonstige:

Literatur

  1. Boyd, S., Vandenberghe, L. "Convex Optimization", Cambridge University Press, 2004

Sonstiges

weitere Literatur:

  • Berstsimas, D., Tsitsiklis, J. N., "Introduction to linear optimization", Athena Scientific, 1997
  • Hamacher, H. W., Klamroth, K., "Lineare Optimierung und Netzwerkoptimierung", 2. Auflage, Vieweg Verlag, 2006

Skript zur Vorlesung: