17.4.1  Lineare Optimierung

Unter dem Begriff Lineare Optimierung (oder auch Linearer Programmierung) versteht man die Maximierung (Minimierung) einer linearen Funktion unter Nebenbedingungen in Ungleichheitsform.
Beispiel (s. Sydsaeter, Mathematik für Wirtschaftswissenschaftler) :
Ein Bäcker hat 150 kg Mehl, 22 kg Zucker und 27,5 kg Butter zur Verfügung, um zwei Arten von Kuchen zu backen. Nehmen Sie an, daß für die Produktion eines Dutzends Kuchen der Sorte A bzw. B folgende Zutaten benötigt werden: .

.
Die Erlöse: Ein Dutzend verkaufter Kuchen A ergibt 20 Euro , ein Dutzend verkaufter Kuchen B ergibt 30 Euro .
Wieviele Dutzend Kuchen der Sorten A (entspricht x₁) und B (entspricht x₂) maximieren nun den Erlös ?
Die Zielfunktion lautet:
maxz = 20 x₁ + 30 x₂
mit den Nebenbedingungen

.
und den Nicht-Negativitätsbedingungen x₁≥ 0 und x₂ ≥ 0. Graphisch: .

---

Abbildung 89: Lösungsraum der Ungleichung

---

.

Um die Ungleichungen besser verarbeiten zu können, werden Schlupfvariablen y₁ ≥ 0, y₂ ≥ 0 und y₃ ≥ 0 eingeführt:

.
Die Schlupfvariable y₁ sagt z.B. aus, wieviel kg Mehl nicht verbraucht wurde.
Das Gleichungssystem hat 3 Zeilen und 5 Variablen. Entsprechend sind 2 Variablen frei wählbar.
Das Prinzip des Simplex-Verfahrens besteht darin, ausgehend von einem Eckpunkt (einer Basislösung) zu einem weiteren Eckpunkt (ebenso eine Basislösung) und damit zu immer größeren Werten von z zu gelangen, bis ein weiteres Anwachsen nicht mehr möglich ist.
Die entsprechenden Schritte in diesem Beispiel sind:

1. Erste zulässige Basislösung:
   x₁=0, x₂=0, y₁=150, y₂=22, y₃=27.5 ergibt z=0.
   
2. Verbesserung durch zunächst Festhalten von x₁=0 und Vergrößerung von x₂ , da Zielfunktion dadurch am stärksten steigt:
   Hierbei entstehen die Folgefragen:
   a) Um wieviel kann x₂ von 0 aus erhöht werden ?
   b) Welche der Variablen y₁, y₂ oder y₃ sollen wir auf 0 setzen ?
   Mit dem Versuch y₁ = 0 folgt aus (I₁), daß x₂=25.
   Mit dem Versuch y₂ = 0 folgt aus (II₁), daß x₂=44.
   Mit dem Versuch y₃ = 0 folgt aus (III₁), daß x₂=27.5. .
   Damit ist der kritische Punkt in Gleichung (I), denn mit x₂ > 25 wird y₁ < 0. x₂ hat damit als Obergrenze den Wert 25.
   Wir setzen also x₂ = 25 und damit y₁ = 0.
   
3. Neue Werte:
   x₁=0, x₂=25, y₁=0, y₂=9.5, y₃=2.5 ergibt z=750.
   
4. Umschreiben des Gleichungssystems, sodaß die Variablen, die nicht gleich Null gesetzt sind, durch die anderen Variablen ersetzt werden: .
   

   (I2)	x2	=	25.0	−	1/2 x1	−	1/6 y1
   (II2)	y2	=	9.5	−	3/4 x1	+	1/12 y1
   (III2)	y3	=	2.5	−	1/2 x1	−	1/6 y1

   .
   z = 20 x₁ + 30 x₂ = 20x₁+30· (25−1/2x₁− 1/6 y₁)
   z = 750 + 5 x₁ − 5 y₁
   
5. weitere Erhöhung von z durch Vergrößern von x₁ (mit y₁ wäre das kontraproduktiv; Deshalb y₁ = 0):
   a) Um wieviel kann x₁ von 0 aus erhöht werden ?
   b) Welche der Variablen x₂, y₂ oder y₃ sollen wir auf 0 setzen ?
   Mit dem Versuch x₂ = 0 folgt aus (I₂), daß x₁=50.
   Mit dem Versuch y₂ = 0 folgt aus (II₂), daß x₁= 38/3.
   Mit dem Versuch y₃ = 0 folgt aus (III₂), daß x₁=5. .
   Damit ist der kritische Punkt durch Gleichung (III₂) gegeben, und x₁ hat damit als Obergrenze den Wert 5.
   
6. Neue Werte:
   x₁ = 5, x₂ = 22.5, y₁=0, y₂=5.75, y₃=0 ergibt z=775.
   
7. Umschreiben des Gleichungssystems, sodaß die Variablen, die nicht gleich Null gesetzt sind, durch die anderen Variablen ersetzt werden: .
   

   (I3)	x1	=	5.0	+	1/3 y1	−	2 y3
   (II3)	x2	=	22.5	−	1/3 y1	+	y3
   (III3)	y3	=	5.75	−	1/6 y1	+	3/2 y3
   	z	=	775	−	10/3 y1	−	10 y3

   
   
8. Der Versuch, eine weitere Erhöhung von z durch Vergrößern von y₁ oder y₂ von Null aus zu erreichen, führt nicht zum Ziel. Ergebnis:
   x₁ = 5, x₂ = 22.5, z=775.
   

Lösung mit Maple:
with(simplex):
cnsts := {3*x+6*y <= 150, x+0.5*y <= 22, x+y <= 27.5}:
obj := -x+y+2*z:
maximize(obj, cnsts ∪ 0 <= x, 0 <= y, 0 <= z) oder:
maximize(obj, cnsts, NONNEGATIVE)oder:
maximize(obj, cnsts)
.
Beispiel 17 - 49 lp0190
Lösen Sie mit dem Simplex-Verfahren das Optimierungsproblem:
maxz = 3x₁ + 4x₂
3 x₁ + 2x₂ ≤ 6
x₁ + 4x₂ ≤ 4

.

Lösung ansehen .
.