Lineare Programme

Beispiel:

Wir können Teig für 2 Typen von Muffins (A oder B) herstellen. Für diese können wir unterschiedliche Preise verlangen:

  • 60 Cent für je 100g von Typ A
  • 50 Cent für je 100g von Typ B

Die unterschiedlichen Teige haben eine unterschiedliche Zusammensetzung:

  • Teig A besteht zu 80% aus Mehl und 20% aus Schokolade.
  • Teig B besteht zu 50% aus Mehl und 50% aus Schokolade.

Wir haben folgende Mengen an Zutaten zur Verfügung:

  • 1500g Mehl
  • 900g Schokolade

Wie finden wir heraus, wie viel Teig von welchem Typ wir für maximale Einnahmen herstellen wollen?

Wir können die Menge an Teig (in Gramm) von Typ A mit $x_1$ und die Menge an Teig von Typ B mit $x_2$ bezeichnen.

Wir wollen also die Menge an Teig von Typ A und B bestimmen, die uns die maximale Einnahmen bringt:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \end{aligned} \] (Ertrag in Cent)

Wir haben 1500g Mehl. Teig A besteht zu 80% aus Mehl, Teig B zu 50%.

Was bedeuted das für $x_1$ und $x_2$?

$0.8 x_1 + 0.5 x_2 \leq 1500$

Wir können versuchen das zu visualisieren:

Die Gerade
$0.8 x_1 + 0.5 x_2 = 1500$
kreuzt die $x_1$-Achse bei
$x_1 = \frac{1500}{0.8} = 1875$
und die $x_2$-Achse bei
$x_2 = \frac{1500}{0.5}=3000$.

Wir dürfen natürlich auch weniger als das gesamte Mehl verwenden:

$\color{blue} 0.8 x_1 + 0.5 x_2 \leq 1500$

Analog haben wir 900g Schokolade. Teig A besteht zu 20% aus Schokolade, Teig B zu 50%.

$\color{red} 0.2 x_1 + 0.5 x_2 \leq 900$

Wir können natürlich nicht weniger als 0 Gramm von einem Teig herstellen:

$ x_1 \geq 0\\ x_2 \geq 0 $

Wir kennen jetzt die Menge mit allen möglichen Kombinationen an Teig, die wir herstellen können.

Welche bringt die größten Einnahmen?

Unser Ziel war:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \end{aligned} \]

Alle Mischverhältnisse in denen wir genau 500 Cent verdienen:
$0.6 x_1 + 0.5 x_2 = 500$

Richtung, in der wir mehr verdienen ist z.B. der Vektor \[ \begin{bmatrix} 0.6 \\ 0.5 \end{bmatrix} \qquad \text{oder} \qquad \begin{bmatrix} 6 \\ 5 \end{bmatrix} \]

Graphisch können wir nun das beste Teigverhältnis ermittlen:

  • $x_1 = 1000$
  • $x_2 = 1400$
  • Einnahmen:
    $0.6 \cdot 1000 + 0.5 \cdot 1400 = 1300$

Was wir aus der graphischen Lösung direkt auch noch sehen:

  • Wir verbrauchen in der Lösung 100% vom Teig.
  • Es gibt nur 3 mögliche Lösungen, die wirklich relevant sind.
  • Die Preise für die Teige können sich etwas ändern, ohne dass eine andere Lösung optimal wird.

Das ganze Problem zusammengenommen ließ sich so formulieren:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \text{subject to} \quad & 0.8 x_1 + 0.5 x_2 \leq 1500 \\ & 0.2 x_1 + 0.5 x_2 \leq 900 \\ & x_1 \geq 0 \\ & x_2 \geq 0 \end{aligned} \]

Diese Formulierung nennt man ein
Lineares Programm (LP).

    Ein LP hat folgende Struktur:

  • Es gibt mehrere, reell-wertige Variablen.
  • Wir wollen eine Zielfunktion maximieren oder minimieren.
  • Wir haben mehrere Nebenbedingungen mit $=$, $\geq$ oder $\leq$.
  • Zielfunktion und Nebenbedingungen sind linear.

Linear bedeutet, dass ein Term nur aus einer Summe besteht, und in jedem Summand maximal eine Variable vorkommen darf. Die Variable darf mit einem Faktor multipliziert werden.

Ein linearer Term kann graphisch immer als Gerade oder Ebene interpretiert werden.

    Linear:

  • $0.6 x_1 + x_2 - 5 x_3$
  • $7 x_1 \leq x_2 - 5 x_3 + 12$
  • $x_2 \geq \log(5)$

    • Nicht linear:

  • $4 x_1 + x_2 x_3$
  • $x_1^2 \leq 4$
  • $\log(x_2) \geq 5$

Was wollen wir mit LPs machen?

  • Große Industrieprobleme modellieren.
  • Optimale Lösungen finden.
  • Zusätzliches Wissen zu der Lösung generieren.

Wir können LPs auch vektorisiert ausdrücken.

Die Nebenbedingungen als Matrix-Vektor Produkt:

\[ \underbrace{ \begin{bmatrix} 0.8 & 0.5 \\ 0.2 & 0.5 \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} }_{x} \leq \underbrace{ \begin{bmatrix} 1500 \\ 900 \end{bmatrix} }_{b} \]

Die Zielfunktion als Vektor-Vektor Produkt:

\[ \max \quad {\underbrace{ \begin{bmatrix} 0.6 \\ 0.5 \end{bmatrix} }_{c}}^T \underbrace{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} }_{x} \]

Jedes lineare Programm können wir allgemein schreiben als:

\[ \begin{aligned} \max \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \]

Entscheidend ist, was in $A$, $b$ und $c$ steht.

Diese Schreibweise nennt sich kanonische Form.

Jedes LP kann in kanonische Form überführt werden.

$$\min \; c^T x \quad \Leftrightarrow \quad \max\; -c^T x$$

$$a^T x \geq b \quad \Leftrightarrow \quad -a^T x \leq -b$$
$$a^T x = b \quad \Leftrightarrow \quad a^T x \leq b \quad \text{und} \quad -a^T x \leq -b$$

Was ist, wenn wir nicht $x_i \geq 0$ haben wollen?

Wir können $x_i$ einfach durch $x_i^+ - x_i^-$ ersetzen.

\[ \begin{aligned} \max \quad & \underbrace{\begin{bmatrix} c_1 & c_2 & \cdots & c_n \end{bmatrix}}_{\color{blue} c^T} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix}}_{\color{blue} x}\\ \text{subject to} \quad & \underbrace{\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}}_{\color{blue} A} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix}}_{\color{blue} x} \leq \underbrace{\begin{bmatrix} b_1\\ b_2 \\ \vdots\\ b_m \end{bmatrix}}_{\color{blue} b} \\ & x \geq 0 \end{aligned} \]

Angenommen wir haben nun ein ganz allgemeines "Muffin" Problem:

  • Wir haben $n$ mögliche Rezepte $r_1, \ldots, r_n$.
  • Wir haben $m$ mögliche Zutagen $z_1, \ldots, z_m$.

\[ \begin{aligned} \max \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \]

  • $x_i$: Wieviel Teig von Rezept $r_i$ produzieren wir?
  • $c_i$: Ertrag für Rezept $r_i$.
  • $b_j$: Vorhandene Menge Zutat $z_j$.
  • $a_{ij}$: Anteil an Zutat $z_j$ in Rezept $r_i$.

Mit mehr als 3 Rezepten kommen wir mit der graphischen Methode nicht weiter. Wir brauchen einen allgemeineren Algorithmus.