Markus Paul, BHAK Schwaz
 
Extremwertprobleme mit EXCEL, Teil 1:
Lineare Optimierung und Extremwertaufgaben

Mathematische Inhalte:

Lineare Optimierung, Extremwertaufgaben Kurzzusammenfassung: Mit dem SOLVER von EXCEL steht ein Tool zur Verfügung, mit dem lineare und nichtlineare Extremwertprobleme gelöst werden können. Bei der linearen Optimierung kann dadurch der Simplexalgorithmus als Black Box eingesetzt werden. Lehrplanbezug: II. Jg. HAK (lineare Optimierung), IV. Jg. HAK (Extremwertprobleme) Mediales Umfeld: Tabellenkalkulation EXCEL; Datei: EX_Extr.xls 1. Lineare Optimierung

Entscheidungsprobleme, bei denen unter Einhaltung bestimmter Bedingungen (Restriktionen, Einschränkungen) aus einer Anzahl von Alternativen die unter bestimmten Gesichtspunkten optimale herauszufinden ist, bezeichnet man als Optimierungsprobleme.

Optimierungsprobleme haben die gleiche Grundstruktur:

1. Zielfunktion, die angibt, welche Größe maximiert oder minimiert werden soll, und

2. Restriktionen, die den zulässigen Wertebereich, die Definitionsmenge der Variablen begrenzen.

Vielen Entscheidungen in der Wirtschaft liegen Optimierungsprobleme zugrunde, die sich durch mathematische Modelle mit einer linearen Zielfunktion und linearen Restriktionen in Form linearer Gleichungen oder Ungleichungen beschreiben lassen. Diese bezeichnet man als Probleme der Linearen Optimierung.

Beispiel (aus: Kronfellner/Peschek, Angewandte Mathematik 3): Im neu errichteten Produktionsbetrieb eines Unternehmers sollen Espressomaschinen in zwei Ausführungen E1 und E2 hergestellt werden. Die Fertigung erfolgt auf zwei vollautomatisierten Fertigungsstraßen F1 und F2. Die folgende Tabelle gibt Aufschluss über die Bearbeitungszeit der Produkte auf den einzelnen Fertigungsstraßen:
Fertigungsstraße
Bearbeitungszeit im Min/Stück
 
E1
E2
F1
20
10
F2
10
40

Zu beachten ist, dass F1 auch für einen anderen Betrieb benötigt wird und nur 20 Stunden pro Woche zur Verfügung steht, F2 dagegen 40 Stunden. Eine genaue Kalkulation ergab, dass E1 einen Deckungsbeitrag von S 1200.- pro Stück, E2 einen Deckungsbeitrag von S 800.- pro Stück erzielen wird. Aus einer Studie weiß man, dass wöchentlich höchstens 75 Espressomaschinen abgesetzt werden können. Für welches Produktionsprogramm soll sich der Unternehmer unter dem Aspekt der Gewinnmaximierung entscheiden?

mathematisches Modell:

Wie viele Einheiten x von E1 und y von E2 müssen produziert werden, damit der Deckungsbeitrag und damit der Gewinn maximal wird?

Als Restriktionen sind dabei die durch die Kapazitäten der Fertigungsstraßen und die begrenzten Absatzmöglichkeiten gegebenen Nebenbedingungen zu beachten und weiters die Nichtnegativitätsbedingung: negative Produktionszahlen werden ausgeschlossen.

a) Grafische Lösung mit EXCEL: Probleme der Linearen Optimierung mit zwei Variablen lassen sich sehr anschaulich grafisch lösen: Bestimme die "Spurgeraden" (=Begrenzungsgeraden der Halbebenen) und zeichne diese im ersten Quadranten 

Die Schnittmenge der ersten drei Halbebenen definieren den zulässigen Bereich, den Simplex.

Die Zielfunktion ist ebenfalls linear:

yz = -1,5x + DB/800

Setzen wir DB = 0, so definiert yz eine Gerade durch den Ursprung. Nun erhöhen wir DB so weit wie möglich. Dadurch wird der Achsenabschnitt der Zielfunktion erhöht, die Zielfunktion wird parallel verschoben. Dies können wir so lange tun, bis der Rand des zulässigen Bereichs, in diesem Beispiel der Eckpunkt (45/30) erreicht ist. Dort ist DB am größten:

DB = 1200·45 + 800·30 = 78000

