Kurs:Algorithmen und Datenstrukturen/Vorlesung/Lineare Optimierung

Lineare Optimierung

Auf dieser Seite wird die lineare Optimierung behandelt. Eine lineare Optimierungsaufgabe ist: Maximiere eine lineare Funktion in mehreren Variablen

$max{c}_1{x}_1+...+c_n{x}_n{c}_i,x_i\in ℝ\iff max{c}^{T}x$.

Die lineare Nebenbedingung sind gegeben als lineare Gleichungen:

$a_{11}{x}_1+...a_{1n}{x}_n=b_1$

...

$a_{m1}{x}_1+...a_{mn}{x}_n=b_m$

$\mathrm{\forall }i=1,...,n:x_i\ge 0$

Dies entspricht dem Gleichungssystem:

$Ax=b,x\ge 0,a\in {ℝ}^{mxn},b\in {ℝ}^m,x\in {ℝ}^n$

Doch ist das ausdrucksstark genug für unsere Probleme?

Umformung von Gleichungssystemen

Beliebige Systeme lassen sich in die Standardform übertragen.

• Minimieren ist wie maximieren: $min{c}^{T}x=max-c^{T}x$
• $\ge$ Bedingungen statt $\le$ Bedingungen: $a_i^{T}x\le b_i\iff -a_i^{T}x\ge -b$
• Gleichung zu Ungleichung: $a_i^{T}x=b_i\iff a_i^{T}x\ge b\wedge a_i^{T}x\le b_i$
• Ungleichung zu Gleichung (Schlupfvariablen einführen): $a_i^{T}x\le b_i\iff a_i^{T}x+s=b,s\ge 0$
• $x_i$ kann negativ sein: $x_i=s-t,s\ge 0,t\ge 0$

Beispiel Gewinnmaximierung

Eine Firma produziert zwei verschiedene Waren. Ware $x_1$ erbringt einen Gewinn von einem Euro. Ware $x_2$ erbringt einen Gewinn von 6 Euro. Die Frage hierzu lautet, welches Verhältnis von $x_1$ und $x_2$ führt zum größten Gewinn? Dazu gibt es zwei Nebenbedingungen:

• Die Firma kann täglich maximal 200 Einheiten der Ware $x_1$ produzieren und maximal 300 Einheiten der Ware $x_2$
• Insgesamt kann die Firma maximal 400 Einheiten pro Tag produzieren

Die Firma beschließt eine weitere Ware zu produzieren.

• Die Ware $x_3$ bringt einen Gewinn von 13 Euro.
• Die maximale Tagesproduktion liegt weiterhin bei 400 Einheiten.
• Für die Produktion von Ware $x_2$ und Ware $x_3$ wird dieselbe Maschine verwendet, allerdings ist der Produktionsaufwand für $x_3$ dreimal höher. Insgesamt kann die Maschine 600 Arbeitsschritte leisten.

Formuliere, die Zielfunktion: $max{x}_1+6\cdot x_2+13\cdot x_3$.

Anschließend formuliere die Nebenbedingungen:

$x_1\le 200$

$x_2\le 300$

$x_1+x_2+x_3\le 400$

$x_2+3\cdot x_3\le 600$

$x_1,x_2,x_3\ge 0$

Polyeder

Die Nebenbedingungen definieren ein drei-dimensionales Polyeder, in dem die optimale Lösung liegt.

Nun formen wir in die Normalform um:

$max{x}_1+6\cdot x_2+13\cdot x_3\to max{x}_1+6\cdot x_2+13\cdot x_3$

$x_1\le 200\to x_1+s_1=200$

$x_2\le 300\to x_2+s_2=300$

$x_1+x_2+x_3\le 400\to x_1+x_2+x_3+s_3=400$

$x_2+3\cdot x_3\le 600\to x_2+3\cdot x_3+s_4=600$

$x_1,x_2,x_3\ge 0\to x_1,x_2,x_3,s_1.s_2.s_3,s_4\ge 0$

Polyeder

Die Nebenbedingungen definieren nun ein Polyeder, in dem die optimale Lösung liegt.

Polyeder

Die Zielfunktion $c=x_1+6\cdot x_2$ ist eine Gerade. Nun wird die Gerade verschoben, bis das Maximum erreicht ist.

Die Linearen Optimierungsprobleme der Form

$max{c}^{T}x$

$(1)Ax=b;x\ge 0$

$(2)Ax\le b;x\ge 0$

besitzen genau dann eine endliche Optimallösung, wenn sie eine optimale Ecklösung (= „Ecke“ des zugehörigen Polyeders) besitzen. D.h. man muss zur Lösungsfindung nur die Ecken des Polyeders betrachten.