Veranstaltung: Lineare Optimierung

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

Termine im Sommersemester

  • Beginn: Donnerstag den 11.04.2019
  • Vorlesung Donnerstags: ab 08:15 bis 09.45 Uhr im ID 04/471
  • Vorlesung Donnerstags: ab 08:15 bis 09.45 Uhr im ID 04/459
  • Übung Freitags: ab 12:30 bis 14.00 Uhr im ID 04/471
  • Übung Freitags: ab 12:30 bis 14.00 Uhr im ID 04/459

Prüfung

Prüfungsform:schriftlich + studienbegleitend
Prüfungsanmeldung:FlexNow
studienbegleitend
Beschreibung der Prüfungsleistung:

Es wird 5 Aufgabenblätter mit jeweils theoretischen Teilaufgaben mit insgesamt 12 Punkten und zusätzlich 4 Programmieraufgaben zu je 10 Punkten geben. Die Prüfungsleistung ist erbracht, wenn bei den theoretischen Aufgaben 30 Punkte und bei den Programmieraufgaben 20 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: