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/2 .
Um die Ungleichungen besser verarbeiten zu können, werden Schlupfvariablen
,
und
eingeführt:
| |
| () | | | | | | | |
| () | | | | | | | |
| () | | | | | | | |
| |
.
Die Schlupfvariable
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:
,
,
,
,
ergibt .
-
2.
- Verbesserung durch zunächst Festhalten von
und Vergrößerung von
, da Zielfunktion dadurch am stärksten steigt:
Hierbei entstehen die Folgefragen:
a) Um wieviel kann
von 0 aus erhöht werden ?
b) Welche der Variablen ,
oder
sollen wir auf 0 setzen ?
Mit dem Versuch
folgt aus (),
daß .
Mit dem Versuch
folgt aus (),
daß .
Mit dem Versuch
folgt aus (),
daß .
.
Damit ist der kritische Punkt in Gleichung (I), denn mit
wird .
hat damit als Obergrenze den Wert 25.
Wir setzen also
und damit .
-
3.
- Neue Werte:
,
,
,
,
ergibt .
-
4.
- Umschreiben des Gleichungssystems, sodaß die Variablen, die nicht gleich Null gesetzt sind,
durch die anderen Variablen ersetzt werden: .
| |
| () | | | | | | | |
| () | | | | | | | |
| () | | | | | | | |
| |
.
-
5.
- weitere Erhöhung von z durch Vergrößern von
(mit
wäre das
kontraproduktiv; Deshalb ):
a) Um wieviel kann
von 0 aus erhöht werden ?
b) Welche der Variablen ,
oder
sollen wir auf 0 setzen ?
Mit dem Versuch
folgt aus (),
daß .
Mit dem Versuch
folgt aus (),
daß .
Mit dem Versuch
folgt aus (),
daß .
.
Damit ist der kritische Punkt durch Gleichung
() gegeben,
und
hat damit als Obergrenze den Wert 5.
-
6.
- Neue Werte:
,
,
,
,
ergibt
.
-
7.
- Umschreiben des Gleichungssystems, sodaß die Variablen, die nicht gleich Null gesetzt sind,
durch die anderen Variablen ersetzt werden: .
| |
| () | | | | | | | |
| () | | | | | | | |
| () | | | | | | | |
| | | | | | | | |
| |
-
8.
- Der Versuch, eine weitere Erhöhung von
durch
Vergrößern von
oder
von Null aus zu erreichen, führt nicht zum Ziel. Ergebnis:
,
,
.
Lösung mit Maxima: .
.
.
.
.
.
.
.
.
.
ergiibt:
Lösung mit Maple:
oder:
oder:
.