Mathematische Inhalte:

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 E₁ und E₂ hergestellt werden. Die Fertigung erfolgt auf zwei vollautomatisierten Fertigungsstraßen F₁ und F₂. 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 F₁ auch für einen anderen Betrieb benötigt wird und nur 20 Stunden pro Woche zur Verfügung steht, F₂ dagegen 40 Stunden. Eine genaue Kalkulation ergab, dass E₁ einen Deckungsbeitrag von S 1200.- pro Stück, E₂ 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 E₁ und y von E₂ 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 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.
1. Bestimme die veränderbaren Zellen, deren Werte so lange angeglichen werden sollen, bis ein Ergebnis ermittelt ist. (bis zu 200 veränderbare Zellen)
1. Bestimme Zellen mit Nebenbedingungen, die innerhalb bestimmter Grenzwerte liegen oder Zielwertforderungen erfüllen müssen. (bis zu 500 Nebenbedingungen)

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 P₁, P₂, P₃ und P₄ in drei Abteilungen A₁, A₂ und A₃. 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.."

• die Stückgewinne verändert werden
• die Fertigungszeiten verändert werden
• die Kapazitäten verändert werden.

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

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.