Optimierung & Operations Research

Überblick

Dozent: Florian Dahms, R 1-138

  • Vorlesung: Mittwoch 10:00-11:30 (1-314)
  • Übung: Dienstag 14:30-16:00 (1-312)
  • OLAT Link
  • Übungsaufgaben in Jupyter
  • Panopto
  • Mündliche Prüfung oder schriftliche Klausur

Referenzen

  • "Theory of Linear and Integer Programming", A. Schrijver

In diesem Kurs geht es um Methoden, mit denen wir schwierige Probleme optimal lösen können.

    Anwendungen:

  • Routen für LKW Flotten
  • Standortsuche für Fabriken
  • Produktionspläne
  • Stundenpläne
  • Personalpläne
  • Poker Strategie

Voraussetzungen

  • Lineare Algebra
  • Grundlagen der Programmierung

Vektoren

\[ a = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} \in \mathbb{R}^3 \]

\[ a^T = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \]

Punktprodukt

\[ a = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix} \quad b = \begin{bmatrix} 4 \\ 5 \\ 6 \end{bmatrix} \]

\[ a \cdot b = a^T b = 1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 = 32 \]

Matrizen

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \in \mathbb{R}^{2 \times 3} \]

\[ A^T = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix} \in \mathbb{R}^{3 \times 2} \]

Matrix-Vektor Produkt

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \quad b = \begin{bmatrix} 7 \\ 8 \\ 9 \end{bmatrix} \]

\[ A b = \begin{bmatrix} 1\cdot 7 + 2 \cdot 8 + 3 \cdot 9 \\ 4 \cdot 7 + 5 \cdot 8 + 6 \cdot 9 \end{bmatrix} = \begin{bmatrix} 50 \\ 122 \end{bmatrix} \]

Matrix-Matrix Produkt

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \in \mathbb{R}^{2 \times 3} \quad B = \begin{bmatrix} 7 & 10 \\ 8 & 11 \\ 9 & 12 \end{bmatrix} \in \mathbb{R}^{3 \times 2} \]

\[ A B = \begin{bmatrix} 1\cdot 7 + 2 \cdot 8 + 3 \cdot 9 & 1 \cdot 10 + 2 \cdot 11 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 8 + 6 \cdot 9 & 4 \cdot 10 + 5 \cdot 11 + 6 \cdot 12 \end{bmatrix} \\= \begin{bmatrix} 50 & 68 \\ 122 & 167 \end{bmatrix} \in \mathbb{R}^{2 \times 2} \]

Es gilt $(A B)^T = B^T A^T$

Geschichte

Im 1. ersten Weltkrieg optimierte Großbritannien ihren Flotteneinsatz mit mathematischen Methoden, um den Verlust durch deutsche U-Boote zu minimieren.

Im 2. Weltkrieg wurde "Operations Research" zur eigenen Disziplin mit etwa 1000 beschäftigten Personen in Großbritannien.

  • Positionierung und Einsatz des neuen Radar Systems
  • Koordination von Flugabwehr Geschützen
  • Koordination von Bomber Geschwadern
  • Optimierung von Produktionsketten
  • ...

Nach dem 2. Weltkrieg wurde viele der neuen Ansätze in der Industrie weiterverfolgt.

  • Petrochemie
  • Fluglinien
  • Logistik
  • Finanzwesen

Python

  • Eine der populärsten Programmiersprachen.
  • (relativ) leicht erlernbar.
  • Exzellente Bibliotheken für Data Science und Machine Learning.
  • Open Source
  • Verwende ich in der Mehrheit meiner Kurse.
Link Jupyter

Mehr Python Referenzen

Im Rahmen der Vorlesung verwenden wir vor allem 3 Bibliotheken:

Lokale Python / Jupyter Installation:
Anaconda

In der Vorlesung wechseln wir immer wieder zwischen mathematischer Notation und Python Code

$$\sum_{i=1}^n i x_i$$ 

            sum(i * x[i] for i in range(1, n + 1))

Achtung: Mathematiker starten Arrays bei 1,
Informatiker bei 0

$$\sum_{i=1}^n i x_i$$ 

            sum((i+1) * x[i] for i in range(n))

Übungen in Jupyter

Bei mehr als 50% der Übungspunkte bekommt ihr 0.3 Notenpunkte Bonus auf die Prüfung.