Ein Beispiel

Die Klausuraufgabe aus Abschnitt 6.2 führt zu folgendem mathematisierten linearen Optimierungsproblem:

Variablenzuweisung:

Anzahl an verkaufter Vollmilchschokolade in kg: x mit x 0

Anzahl an verkaufter Zartbitterschokolade in kg: y mit y 0

Zielfunktion:

Z(x, y) = 10 x + 8 y; Z -> Max

Nebenbedingungen:

Kakao in kg: 3/10 x + 6/10 y 120

Milchpulver in kg: 2/10 x + 2/10 y 52

Zucker in kg: 5/10 x + 2/10 y 100

Für jede Nebenbedingung muß eine Schlupfvariable eingeführt werden, um aus den Ungleichungen Gleichungen zu machen. Sie läßt sich als Variable für die noch freie Kapazität bzgl. der von der Nebenbedingung beschriebenen "Ressource" auffassen. Zum Beispiel wäre als die noch übrige Menge an Kakao zu interpretieren. Mit der Einführung der Schlupfvariablen

0 erhält man:

3/10 x + 6/10 y + + 0 + 0 = 120

2/10 x + 2/10 y + 0 + + 0 = 52

5/10 x + 2/10 y + 0 + 0 + = 100

Z(x, y) = 10 x + 8 y + 0 + 0 + 0 ; Z -> Max

Mit der Nulllösung als Startlösung ist der Startgewinn = 0.

Daraus ergibt sich das Starttableau:

x	y					:

3/10	6/10	1	0	0	120	120 : 3/10 = 400
2/10	2/10	0	1	0	52	52 : 2/10 = 260
5/10	2/10	0	0	1	100	100 : 5/10 = 200

10	8	0	0	0	Z-0

Erster Pivotschritt:

Welche Informationen lassen sich dem Tableau entnehmen?

Die Zielzeile verrät, daß man pro kg Vollmilchschokolade einen höheren Gewinn (10 DM) erzielt als pro kg Zartbitterschokolade (nur 8 DM). Somit ist die erste Spalte die gesuchte Pivotspalte.

Berechnet man für diese Spalte die zugehörigen Verhältnisse , so erkennt man, daß dieses Verhältnis für die dritte Zeile (Die Zeile mit den Variablen wird nicht mitgezählt!) minimal ist (200). Dies ist die gesuchte Pivotzeile. Das gesuchte Pivotelement befindet sich also auf der Position (3, 1) und hat den Wert 5/10.

Die Zeile mit dem Pivotelement wird nun derart mit Hilfe des Gaußalgorithmus umgeformt, daß das Pivotelement den Wert 1 bekommt. Die daraus resultierende Zeile wird von den anderen Zeilen so abgezogen, daß die Koeffizienten der ersten Spalte über und unter dem Pivotelement zu Null werden.

Das resultierende Tableau lautet dann:

x	y					:

0	12/25	1	0	-3/5	60	60 : 12/25 = 125
0	3/25	0	1	-2/5	12	12 : 3/25 = 100
1	2/5	0	0	2	200	200 : 4/10 = 500

0	4	0	0	-20	Z-2000

Der Gewinn hat sich auf 2000 DM gesteigert. Dazu würden die Herstellung von 200 kg Vollmilchschokolade und 0 kg Zartbitterschokolade gehören. Außerdem wären noch 60 kg Kakao sowie 12 kg Milchpulver übrig. Der Zucker hingegen wäre vollständig verbraucht.

In der Zielzeile gibt es jedoch noch einen positiven Koeffizienten (4). Der Gewinn läßt sich somit noch weiter optimieren. Es folgt der zweite Pivotschritt:

Der positive Koeffizient 4 bestimmt die zweite Spalte als Pivotspalte. Berechnet man für diese Spalte die zugehörigen Verhältnisse , so erkennt man, daß dieses Verhältnis für die zweite Zeile minimal ist (100). Dies ist die gesuchte Pivotzeile. Das gesuchte Pivotelement befindet sich also auf der Position (2, 2) und hat den Wert 3/25. Mit Gaußumformungen analog der Beschreibung oben, ergibt sich als neues Tableau:

x	y

0	0	1	-4	1	12
0	1	0	25/3	-10/3	100
1	0	0	-10/3	-100/3	160

0	0	0	-100/3	-20/3	Z-2400

Dieses Tableau weist in der Zielzeile keine positiven Koeffizienten mehr auf. Somit ist das Optimum erreicht. Es beträgt 2400 DM, wie man der Zielzeile entnehmen kann.

Welche weiteren Informationen können wir dem Tableau entnehmen?

Es müssen 160 kg Vollmilchschokolde sowie 100 kg Zartbitterschokolade hergestellt werden. Außerdem haben wir noch 12 kg an freier Kapazität für den Kakao, während das Milchpulver und der Zucker ganz verbraucht sind. Das Milchpulver und der Zucker sind voll ausgelastet.

zurück