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 \mathbb {R} \Leftrightarrow maxc^{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}$

$\forall i=1,...,n:x_{i}\geq 0$

Dies entspricht dem Gleichungssystem:

$Ax=b,x\geq 0,a\in \mathbb {R} ^{mxn},b\in \mathbb {R} ^{m},x\in \mathbb {R} ^{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$
$\geq$ Bedingungen statt $\leq$ Bedingungen: $a_{i}^{T}x\leq b_{i}\Leftrightarrow -a_{i}^{T}x\geq -b$
Gleichung zu Ungleichung: $a_{i}^{T}x=b_{i}\Leftrightarrow a_{i}^{T}x\geq b\land a_{i}^{T}x\leq b_{i}$
Ungleichung zu Gleichung (Schlupfvariablen einführen): $a_{i}^{T}x\leq b_{i}\Leftrightarrow a_{i}^{T}x+s=b,s\geq 0$
$x_{i}$ kann negativ sein: $x_{i}=s-t,s\geq 0,t\geq 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}\leq 200$

$x_{2}\leq 300$

$x_{1}+x_{2}+x_{3}\leq 400$

$x_{2}+3\cdot x_{3}\leq 600$

$x_{1},x_{2},x_{3}\geq 0$

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}\leq 200\to x_{1}+s_{1}=200$

$x_{2}\leq 300\to x_{2}+s_{2}=300$

$x_{1}+x_{2}+x_{3}\leq 400\to x_{1}+x_{2}+x_{3}+s_{3}=400$

$x_{2}+3\cdot x_{3}\leq 600\to x_{2}+3\cdot x_{3}+s_{4}=600$

$x_{1},x_{2},x_{3}\geq 0\to x_{1},x_{2},x_{3},s_{1}.s_{2}.s_{3},s_{4}\geq 0$

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

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\geq 0~$

$(2)Ax\leq b;\ x\geq 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.