Um dies mit EXCEL zu realisieren, erstellen wir Wertetabellen für die drei Spurgeraden, der zulässige Bereich ergibt sich als Minimum der Werte der drei Spurgeraden. Die Spalte mit der Zielfunktion verknüpfen wir mit der Zelle für DB:

Nun verknüpfen wir noch die Zelle für DB mit einer Bildlaufleiste. Die Bildlaufleiste findet man im Menü "Ansicht" > Symbolleisten > Formular:

Mit der Maus wird die Bildlaufleiste aufgezogen und positioniert. Mit einem Klick der rechten Maustaste kann das Kontextmenü geöffnet werden, "Steuerelement formatieren" liefert eine Dialogbox, bei der die Ausgabeverknüpfung hergestellt werden muss:

Da der Maximalwert einer Bildlaufleiste 30000 ist, wir aber DB bis 100000 verschieben können sollten, transformieren wir den Wert der Bildlaufleiste in Zelle $G$1 in der Zelle $F$1 durch die Formel "=G1*1000".

Zuletzt erstellen wir ein Diagramm mit dem zulässigen Bereich und der Zielfunktion. Dazu eignet sich am besten der Diagrammtyp "Punkt (XY)" und der Untertyp "Punkte mit Linien ohne Datenpunkte". Nun verschieben wir DB im zulässigen Bereich mit der Bildlaufleiste so weit wie möglich (siehe Datei Linopt.xls):

Wir können die Zielfunktion bis in den Eckpunkt (45/30) verschieben. Hier hat DB das Maximum.

Dies führt zu folgender Tabelle im Maximum:
 
dx=
5
DB=
78000
x y1 y2 y3 zul.Bereich yz Zielfkt
0
120
60
75
60
97,5
5
110
58,75
70
58,75
90
10
100
57,5
65
57,5
82,5
15
90
56,25
60
56,25
75
20
80
55
55
55
67,5
25
70
53,75
50
50
60
30
60
52,5
45
45
52,5
35
50
51,25
40
40
45
40
40
50
35
35
37,5
45
30
48,75
30
30
30
50
20
47,5
25
20
22,5
55
10
46,25
20
10
15
60
0
45
15
0
7,5
65
-10
43,75
10
-10
0
70
-20
42,5
5
-20
-7,5

Der Tabelle kann man entnehmen, dass sich bei x = 45 die Geraden y1, y3 und yz schneiden bei y = 30.

b) Lösung mit EXCEL-Solver:

EXCEL verfügt neben der ZIELWERTSUCHE noch über ein weiteres leistungsstarkes Werkzeug, den SOLVER. Dieses Tool findet man im Menü EXTRAS. Falls der SOLVER dort nicht aufscheint, muss er über den ADD-In-Manager (ebenfalls Menü EXTRAS) aktiviert werden.

SOLVER löst Optimierungsprobleme, die sich mathematisch in einem System von (Un-) Gleichungen ausdrücken lassen:

  1. Bestimme die Zielzelle, deren Wert minimiert, maximiert oder auf einen bestimmten Wert festgesetzt werden soll.
  2. Bestimme die veränderbaren Zellen, deren Werte so lange angeglichen werden sollen, bis ein Ergebnis ermittelt ist. (bis zu 200 veränderbare Zellen)
  3. Bestimme Zellen mit Nebenbedingungen, die innerhalb bestimmter Grenzwerte liegen oder Zielwertforderungen erfüllen müssen. (bis zu 500 Nebenbedingungen)
Wir definieren das Optimierungsproblem in einer neuen Tabelle:

Das führt für die Anfangswerte x = 20 und y = 20 zu folgender Tabelle:
 
E1 E2
Anzahl
20
20
Summe Maximal
F1
20
10
600
1200
F2
10
40
1000
2400
Absatz
1
1
40
75
DB
1200
800
40000

Nun wird über das Menü EXTRAS der SOLVER aufgerufen und folgende Zuordnungen getroffen:

Die Nebenbedingungen müssen über HINZUFÜGEN durch folgendes Kontextmenü eingegeben werden:

Erteilt man nun den Auftrag LÖSEN, bringt der SOLVER folgende Lösung:
 
E1 E2
Anzahl
45
30
Summe Maximal
F1
20
10
1200
1200
F2
10
40
1650
2400
Absatz
1
1
75
75
DB
1200
800
78000

