0

0/16

17 Anwendungen

0/16/3

17.4 lineare Un-Gleichungssysteme

0/16/3/0

17.4.1 Lineare Optimierung

0/16/3/0/0

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: .
.





SorteMehlZuckerButter




A 3 1.0 1
B 6 0.5 1




.
.
Die Erlöse: Ein Dutzend verkaufter Kuchen A ergibt 20 , ein Dutzend verkaufter Kuchen B ergibt 30 .
Wieviele Dutzend Kuchen der Sorten A (entspricht x1) und B (entspricht x2) maximieren nun den Erlös ↯
Die Zielfunktion lautet:
max z = 20x1 + 30x2
mit den Nebenbedingungen
3x 1+6.0x2 150.0
x1+0.5x2 22.0
x1+x2 27.5
.
und den Nicht-Negativitätsbedingungen x1 0 und x2 0.

Graphisch: .

0/16/3/0/1


PIC .

Abbildung 1: Lösungsraum der Ungleichung

0/16/3/0/2 .

Um die Ungleichungen besser verarbeiten zu können, werden Schlupfvariablen y1 0, y2 0 und y3 0 eingeführt:

(I1)y1+3x1+6.0x2 =150.0
(II1)y2+x1+0.5x2 =22.0
(III1)y3+x1+x2 =27.5
.
Die Schlupfvariable y1 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:
x1 = 0, x2 = 0, y1 = 150, y2 = 22, y3 = 27.5 ergibt z = 0.
2.
Verbesserung durch zunächst Festhalten von x1 = 0 und Vergrößerung von x2 , da Zielfunktion dadurch am stärksten steigt:
Hierbei entstehen die Folgefragen:
a) Um wieviel kann x2 von 0 aus erhöht werden ↯
b) Welche der Variablen y1, y2 oder y3 sollen wir auf 0 setzen ↯
Mit dem Versuch y1 = 0 folgt aus (I1), daß x2 = 25.
Mit dem Versuch y2 = 0 folgt aus (II1), daß x2 = 44.
Mit dem Versuch y3 = 0 folgt aus (III1), daß x2 = 27.5. .
Damit ist der kritische Punkt in Gleichung (I), denn mit x2 > 25 wird y1 < 0. x2 hat damit als Obergrenze den Wert 25.
Wir setzen also x2 = 25 und damit y1 = 0.
3.
Neue Werte:
x1 = 0, x2 = 25, y1 = 0, y2 = 9.5, y3 = 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 2x1-1 6y1
(II2)y2 =9.5-3 4x1+ 1 12y1
(III2)y3 =2.5-1 2x1-1 6y1
.
z = 20x1 + 30x2 = 20x1 + 30 (25 -1 2x1 -1 6y1)
z = 750 + 5x1 - 5y1
5.
weitere Erhöhung von z durch Vergrößern von x1 (mit y1 wäre das kontraproduktiv; Deshalb y1 = 0):

a) Um wieviel kann x1 von 0 aus erhöht werden ↯
b) Welche der Variablen x2, y2 oder y3 sollen wir auf 0 setzen ↯
Mit dem Versuch x2 = 0 folgt aus (I2), daß x1 = 50.
Mit dem Versuch y2 = 0 folgt aus (II2), daß x1 = 38 3 .
Mit dem Versuch y3 = 0 folgt aus (III2), daß x1 = 5. .
Damit ist der kritische Punkt durch Gleichung (III2) gegeben, und x1 hat damit als Obergrenze den Wert 5.

6.
Neue Werte:
x1 = 5, x2 = 22.5, y1 = 0, y2 = 5.75, y3 = 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 3y1-2y3
(II3)x2 =22.5-1 3y1+y3
(III3)y3 =5.75-1 6y1+3 2y3
z =775-10 3 y1-10y3

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

Lösung mit Maxima: .
load(simplex); .

u1 : x >= 0; .
u2 : y >= 0; .
u3 : 3 * x + 6 * y <= 150; .
u4 : x + 0.5 * y <= 22; .
u5 : x + y <= 27.5; .
ZF : 20 * x + 30 * y; .
NB : [u1,u2,u3,u4,u5]; .

maximize_lp(ZF,NB),numer; .

ergiibt: (%o24)[775.0, [y = 22.5,x = 5.0]] 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,NONNEGATIV E) oder:
maximize(obj,cnsts)
.

0/16/3/0/3 .
Beispiel 17 - 160
Lösen Sie mit dem Simplex-Verfahren das Optimierungsproblem:
max z = 3x1 + 4x2
3x1 + 2x2 6
x1 + 4x2 4

Lösung : .
Wir führen die Schlupfvariablen y1 und y2 ein und erhalten:
A 1 :y1+3x1+2x2 =6 B1 :y2+ x1 +4x2 =4 ,
mit x1,x2,y1,y2 0. .
Erste Basislösung:
x1 = 0,x2 = 0,y1 = 6,y2 = 4 z = 3x1 + 4x2 = 0.
z steigt stärker, wenn wir zunächst x2 erhöhen.
Für x1 = 0,y1 = 0 folgt aus A1, dass x2 = 3 (nicht zulässig wg. B1).
Für x1 = 0,y2 = 0 folgt aus B1, dass x2 = 1 (’kritischer Punkt’).
Daher: nächste Lösung aus B1:
y2 = 0,x2 = 1,x1 = 0,y1 = 4, z = 4.
Ausdrücken der von Null verschiedenen Variablen:
B2 :x2 =1-1 4x1-1 4y2 A2 :y1 =4-5 2x1+1 2y2 , .
was z = 3x1 + 4x2 = 3x1 + 4 - x1 - y2 = 4 + 2x1 - y2 ergibt.
Wir erhöhen x1 y2 = 0 .
Für y2 = 0 folgt aus A2, dass x1 = 4 (schlecht).
Für y2 = 0 folgt aus B2, dass x1 = 8 5 . .
Daher: nächste Lösung:
y2 = 0, und aus A2 folgt: x2 = 3 5,x1 = 8 5,y1 = 0,y2 = 0 z = 36 5 . .
Ausdrücken der von Null verschiedenen Variablen:
x1 = 8 5 -2 5y1 + 1 5y2 x2 = 3 5 + 1 10y1- 3 10y2 z =36 5 -4 5y1 -3 5y2 .
Durch Vergrößern von y1 oder y2 wird z kleiner. Daher:
x1 = 8 5,x2 = 3 5,z = 36 5 fertig.

.
0/16/3/0/4