In diesem Beispiel ist die Lösung eindeutig. Wie reagiert nun der SOLVER, wenn es unendlich viele Lösungen gibt? Um dies auszutesten, lassen wir den zulässigen Bereich unverändert, ändern aber die Zielfunktion so ab, dass sie parallell zu einer der Spurgeraden ist, etwa parallel zu y3 mit der Steigung -1. Dies ist dann der Fall, wenn die Deckungsbeiträge von E1 und E2 gleich hoch sind. Wir setzen E1 auf 800. Dann ist jeder Punkt auf y3 zwischen den Eckpunkten (20/55) und (45/30) Lösung des Optimierungsproblems.

Nun starten wir den Solver mit verschiedenen Startwerten:

1. Startwert (40/40):
 
E1 E2
Anzahl
40
40
Summe Maximal
F1
20
10
1200
1200
F2
10
40
2000
2400
Absatz
1
1
80
75
DB
800
800
64000

Hier liefert der SOLVER die Lösung (45/30), einen Eckpunkt, der maximale DB beträgt 60.000:
 
E1 E2
Anzahl
45
30
Summe Maximal
F1
20
10
1200
1200
F2
10
40
1650
2400
Absatz
1
1
75
75
DB
800
800
60000

2. Startwert (20/60) liefert die Lösung (20/55), wieder mit 60.000 als maximalem DB

3. Startwert (30/40) liefert die Lösung (32,5/42,5), wieder mit 60.000 als maximalem DB

4. Startwert (0/0) liefert die Lösung (37,5/37,5), wieder mit 60.000 als maximalem DB

Man sieht: Der Solver ermittelt je nach Startwert beim nicht eindeutigen Lösungsfall nächstgelegene Randpunkte des zulässigen Bereichs als Lösung. Spätestens hier stellt sich die Frage: Wie funktioniert der SOLVER? In der Hilfe zum SOLVER finden sich einige Erläuterungen zum verwendeten Algorithmus: "Microsoft Excel Solver verwendet den nichtlinearen Optimierungscode GRG2 (Generalized Reduced Gradient), der von Leon Lasdon, University of Texas in Austin, und Allan Waren, Cleveland State University, entwickelt wurde.

Bei linearen und ganzzahligen Problemen werden die Simplexmethode, bei der die Variablen Beschränkungen unterliegen, und die Branch-and-bound-Methode verwendet, die von John Watson und Dan Fylstra bei Frontline Systems, Inc. entwickelt wurde. Weitere Informationen zu von Solver verwendeten internen Lösungsprozessen erhalten Sie unter folgender Adresse:

Frontline Systems, Inc.

P.O. Box 4288

Incline Village, NV 89450-4288

(702) 831-0300

Web-Site: http://www.frontsys.com (englischsprachig)

E-Mail: info@frontsys.com

Mit dem SOLVER können nun spielend auch Probleme mit mehr als zwei Variablen gelöst werden, die sich nicht mehr grafisch, sondern nur noch mit dem Simplexalgorithmus lösen lassen.

Beispiel 2 (aus: Kronfellner/Peschek, Angewandte Mathematik 3): Ein Betrieb erzeugt vier Produkte P1, P2, P3 und P4 in drei Abteilungen A1, A2 und A3. Der Stückgewinn der Produkte beträgt 5, 4, 3, 2 GE. Der folgenden Tabelle können die Fertigungszeiten der einzelnen Produkte und die Abteilungskapazitäten entnommen werden:
Abteilung
Fertigungszeit für
Kapazität
 
P1
P2
P3
P4
 
A1
8
3
4
2
300
A2
4
4
5
3
200
A3
2
6
3
5
250

Berechne das gewinnmaximale Produktionsprogramm! Versuche zuerst durch Probieren eine optimale Lösung zu finden, dann mit dem SOLVER!

Der Solver liefert die Lösung (30/20/0/0):
  P1 P2 P3 P4    
Anzahl
30
20
0
0
Summe Max
A1
8
3
4
2
300
300
A2
4
4
5
3
200
200
A3
2
6
3
5
180
250
Gewinn
5
4
3
2
230
 
Nun kann man die Schüler experimentieren lassen: "Was geschieht, wenn.."

Ein reiches Betätigungsfeld für experimentellen Unterricht!

Zu jeder Änderung der Ausgangsbedingungen findet man auf Knopfdruck das optimale Produktionsprogramm.

2. Extremwertprobleme mit zwei Variablen: "Extremwertaufgaben"

Mit dem SOLVER von EXCEL können auch nichtlineare Extremwertprobleme gelöst werden. Bei den klassischen "Extremwertaufgaben" erübrigt sich mit dieser Black-Box das Ableiten und Nullsetzen der Zielfunktion.

Beispiel 3 (aus: Steiner/ Weilharter: Mathematik 3): Es sind der Radius und die Höhe jenes geschlossenen zylindrischen Kessels mit V = 58 l Inhalt zu bestimmen, dessen Materialkosten minimal sind.

Eine Größe (hier: Oberfläche des Zylinders) in Abhängigkeit von zwei Variablen (hier: Radius und Höhe) soll optimiert (hier: minimiert) werden. Wir geben in der Zelle A2 für den Radius den Wert 2,5, in der Zelle B2 für die Höhe 3 ein. In Zelle C2 schreiben wir die Formel für das Volumen des Zylinders: V=r²ph (Nebenbedingung); in Zelle D2 die Formel für die Oberfläche des Zylinders: O=2rp(r+h) (Hauptbedingung, die zu minimierende Funktion). In EXCEL schaut das folgendermaßen aus:

Wir erhalten folgende Werte:
 
r h NB: V=58 HB: O > min
2,5
3
58,90486225
86,39379797

r und h wurden willkürlich gewählt, aber so, dass die Nebenbedingung V=58 annähernd erfüllt ist. (Die Konvergenz des SOLVERs hängt stark von der Güte des Näherungswerts ab!)

Nun lassen wird den SOLVER arbeiten: Die Oberfläche ist die Zielzelle D2, die minimiert werden soll; Radius und Höhe in A3 und B3 sind die veränderbaren Zellen; das Volumen in C2 soll als Nebenbedingung 58 sein, weiters sollen Radius und Höhe nicht-negativ sein:

Und schon erhalten wir mit dem Befehl "Lösen" die Lösung:

(Falls der Wert der Nebenbedingung zu ungenau sein sollte, kann die "Genauigkeit" des SOLVER in den OPTIONEN erhöht werden!)
 
r h NB: V=58 HB: O > min
2,0977
4,1954
58,0000
82,9468

Der Radius ist 2,098 dm, die Höhe ist 4,196, das ist genau der doppelte Radius. Die minimale Oberfläche beträgt 82,95 dm². Wir erhalten allerdings nicht die symbolische Lösung

wir erhalten "nur" die numerische Lösung!

Man erspart sich mit dem SOLVER somit das Herausrechnen einer Variablen aus der Nebenbedingung, das Einsetzen dieser Variablen in die Hauptbedingung, das Ableiten und Nullsetzen der Zielfunktion. Bei Aufgaben mit komplizierten Hauptbedingungen ist das ein entscheidender Vorteil.

Aber was ist, wenn der Schüler einen Fehler in den Ausgangsbedingungen macht? Dann ist er aufgeschmissen! Was in der Black-Box SOLVER passiert, ist nicht nachvollziehbar. Für solche Fälle empfiehlt es sich, schrittweise mit einem Computeralgebra-System (Mathcad!) die Rechenschritte nachzuvollziehen und das eigene Tun durch Graphiken und Wertetabellen bei jedem Schritt zu kontrollieren.

Dass derSOLVER aber in der Praxis höchst relevante Probleme löst, soll in einem weiteren Beitrag demonstriert werden: Der SOLVER löst nämlich das Portfolio-Problem: Wie müssen Aktien gemischt werden, dass das Risiko minimiert wird!

Literatur:

Maria Grünes: Lineare Optimierung mit EXCEL. Mathematik-Seminar "Intentionen des neuen Lehrplanes", Seefeld 1996.

Maria Grünes hat im Rahmen dieses Mathematik-Seminars die grafische Lösung mit der Bildlaufleiste in EXCEL vorgestellt.

Kronfellner/ Peschek: Angewandte Mathematik. Wien: HPT 1986.

Diesem Schulbuch sind die Aufgaben zur Linearen Optimierung entnommen.

Hanisch/ Reichel/ Müller/ Schak: Ist Gleich. HAK1. Wien: ÖBV HPT 1999.

Die lineare Optimierung mit dem SOLVER ist in diesem neuen Schulbuch eingearbeitet.