Lineare Optimierung in der Schule
mit GeoGebra
Diplomarbeit
im Lehramtsstudium Mathematik - Chemiezur Erlangung des akademischen Grades
Magistra der Naturwissenschaften
eingereicht an der
Fakultät für Mathematik, Informatik und Physik
der Universität Innsbruck
von
Theres Mair
Mai 2018
durchgeführt am Institut für Mathematik
der Universität Innsbruck
bei
Univ.-Prof. Dr. Tim Netzer
Few realize that linear programming is a revolutionary development that per-
mits us, for the first time in our long evolutionary history, to make decisions
about the complex world in which we live that can approximate, in some sen-
se, the optimal or best decision. [1, Foreword]
George B. Dantzig
Wenige erkennen, dass lineare Programmierung eine revolutionäre Entwick-
lung ist, die es uns zum ersten Mal in unserer langen Evolutionsgeschichte
ermöglicht, Entscheidungen über die komplexe Welt zu treffen, in der wir
uns befinden, die in gewisser Weise die optimale oder beste Entscheidung
sein kann. [1, Vorwort]
George B. Dantzig
Vorwort
Die folgende Diplomarbeit ist in zwei große Teile gegliedert. Im ersten Teil wird die
geschichtliche Entwicklung der linearen Optimierung beschrieben, aber auch die theore-
tischen und mathematischen Grundlagen dieses Zweiges der Mathematik werden behan-
delt. Damit ist eine allgemeine Beschreibung der Aufgaben und Lösungsmethoden für
lineare Optimierungsaufgaben möglich. Ich habe mich in dieser Arbeit auf jene Teilbe-
reiche der linearen Optimierung konzentriert, die auch im Schulunterricht relevant sind.
Andere mathematischen Aspekte blieben unberücksichtigt.
Der zweite Teil befasst sich mit der Anwendung der linearen Optimierung im Schulun-
terricht. Dabei werden einige Schulbeispiele exemplarisch gelöst. Bei der Lösung wird im
Unterricht auf moderne Technologien zurückgegriffen. Ich habe dazu die freie Software
GeoGebra ausgewählt und die genauen Schritte zur Lösung der Beispiele jeweils genau
erläutert.
Ich versuche das Thema in der Arbeit möglichst schülergerecht aufzubereiten, sodass
auch Lehrpersonen diese für die Vorbereitung des Unterrichts verwenden können. Eben-
so können auch Maturanten und Maturantinnen diese Arbeit zur Vorbereitung auf die
Reife- und Diplomprüfung verwenden. Dadurch soll ein tieferer Einblick in die mathe-
matischen Hintergründe der linearen Optimierung und ein genaueres Verständis möglich
sein.
Mein persönliches Interesse an diesem Thema entstand im Laufe meiner Lehrtätigkeit an
einer höheren Bundeslehranstalt für wirtschftliche Berufe. Dort konnte ich bereits Un-
terrichtserfahrung sammeln und auch das Thema der linearen Optimierung unterrichten.
Ich habe die Erfahrung gemacht, dass die Schüler und Schülerinnen dieses Thema im
Unterricht interessiert verfolgt haben. Das mag am praktischen Nutzen liegen. Vielleicht
lag es auch daran, dass ich mehr über diesen Teilbereich der Mathematik erfahren wollte.
Alle Bilder und Graphiken dieser Diplomarbeit wurden, wenn nicht anders angegeben,
selbst erstellt. Dazu habe ich die Software GeoGebra 5 verwendet.
Danksagung
Ich möchte an dieser Stelle all jenen danken, die mich beim Schreiben der Diplomarbeit
unterstützt haben.
Mein Dank gilt Herrn Univ.-Prof. Dr. Tim Netzer, der mein Thema mit Freude ange-
nommen und diese Arbeit betreut hat. Vielen Dank für die freundliche Hilfsbereitschaft
und die schnellen und positiven Rückmeldungen zu meinen Anliegen.
Ein großes Dankeschön möchte ich auch meiner Familie sagen, die mir mein Studium
ermöglicht und all meine Entscheidungen unterstützt haben. Die Ermutigungen und po-
sitiven Zusprüche waren sehr wichtig für mich. Vielen Dank auch an meine Familie für
das Korrekturlesen der Arbeit.
Inhaltsverzeichnis
Vorwort 5
Danksagung 7
1 Geschichtliche Entwicklung der linearen Optimierung 11
1.1 Die drei Begründer der linearen Optimierung . . . . . . . . . . . . . . . . 11
1.2 Erste Anwendungen und weitere Entwicklungen . . . . . . . . . . . . . . 13
2 Modellierung linearer Optimierungsaufgaben 15
3 Lösung linearer Optimierungsaufgaben 19
3.1 Mathematische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Lösung einer linearen Ungleichung in 2 oder mehreren Variablen . 20
3.1.2 Konvexe Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.3 Konvexe Polyeder . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Graphische Lösung linearer Programme . . . . . . . . . . . . . . . . . . . 25
3.2.1 Zulässiger Bereich . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.2 Optimale Lösung - Hauptsatz . . . . . . . . . . . . . . . . . . . . 27
3.2.3 Graphisches Lösungsverfahren für zwei Variablen . . . . . . . . . 28
3.2.3.1 Maximumsproblem . . . . . . . . . . . . . . . . . . . . . 28
3.2.3.2 Minimumsproblem . . . . . . . . . . . . . . . . . . . . . 30
3.2.4 Graphisches Lösungsverfahren für drei Variablen . . . . . . . . . . 31
Inhaltsverzeichnis
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren . . . . 33
3.3.1 Grundidee und Normalform . . . . . . . . . . . . . . . . . . . . . 34
3.3.1.1 Idee des Simplex-Verfahrens . . . . . . . . . . . . . . . . 34
3.3.1.2 Normalform eines linearen Programms . . . . . . . . . . 35
3.3.2 Einführendes Beispiel mit 2 Variablen . . . . . . . . . . . . . . . . 37
3.3.3 Allgemeine Formulierung des Simplex-Algorithmus . . . . . . . . 42
4 Anwendungsbeispiele 49
4.1 Beispiel 1 - Fruchtsäfte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Beispiel 2 - Gartenmaschinen . . . . . . . . . . . . . . . . . . . . . . . . 52
5 Lineare Optimierung im Schulunterricht 55
5.1 Gesetzliche Grundlage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 GeoGebra - die Geometrie Software . . . . . . . . . . . . . . . . . . . . . 57
5.3 Anwendung in der Schule . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.3.1 Lineare Ungleichungen und Ungleichungssysteme . . . . . . . . . 60
5.3.2 Lineare Optimierung - Maximumsaufgaben . . . . . . . . . . . . . 66
5.3.3 Lineare Optimierung - Minimumsaufgabe . . . . . . . . . . . . . . 75
5.3.4 Mehrdeutige Lösung bei der linearen Optimierung . . . . . . . . . 79
5.3.5 Maturaaufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3.5.1 Fruchtsäfte . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.5.2 Gürtelproduktion . . . . . . . . . . . . . . . . . . . . . . 85
6 Schlusswort 89
Literaturverzeichnis 91
10
1 Geschichtliche Entwicklung der
linearen Optimierung
In diesem Kapitel möchte ich einen kurzen Überblick zur geschichtlichen Entwicklung
der linearen Optimierung geben. Bereits der bekannte Mathematiker Leonhard Euler
(1707 - 1783) schrieb im Jahr 1744: Was immer in der Welt passiert, in seinem Inneren
hat es Maximum oder Minimum. Somit ist kein Zweifel, dass alle Naturphänomene über
die Methode des Maximierens oder Minimierens erklärt werden können [2].
Bei beinahe jedem Problem wird versucht unter minimalem Aufwand und/oder maxi-
malem Erfolg eine entsprechende Lösung zu finden. Das Optimieren erscheint als etwas
Natürliches und daher ist es auch nicht verwunderlich, dass in vielen Wissenschaftsbe-
reichen die Optimierung eine wichtige Rolle spielt [3, S.2].
Ich möchte in diesem einleitenden Kapitel nicht bis ins 18. Jahrhundert zurückgehen,
sondern mich auf den zeitlichen Abschnitt beschränken, in dem die lineare Optimierung
so entwickelt wurde, wie wir sie heute verstehen.
1.1 Die drei Begründer der linearen Optimierung
Der russische Mathematiker LEONID V. KANTOROVICH (1912 - 1986), der an der
Universität Leningrad unterrichtete, erhielt in den 1930er Jahren den Auftrag, sich mit
der mathematischen Modellierung und Optimierung der Produktion einer Furnierholz-
1.1 Die drei Begründer der linearen Optimierung
fabrik zu befassen. Im Jahre 1939 veröffentlichte er dazu ein Buch mit dem Titel „Eine
mathematische Methode der Produktionsplanung und Organisation und des besten Ge-
brauchs von ökomenischen Betriebsmitteln“. Die Bedeutung der Arbeit blieb beinahe
unerkannt. Durch die damalige politische Situation wurde das Buch im Westen nicht
verbreitet und auch im Osten wurde es nicht weiter beachtet. Kantorovich selber ver-
wendete den Ausdruck „Lineare Optimierung“ nicht [3, S.10-11].
Der Durchbruch der linearen Optimierung ist dem amerikanischen Mathematiker GE-
ORGE B. DANTZIG (1914 - 2005) zu verdanken. Er entwickelte die lineare Optimierung
so, wie wir sie heute kennen. Er verwendete bei der Modellierung von Optimierungsauf-
gaben als erster lineare Ungleichungen für ökonomische Beschränkungen und eine lineare
Zielfunktion. Im Jahre 1947 veröffentlichte er sein Buch „Modelling in a linear Struc-
ture“, in dem die Simplex-Methode vorgestellt wurde. Diese wird bis heute zur Lösung
von linearen Optimierungsaufgaben verwendet. Dantzig verwendete deshalb den Namen
Simplex-Methode, weil damit die Geometrie des Wechsels von einer Polyederecke zur
nächsten am besten beschrieben wird [3, S.13] (siehe dazu auch Abschnitt 3.3).
Als weiterer Begründer der lineare Optimierung gilt der amerikanische Ökonom und
Physiker TJALLING C. KOOPMANS (1910 - 1985), der in den Niederlanden gebo-
ren wurde. Er war an der Universität Yale und Stanford tätig und versuchte während
des zweiten Weltkrieges die Schifffahrtsrouten der Amerikaner zu optimieren [3, S.12].
Außerdem beschäftigte er sich mit Problemen der Ressourcenaufteilung.
Koopmans organisierte im Jahr 1949 das erste „Symposium on Mathematical Program-
ming“ in Chicago, an dem viele bekannte Mathematiker und Ökonomen teilnahmen [3,
S.13]. Bis heute finden diese Symposien in regelmäßigen Abständen statt, bei denen in
vielen Vorträgen die neuesten Entwicklungen auf dem Gebiet der Optimierung präsen-
tiert werden. Heuer findet das Symposium in Bordeaux statt (1. bis 6. Juli 2018).
Im Jahr 1975 erhielten L. Kantorovich und T. Koopmans für ihre Theorie der optima-
12
1 Geschichtliche Entwicklung der linearen Optimierung
len Ressourcenverteilung den Nobelpreis für Wirtschaftswissenschaften [4, IV]. Dadurch
wird deutlich welche Bedeutung die lineare Optimierung hat.
1.2 Erste Anwendungen und weitere Entwicklungen
In den 1940er und 1950er Jahren waren lineare Optimierungsaufgaben oft mit einem
enormen Rechenaufwand verbunden, da zur Lösung noch keine Computer zur Verfügung
standen.
Im Jahr 1949 wurde der Ökonom G. J. STIEGLERmit dem Diäten - Problem beauftragt.
Er sollte eine möglichst kostengünstige Nahrungszusammensetzung für Soldaten der US
- Army finden. Dazu stellte er eine lineare Optimierungsaufgabe mit 9 Ungleichungen
und 77 Variablen auf [3, S.18]. Zur Lösung wurden neun Personen und insgesamt ca. 120
Tage Rechenarbeit benötigt.
Ein wichtiges Anwendungsgebiet war damals auch die Petro - Industrie. So wurden linea-
re Optimierungsaufgaben verwendet, um die Spaltung von Erdöl in Benzin und andere
hochwertige Rohöle zu optimieren.
Durch den technischen Fortschritt war es im Jahr 1956 bereits möglich, lineare Opti-
mierungsaufgaben mit mehr als 200 Ungleichungen und 1000 Variablen in ungefähr fünf
Stunden zu lösen [4, IV]. Dazu wurde der Großrechner IBM 704 verwendet, der 1954
präsentiert wurde.
In den 1960er und 70er Jahren wurden andere Richtungen der Optimierung erforscht. Da-
zu zählt zum Beispiel die nichtlineare Optimierung, bei der nicht-lineare Ungleichungen
zur Modellierung dienen und auch die Zielfunktion nicht-linear ist. Weiters unterscheidet
man noch zwischen globaler, diskreter oder stochastischer Optimierung [3, S.25].
Ich möchte hier allerdings nicht näher auf die weiteren Teilbereiche der Optimierung ein-
gehen, da ich mich im Weiteren nur mit der linearen Optimierung beschäftigen möchte.
13
1.2 Erste Anwendungen und weitere Entwicklungen
Neben dem Begriff lineare Optimierung wird auch lineare Programmierung verwendet.
Dabei versteht man unter Programmierung so viel wie Planung.
14
2 Modellierung linearer
Optimierungsaufgaben
Ich möchte zu Beginn dieses Abschnitts ein einfaches Beispiel anführen. Beispiele dieser
Art werden sehr oft im Schulunterricht bearbeitet.
Eine Firma stellt zwei Sorten von Säften her.
Die Abfüllmaschine für die erste Sorte schafft höchstens 1000 Flaschen am Tag. Die Ma-
schine für die zweite Sorte höchstens 1300 Flaschen am Tag. Täglich können insgesamt
höchstens 1900 Flaschen abgefüllt werden.
Der Gewinn für eine Flasche der ersten Sorten beträgt e0,60. Für die zweite Sorte be-
trägt der Gewinn pro Flasche e0,40.
Ermitteln Sie wie viele Flaschen die erste bzw. zweite Maschine erzeugen muss, damit
die Firma einen größtmöglichen Gewinn erzielt.
Zur Lösung des Problems werden zuerst Variablen festgelegt, damit der Produktions-
prozess beschrieben werden kann.
Es sei
x... Anzahl der Flaschen, die Maschine 1 herstellt
y... Anzahl der Flaschen, die Maschine 2 herstellt.
Da die Flaschenanzahl nicht negativ sein kann, müssen die sogenannten Nichtnegativi-
tätsbedingungen erfüllt sein:
x ≥ 0
y ≥ 0
Durch die Angabe der höchstmöglichen Leistungen der Abfüllmaschinen, ergeben sich
die einschränkenden Bedingungen:
x ≤ 1000
y ≤ 1300
x+ y ≤ 1900
Unter diesen fünf Bedingungen, soll der Gewinn der Firma, der durch die sog. Zielfunk-
tion 0, 60x+ 0, 40y = Z(x, y) gegeben ist, möglichst groß sein.
Am obigen Beispiel lässt sich bereits erkennen, dass die lineare Optimierung in der
Wirtschaft eine große Rolle spielt. Entscheidungsprobleme sollen durch mathematische
Methoden rechnerisch optimal gelöst werden. Falls der Wert der Zielfunktion möglichst
groß sein soll, spricht man von einem Maximumsproblem; wird ein möglichst kleiner
Wert der Zielfunktion verlangt, von einem Minimumsproblem. Die Aufgabe der mathe-
matischen Optimierung besteht darin, das Maximum oder das Minimum einer Zielfunkti-
on zu bestimmen, wobei der Definitionsbereich für die Zielfunktion durch einschränkende
Bedingungen festgelegt wird. [4, S.7]
Von linearer Optimierung spricht man, wenn sowohl die Zielfunktion, als auch die ein-
schränkenden Bedingungen durch lineare Gleichungen und Ungleichungen beschrieben
werden können. Die Beschreibung durch lineare Gleichungen und Ungleichungen hat den
Vorteil, dass die Lösung aus mathematischer Sicht relativ einfach ist (siehe dazu auch
Kapitel 3). Die Formulierung der einschränkenden Bedingungen und der Zielfunktion
16
2 Modellierung linearer Optimierungsaufgaben
durch lineare Gleichungen und Ungleichungen nennt man Modellierung. Diese Modellie-
rung ist notwendig, um dann zur mathematischen Lösung überzugehen.
Allgemein kann ein Optimierungsproblem auf folgende Weise formuliert werden:
max(f(x))
mit
x ∈ S
Dabei sei S ⊆ Rn der zulässige Bereich und f : S → Rn die Zielfunktion.
Ziel ist die Bestimmung des Maximums der Funktion f auf der Menge S. Analog kann
ein Minimumsproblem formuliert werden. Dabei soll das Minimum der Funktion f auf
der Menge S bestimmt werden.
In der Praxis kann die Modellierung der Optimierungsaufgabe deutlich aufwändiger
als im obigen Beispiel sein. Einerseits sind manche Probleme mathematisch nicht klar
fassbar und andererseits können konkurrierende Optimierungsziele herrschen [5, S.9].
Ist ein Unternehmen zum Beispiel auf den Zukauf knapper Ressourcen angewiesen, so
sollten die Gesamtkosten für den Zukauf möglichst gering sein, aber der Preis sollte für
den Verkäufer der Ressourcen trotzdem attraktiv sein.
Um die lineare Optimierung theoretisch einheitlich zu beschreiben, versucht man die Re-
lationszeichen ≤ und ≥ bei den einschränkenden Bedingungen durch Gleichheitszeichen
zu ersetzen. Zusätzlich will man nicht ständig zwischen Minimierungs- und Maximie-
rungsaufgaben unterscheiden. Man betrachtet meist nur einen Typ von Aufgaben, da
das Maximum einer Funktion f genau dem negativen Wert des Minimums der zu f
inversen Funktion entspricht:
maxx∈S
( f(x)) = −(minx∈S
( −f(x)))
17
Wird ein Optimierungsproblem in diese einheitliche Form umgeschrieben, nennt man
das auch die Normalform oder Standardform der Optimierungsaufgabe (siehe Kap. 3).
18
3 Lösung linearer
Optimierungsaufgaben
3.1 Mathematische Grundlagen
In diesem Abschnitt werden einige mathematische Voraussetzungen erläutert, die für die
Lösung von linearen Programmen notwendig sind.
Die Grundbegriffe der Mengenlehre und von linearen Funktionen in 2 Variablen setze
ich an dieser Stelle voraus:
• Menge und mögliche Schreibweisen
• leere Menge, Teilmenge
• Durchschnitt und Vereinigung von Mengen
• Normalform einer linearen Funktion in zwei Variablen
• Graph einer linearen Funktion und dessen Darstellung im Koordinatensystem
Ebenso setze ich lineare Ungleichungen in einer Variablen und deren Lösungsmenge in
der Menge der reellen Zahlen R voraus.
3.1 Mathematische Grundlagen
3.1.1 Lösung einer linearen Ungleichung in 2 oder mehreren
Variablen
Unter einer linearen Ungleichung in 2 Variablen x und y versteht man eine Aufgabe, die
immer in der Form
ax+ by < c
angegeben werden kann (eventuell durch Äquivalenzumformungen umgeformt). Dabei
gelte, dass a, b, c ∈ R. Falls auch für die zwei Variablen jeweils die Grundmenge der
reellen Zahlen angenommen wird, so werden alle Zahlenpaare
(x, y) ∈ R2
gesucht, die diese Aufgabe erfüllen. Graphisch ergibt die Lösungsmenge eine offene Halb-
ebene. Wird anstelle von < das Relationszeichen ≤ verwendet, so gehört die Menge der
Zahlenpaare (x, y), die die Bedingung ax + by = c erfüllen ebenso zur Lösungsmenge,
die dann als geschlossene Halbebene bezeichnet wird. Offene Halbebenen werden durch
strichlierte Geraden begrenzt, geschlossene Halbebenen durch durchgezogene Geraden.
Siehe dazu auch Abbildung 3.1 und 3.2; die Lösungsmenge ist jeweils blau gefärbt.
Abbildung 3.1: offene Halbebene Abbildung 3.2: geschlosseneHalbebene
Werden lineare Ungleichungen auf drei Variablen erweitert, so sind Aufgaben der Form
20
3 Lösung linearer Optimierungsaufgaben
ax+ bx+ cz < d mit a, b, c, d ∈ R zu lösen.
Betrachtet man als Grundmenge der Variablen wieder jeweils die Menge der reellen
Zahlen R, so stellt die Lösungsmenge einen (offenen) Halbraum dar.
Die Ebene ax+ by + cz = d teilt den Raum R3 in zwei Halbräume.
Betrachtet man lineare Ungleichungen mit n Variablen x1, x2, x3, ..., xn und die Menge
der reellen Zahlen R gilt als Grundmenge jeder einzelnen Variablen, so betrachtet man
den Vektorraum Rn. Als Lösung kommen alle n-Tupel (x1, x2, x3, ..., xn) infrage, die die
Ungleichung erfüllen.
Jede Ungleichung legt einen Halbraum des Rn fest, wobei die Begrenzung eine (n− 1)-
dimensionale Hyperebene darstellt.
Der Begriff Hyperebene ist eine Verallgemeinerung des Begriffs der Ebene im dreidimen-
sionalen Raum R3 auf einen Raum beliebiger Dimension Rn.
Definition. [4, S.77] Eine Hyperebene im n-dimensionalen Raum Rn ist die Menge
aller Punkte mit den geordneten n-Tupeln (x1, x2, ..., xn), die eine lineare Funktion
a1x1 + a2x2 + ...+ anxn = b und (a1, a2, ..., an) 6= (0, 0, ..., 0) erfüllen.
Im zweidimensionalen Raum stellt jede Gerade eine Hyperebene dar; im dreidimensio-
nalen Raum jede Ebene.
3.1.2 Konvexe Mengen
Betrachtet man Punktmengen im n-dimensionalen Raum Rn, so kann jeder Punkt durch
seine Koordinaten im Raum (x1, x2, x3, ..., xn) beschrieben werden.
Definition. (Vgl. [6, S.9]) Es sei M ⊆ Rn. M heißt konvex, wenn für alle P , Q ∈ M ,
alle Punkte der Form aP + (1− a)Q mit a ∈ R und 0 ≤ a ≤ 1 Elemente der Menge M
sind.
21
3.1 Mathematische Grundlagen
Anschaulich heißt das, dass mit zwei beliebigen Punkten P und Q auch alle Punkte
auf ihrer Verbindungsstrecke zur Menge M gehören. In den folgenden Abbildungen sind
konvexe und nicht konvexe Mengen im R2 dargestellt.
Abbildung 3.3: konvexe Menge Abbildung 3.4: nicht konvexe Menge
Für konvexe Mengen gilt folgender Satz:
Satz. (Vgl. [4, S.31]) Sind M1, M2, ..., Mn konvexe Punktmengen, so ist der Durch-
schnitt D = M1 ∩M2 ∩ ... ∩Mn wieder eine konvexe Punktmenge.
Beweis. [4, S.31f] Nach der Voraussetzung sind M1, M2, ..., Mn konvexe Punktmengen.
Die Durchschnittsmenge D = M1 ∩M2 ∩ ...∩Mn ist nach Definition die Menge der Ele-
mente, die sowohl zu M1, wie zu M2, ... wie zu Mn gehören. Also ist D eine Teilmenge
von jeder Menge M1, M2, ..., Mn. Da nun die Verbindungsstrecke von zwei beliebigen
Punkten jeder konvexen Menge zu der Menge gehört, gilt das auch für die Verbindungs-
strecke zweier beliebiger Punkte der Durchschnittsmenge. Das bedeutet aber, dass der
Durchschnitt von n konvexen Punktmengen wieder konvex ist.
Alle Punkte einer Ebene bzw. einer Halbebene bilden eine konvexe Menge.
Daher ist die Durchschnittsmenge von 2 Halbebenen eine konvexe Menge.
22
3 Lösung linearer Optimierungsaufgaben
Ebenso ist die Durchschnittsmenge von 3 Halbebenen eine konvexe Menge.
Allgemein ist auch die Durchschnittsmenge von n Halbebenen eine konvexe Menge.
Definition. [6, S.9] Ist eine beliebige Punktmenge M gegeben, die nicht notwendiger-
weise konvex ist, so kann man diese durch Hinzufügen von Punkten zu einer konvexen
Menge erweitern. Die kleinstmögliche konvexe Menge M co, die die Menge M enthält,
heißt konvexe Hülle von M .
Beispiele:
Hat man im zweidimensionalen Raum R2 zwei beliebige Punkte A und B gegeben, so
entspricht die konvexe Hülle der Strecke AB.
Sind drei Punkte A,B und C im R2 gegeben, so ist die konvexe Hülle die Dreiecksfläche
mit den Eckpunkten A,B,C (siehe Abbildung 3.5).
Abbildung 3.5: konvexe Hülle von A, B und C
3.1.3 Konvexe Polyeder
Definition. [4, S.33] Ist M eine konvexe Punktmenge, so heißt E ein Eckpunkt von
M , wenn es keine echte Strecke in M gibt, die den Punkt E als Mittelpunkt hat.
Definition. Eine beschränkte konvexe Menge mit nur endlich vielen Eckpunkten heißt
konvexes Polytop.
Das Polyeder wird als Schnittmenge endlich vieler Halbräume definiert. Der Name Po-
lyeder kommt aus dem Griechischen und bedeutet so viel wie „Vielflächner“. Man kann
23
3.1 Mathematische Grundlagen
sich also einen geometrischen Körper vorstellen, der von ebenen Flächen begrenzt wird
und mit zwei belieben Punkten auch deren Verbindungslinie enthält.
Im zweidimensionalen Raum bilden die Schnittpunkte von zwei Geraden die Eckpunkte
eines Polyeders, im dreidimensionalen Raum die Schnittpunkte von je 3 Ebenen. Im n-
dimensionalen Raum wird jede Ecke eines Polyeders durch den Schnitt von Hyperebenen
bestimmt.
Bekannte zwei- bzw. dreidimensionale konvexe Polyeder aus der Schulgeometrie sind
zum Beispiel:
• Rechteck
• Dreieck
• Vieleck
• Würfel
• Pyramide
Die folgende Abbildung 3.6 zeigt ein konvexes Polyeder im dreidimensionalen Raum.
Abbildung 3.6: Ein konvexes Polyeder [7]
24
3 Lösung linearer Optimierungsaufgaben
Viele weitere Abbildungen dreidimensionaler Polyeder findet man im Internet, zum Bei-
spiel bei Wikipedia unter https://de.wikipedia.org/wiki/Polyeder unter Abschnitt 4 (Be-
nennung).
3.2 Graphische Lösung linearer Programme
3.2.1 Zulässiger Bereich
Wie im Kapitel 2 - Modellierung linearer Programme - bereits erwähnt, werden bei einer
linearen Optimierungsaufgabe stets einschränkende Bedingungen, Nichtnegativitätsbe-
dingungen und eine Zielfunktion in Form von linearen Ungleichungen und Gleichungen
angegeben. Allgemein kann solch eine Aufgabe in folgender Weise angegeben werden
(vgl. [4, S.80]):
a11x1 + a12x2 + a13x3 + ...+ a1nxn ≤ b1
a21x1 + a22x2 + a23x3 + ...+ a2nxn ≤ b2
...
am1x1 + am2x2 + am3x3 + ...+ amnxn ≤ bm
einschränkende Bedingungen (3.1)
x1 ≥ 0
x2 ≥ 0...
xn ≥ 0
Nichtnegativitätsbedingungen (3.2)
Unter diesen Bedingungen sollen nun die Variablen x1, x2, ..., xn bestimmt werden, so
dass die Zielfunktion Z = c1x1+c2x2+· · ·+cnxn einen Maximalwert (oder Minimalwert)
25
3.2 Graphische Lösung linearer Programme
annimmt.
Die Koeffizienten aij, bi und cj (i = 1, 2, 3...,m und j = 1, 2, 3, ..., n) sind stets reelle
Zahlen.
Bei den einschränkenden Bedingungen wird hier nur das Relationszeichen ≤ angegeben,
da jeden Ungleichung mit dem Relationszeichen ≥ durch die Multiplikation mit der Zahl
-1 in diese Form umgeschrieben werden kann.
Als Lösung des linearen Programms kommen nun all jene n-Tupel (x1, x2, ..., xn) in
Frage, die die Bedingungen (3.1) und (3.2) erfüllen. Diese Menge der n-Tupel wird als
zulässiger Bereich bezeichnet.
Die Punktmenge der zulässigen Lösungen wird durch Hyperebenen begrenzt. Ihre Glei-
chungen erhält man, indem man bei den einschränkenden Bedingungen nur das Gleich-
heitszeichen gelten lässt [4, S.80]:
a11x1 + a12x2 + a13x3 + ...+ a1nxn = b1
a21x1 + a22x2 + a23x3 + ...+ a2nxn = b2
...
am1x1 + am2x2 + am3x3 + ...+ amnxn = bm
Gleichungen der Hyperebenen (3.3)
Geometrisch beschreibt die Menge der zulässigen Lösungen ein n-dimensionales Poly-
eder, das durch m Hyperebenen begrenzt wird (vgl. Abschnitt 3.1.3).
Dass der zulässigen Bereich sogar eine konvexe Menge beschreibt, besagt der folgende
Satz:
Satz. (vgl. [6, S.14]) Der zulässige Bereich ist konvex.
Beweis. (vgl. [6, S.14]) Seien r = (r1, r2, ..., rn) und s = (s1, s2, ..., sn) zwei beliebige
Punkte des zulässigen Bereiches (d.h.: beide Punkte erfüllen die Nichtnegativitäts- und
26
3 Lösung linearer Optimierungsaufgaben
die einschränkenden Bedingungen). Bezeichnen wir die Koeffizientenmatrix (aij) in (3.1)
mit A und den Spaltenvektor aus den rechten Seiten von (3.1) mit b, so gilt: Ar ≤ b
und As ≤ b. Für ein beliebiges λ mit 0 ≤ λ ≤ 1 folgt daraus:
λAr ≤ λb und (1− λ)As ≤ (1− λ)b. Durch Umformungen (Addition der beiden Unglei-
chungen und herausheben) kommt man zu folgender Ungleichung: A(λr+ (1−λ)s) ≤ b.
Da alle Komponenten von r und s nicht negativ sind, folgt das auch für λr + (1− λ)s.
Der Punkt λr + (1− λ)s ist also zulässig.
3.2.2 Optimale Lösung - Hauptsatz
Von dem oben definierten zulässigen Bereich soll nun eine Lösung bestimmt werden,
die die Zielfunktion maximiert (bzw. minimiert). Man nennt eine solche Lösung eine
optimale Lösung. Zum Auffinden der optimalen Lösung des linearen Programms ist
der sog. „Hauptsatz der linearen Optimierung“ hilfreich.
Satz. (vgl. [6, S.15]) (a) Eine lineare Funktion z = f(x1, x2, ..., xn), die auf einem kon-
vexen Polyeder definiert ist, nimmt dort ihr Minimum/Maximum in mindestens einem
Eckpunkt an.
(b) Nimmt die lineare Funktion ihr Minimum (bzw. Maximum) in mehr als einem der
Punkte an, so nimmt sie es auf der gesamten konvexen Hülle dieser Punkte an.
Beweis. (vgl. [6, S.15]) (a) Sei min(f(x1, x2, ..., xn)) = f(x1, x2, ..., xn) und (x1, x2, ..., xn)
kein Eckpunkt des zulässigen Bereiches.
Die Eckpunkte seien r1, r2, ..., rq, wobei alle Eckpunkte durch n-Tupel gegeben sind.
Dann kann der Punkt (x1, x2, ..., xn) als Linearkombination der Eckpunkte geschrieben
werden:
(x1, x2, ..., xn) = ∑qi=1 λiri, wobei
∑qi=1 λi = 1 und 0 ≤ λi ≤ 1 für i = 1, 2, ..., q.
Ist mini(f(ri))= f(rk), so gilt: f(x1, x2, ..., xn) = ∑qi=1 λif(ri) ≥ f(rk) ·∑q
i=1 λi = f(rk).
27
3.2 Graphische Lösung linearer Programme
Da f(x1, x2, ..., xn) das Minimum von f(x1, x2, ..., xn) ist, folgt f(x1, x2, ..., xn) = f(rk)
und das Minimum wird auch im Eckpunkt rk angenommen.
(b) f(x1, x2, ..., xn) nehme das Minimum in p Punkten r1, r2, ..., rp an (alle ri mit i =
1, 2, ..., p seien wieder durch n-Tupel gegeben). Die konvexe Hülle der Punkte ri ist
gegeben durch die Menge aller folgenden r0:
r0 = ∑pi=1 λiri mit ∑p
i=1 λi = 1 und 0 ≤ λi ≤ 1 für i = 1, 2, ..., p.
Dann folgt, dass f(r0) = ∑pi=1 λif(ri) = f(r1)
∑pi=1 λi = f(r1) = minf(x1, x2, ..., xn).
Analog kann der Beweis für das Maximum gezeigt werden.
Somit kann man sich bei der Suche nach der optimalen Lösung auf die Eckpunkte des zu-
lässigen Bereiches beschränken. Da der zulässige Bereich durch ein Polyeder mit endlich
vielen Ecken gegeben ist, hat man eine endliche „Kandidatenmenge“.
3.2.3 Graphisches Lösungsverfahren für zwei Variablen
Die genaue Vorgehensweise beim graphischen Lösen linearer Programme mit zwei Varia-
blen möchte ich gerne im Kapitel 5 ausführlicher besprechen, da dieses Lösungsverfahren
in der Schule verwendet wird. Dort werde ich auch auf die verschiedenen Fälle der zuläs-
sigen Bereiche eingehen. Trotzdem erkläre ich an dieser Stelle kurz die Vorgehensweise.
3.2.3.1 Maximumsproblem
Als Variablen werden x und y verwendet. Allgemein kann die Optimierungsaufgabe auf
folgende Weise angegeben werden:
Nichtnegativitätsbedingungen: x ≥ 0 und y ≥ 0
28
3 Lösung linearer Optimierungsaufgaben
Einschränkende Bedingungen:
a11x+ a12y ≤ b1
a21x+ a22y ≤ b2
...
am1x+ am2y ≤ bm
Zielfunktion: c1x+ c2y = Z →Max.
Dabei sind aij, cj und bi mit i = 1, 2, ...,m und j = 1, 2 reelle Zahlen.
Alle Zahlenpaare (x, y), die die Nichtnegativitäts- und einschränkenden Bedingungen
erfüllen, bilden den zulässigen Bereich. Graphisch wird der zulässige Bereich als Vieleck
im R2 dargestellt, wobei die einschränkenden Bedingungen die begrenzenden Geraden
liefern (Relationszeichen durch Gleichheitszeichen ersetzen).
Ein möglicher zulässiger Bereich einer Maximumsaufgabe, der durch drei einschränkende
Bedingungen gegeben ist, wird in untenstehender Abbildung 3.7 dargestellt. Der zuläs-
sige Bereich ist braun markiert.
Für die Zielfunktion ergibt sich eine Schar von parallelen Geraden, wobei der Wert von
Z für jede einzelne Gerade konstant ist. Die Aufgabe ist nun, das Wertepaar (x, y) aus
dem zulässigen Bereich zu finden, für das der Wert von Z maximal wird.
Dazu setzt man für Z den Wert 0 ein und zeichnet diese Gerade ins Koordinatensystem
ein. Dann zeichnet man eine zu dieser Geraden parallel Gerade, die mindestens noch
einen Punkt des zulässigen Bereiches enthält mit einem möglichst extremen Achsenab-
schnitt (positiv oder negativ, je nach Vorzeichen der Koeffizienten der Zielfunktion) auf
der y-Achse.
29
3.2 Graphische Lösung linearer Programme
Abbildung 3.7: zulässiger Bereich - Maximumsaufgabe
3.2.3.2 Minimumsproblem
Ähnlich wie die Maximumsaufgabe kann auch die Minimumsaufgabe allgemein angege-
ben werden:
Nichtnegativitätsbedingungen: x ≥ 0 und y ≥ 0
Einschränkende Bedingungen:
a11x+ a12y ≥ b1
a21x+ a22y ≥ b2
...
am1x+ am2y ≥ bm
Zielfunktion: c1x+ c2y = Z →Min.
Die Variablen seien wie oben definiert.
30
3 Lösung linearer Optimierungsaufgaben
Alle Zahlenpaare (x, y), die die Nichtnegativitäts- und einschränkenden Bedingungen
erfüllen, bilden wiederum den zulässigen Bereich (Vorgehensweise wie oben).
Ein möglicher zulässiger Bereich einer Minimumsaufgabe, der durch drei einschränkende
Bedingungen gegeben ist, wird in Abbildung 3.8 dargestellt. Der zulässige Bereich ist
braun markiert.
Abbildung 3.8: zulässiger Bereich - Minimumsaufgabe
Zum Bestimmen der optimalen Lösung geht man analog zur Maximumsaufgabe vor. Die
Zielfunktion zeichnet man wiederum so ein, dass sie mindestens noch einen Punkt des
zulässigen Bereiches enthält, mit einem möglichst extremen Achsenabschnitt (abhängig
von den Koeffizienten der Zielfunktion) auf der y-Achse.
3.2.4 Graphisches Lösungsverfahren für drei Variablen
Treten bei einer linearen Optimierungsaufgabe drei Variablen x, y und z auf, so kann
das graphische Lösungsverfahren auf den Raum R3 übertragen werden.
Der zulässige Bereich wird nun durch ein dreidimensionales Polyeder festgelegt. Die Be-
31
3.2 Graphische Lösung linearer Programme
grenzungen des Polyeders werden durch Ebenen bestimmt (einschränkende Bedingungen
mit Gleichheitszeichen).
Gesucht wird ein Zahlentripel (x, y, z) als optimale Lösung.
Die graphische Darstellung der Zielfunktion liefert eine Schar von parallelen Ebenen,
wobei der Wert Z der Zielfunktion jeweils wieder konstant ist.
Bei einem Maximumsproblem wird die Ebene der Zielfunktion nun so weit verschoben,
dass sie noch mindestens einen Punkt mit dem Lösungspolyeder gemeinsam und einen
möglichst extremen Abstand vom Koordinatenursprung hat (sind die Koeffizienten der
Zielfunktion positiv, so soll der Abstand möglichst groß sein). Bei einer Minimumsauf-
gabe soll der Abstand zum Koordinatenursprung möglichst klein sein, vorausgesetzt die
Koeffizienten der Zielfunktion sind positiv.
Die folgenden Abbildungen sollen die graphische Lösung im dreidimensionalen Raum
erläutern. In der Abbildung 3.9 ist ein möglicher dreidimensionaler zulässiger Bereich
dargestellt, der braun gefärbt ist. Dazu ist eine beliebige Ebene der Zielfunktion einge-
zeichnet.
In der Abbildung 3.10 ist eine Schar von drei Ebenen eingezeichnet, die durch die Ziel-
funktion gegeben ist. Diese Ebene müsste zur optimalen Lösung noch entsprechend ver-
schoben werden.
Lineare Programme mit mehr als 3 Variablen werden im Allgemeinen nicht graphisch
gelöst, da dies nicht anschaulich darstellbar ist.
32
3 Lösung linearer Optimierungsaufgaben
Abbildung 3.9: zulässiger Bereich
Abbildung 3.10: zulässiger Bereich mit Ebenenschar
3.3 Rechnerische Lösung linearer Programme - das
Simplex-Verfahren
Die Berechnung eines Maximums oder Minimums einer reellen Funktion wird generell
mit Hilfe der Differentialrechnung gelöst. Allerdings kann die Differentialrechnung für die
33
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
Maximierung/Minimierung einer linearen Zielfunktion nicht verwendet werden. Lineare
Funktionen sind zwar an jeder beliebigen Stelle ihres Definitionsbereiches differenzierbar,
aber ihre Steigung ist konstant. Daher kann die notwendige Bedingung für Extremstellen
(waagrechte Tangente an der Extremstelle, also f ′(x) = 0) nicht erfüllt werden. Zusätz-
lich wird durch die Nebenbedingungen der Definitionsbereich der linearen Zielfunktion
eingeschränkt, sodass ein möglicher Extremwert auch außerhalb dieses Definitionsberei-
ches liegen könnte.
Die Berechnung eines Maximums/Minimums der linearen Zielfunktion wird daher nicht
mit der Differentialrechnung gelöst.
Wie bereits im Kapitel 1 - Geschichte der linearen Optimierung - erwähnt, wird das
Simplex-Verfahren zur Lösung von linearen Programmen verwendet.
3.3.1 Grundidee und Normalform
3.3.1.1 Idee des Simplex-Verfahrens
Die Arbeitsweise des Simplexalgorithmus lässt sich am Vorgehen einer Ameise illustrie-
ren, die auf den Kanten eines Polyeders entlang krabbelt [...], um eine geeignete Zielecke
zu finden. Die Ameise kann nicht sehen, wo diese Ecke liegt, und wenn sie nun wahllos
dem Zufall folgend die Kanten durchlaufen würde, könnte es eine Ewigkeit dauern, bis
sie ihr Ziel erreicht [8, S.7](siehe Abbildung 3.11).
Durch das Simplex-Verfahren bekommt die Ameise Zusatzinformationen, um festzustel-
len welche der beiden benachbarten Ecken sie wählen sollte. Dabei wird die Zielfunktion
in beiden benachbarten Ecken ausgewertet; sie wählt jene Ecke mit dem „besseren“ Wert
(größeren Wert für Maximumsaufgaben, kleineren Wert für Minimumsaufgaben). In der
neuen Ecke wird die Auswertung erneut durchgeführt. Dies wird solange wiederholt, bis
die Zielecke (=optimale Ecke) erreicht ist.
34
3 Lösung linearer Optimierungsaufgaben
Abbildung 3.11: Idee des Simplex-Verfahrens
Der Simplexalgorithmus erspart zwar gewöhnlich den Weg durch alle Ecken, aber auch
dann können zwischen den Startecken und der optimalen Lösung durchaus sehr viele
Ecken durchlaufen werden. [...] Wenn nun zwischen der Startecke und der optimalen
Ecke sehr viele kurze Kanten liegen, kommt der Simplexalgorithmus nur langsam voran
[8, S.7].
Für die Berechnung der optimalen Lösung heißt das nun, dass man zuerst einen be-
liebigen, einfach zu berechnenden Eckpunkt des zulässigen Bereiches bestimmt. Dann
berechnet man die Koordinaten des nächsten Eckpunktes so, dass eine stete Verbesse-
rung der Zielfunktion erreicht wird. Dies wird solange wiederholt, bis keine Verbesserung
mehr möglich ist.
3.3.1.2 Normalform eines linearen Programms
Am Ende von Kapitel 2 wurde kurz erläutert, dass das Umschreiben der einschränkenden
Bedingungen in lineare Gleichungen notwendig ist, um zur Normal- oder Standardform
des linearen Programms zu gelangen. Das erfordert das Einführen neuer Variablen, den
35
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
sog. Schlupfvariablen.
Hat man zum Beispiel die lineare Ungleichung x + 2y ≤ 5 vorliegen, so führt man eine
neue Variable z ein und kann als Gleichung x+ 2y+ z = 5 schreiben. Die neue Variable
z ist dabei nicht negativ.
Alle einschränkenden Bedingungen aus (3.1) - siehe Seite 25 - werden nun mit den
Schlupfvariablen u1, u2, ..., um in neue Nebenbedingungen umgeschrieben:
a11x1 + a12x2 + a13x3 + ...+ a1nxn + u1 = b1
a21x1 + a22x2 + a23x3 + ...+ a2nxn + u2 = b2
...
am1x1 + am2x2 + am3x3 + ...+ amnxn + um = bm
Nebenbedingungen (3.4)
Dabei sind die Schlupfvariablen nicht negativ: u1 ≥ 0, ..., um ≥ 0.
Die Nichtnegativitätsbedingungen und die Zielfunktion für eine Maximumsaufgabe blei-
ben unverändert:
x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0
Z = c1x1 + c2x2 + ....cnxn →Max.
Analog kann auch jedes Minimumsproblem in diese Normalform umgeschrieben werden.
Dabei werden zuerst die einschränkenden Bedingungen mit der Zahl -1 multipliziert,
um die Relationszeichen von ≥ zu ≤ umzuschreiben. Dann werden die Schlupfvariablen
eingeführt, die wiederum nicht negativ sind.
36
3 Lösung linearer Optimierungsaufgaben
3.3.2 Einführendes Beispiel mit 2 Variablen
Ich möchte an dieser Stelle die rechnerische Lösung an der Maximumsaufgabe erläutern,
die im Kapitel 2 (vgl. Seite 15/16) bereits modelliert wurde. Gleichzeitig möchte ich
auch Zusammenhänge mit der graphischen Lösung im R2 herstellen. Das folgende lineare
Programm in den Variablen x1 und x2 ist zu lösen:
Einschränkende Bedingungen: I) x1 ≤ 1000
II) x2 ≤ 1300
III) x1 + x2 ≤ 1900
Nichtnegativitätsbedingungen: x1 ≥ 0
x2 ≥ 0
Zielfunktion: Z = 0, 60x1 + 0, 40x2 →Max.
Graphisch erhält man durch diese Bedingungen folgenden zulässigen Bereich:
Abbildung 3.12: zulässiger Bereich im R2
37
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
Zuerst wird das lineare Programm in die Normalform umgeschrieben, dazu werden drei
nicht negative Schlupfvariablen u1, u2 und u3 eingeführt. Die Schlupfvariablen werden
auch in die Zielfunktion aufgenommen, allerdings erhalten sie dort die Koeffizienten null,
da sie keinen Einfluss auf den Gewinn der Firma haben. Man erhält dadurch folgendes
Gleichungssystem A1:
I) x1 + u1 = 1000
II) x2 + u2 = 1300
III) x1 + x2 + u3 = 1900
Z = 0, 60x1 + 0, 40x2 + 0u1 + 0u2 + 0u3
Zu Beginn setzt man nun x1 = 0 und x2 = 0.
Dadurch erhält man eine erste Lösung des Gleichungssystems A1:
u1 = 1000, u2 = 1300 und u3 = 1900.
Diese Lösung nennt man die 1. Basislösung. Diese Lösung ist allerdings nicht optimal,
da sich dadurch Z = 0 ergibt.
Graphisch entspricht diese Lösung dem Eckpunkt A = (0|0) im zulässigen Bereich.
Der Wert der Zielfunktion kann erhöht werden, wenn die Variablen x1 und/oder x2
erhöht werden. Da die Variable x1 den größeren Koeffizienten in der Zielfunktion hat,
wird nun zuerst x1 erhöht.
Für x1 ergeben sich die Einschränkungen x1 ≤ 1000 und x1 ≤ 1900 aus den Gleichungen
I und III. Die Einschränkung x1 ≤ 1000 ist also bestimmend für x1, daher wird Gleichung
I folgendermaßen umgeformt: x1 = 1000− u1.
Nun wird die Variable x1 in allen anderen Gleichungen durch 1000−u1 ersetzt und man
erhält dadurch das Gleichungssystem A2:
38
3 Lösung linearer Optimierungsaufgaben
I) x1 + u1 = 1000
II) x2 + u2 = 1300
III) 1000− u1 + x2 + u3 = 1900
Z − 600 = 0, 60u1 + 0, 40x2
Wählt man nun den größtmöglichen Wert für x1, erhält man die 2. Basislösung aus A2:
x1 = 1000, u1 = 0, x2 = 0 (weil nur x1 vergrößert wurde), u2 = 1300 und u3 = 900.
Die Zielfunktion ergibt Z = 600. Graphisch entspricht diese Lösung dem Eckpunkt
B=(1000|0).
Diese Lösung ist noch nicht optimal, weil durch die Erhöhung von x2, der Wert der
Zielfunktion noch gesteigert werden kann.
Für x2 ergeben sich die Einschränkungen x2 ≤ 1300 und x2 ≤ 900 aus den Gleichungen
II und III. Die Einschränkung x2 ≤ 900 ist also bestimmend für x2, daher wird Gleichung
III folgendermaßen umgeformt: x2 = 900 + u1 − u3.
Nun wird die Variable x2 in allen anderen Gleichungen ersetzt und man erhält dadurch
das Gleichungssystem A3:
I) x1 + u1 = 1000
II) u1 − u3 + u2 = 400
III) x2 − u1 + u3 = 900
Z − 930 = −0, 20u1 − 0, 40u3
Wählt man nun den größtmöglichen Wert für x2, erhält man die 3. Basislösung aus A3:
x2 = 900, x1= 1000 (weil nur x2 vergrößert wurde), u1 = 0, , u2 = 400 und u3 = 0.
39
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
Die Zielfunktion ergibt Z = 930. Graphisch entspricht diese Lösung dem Eckpunkt
C = (1000|900).
Diese Lösung ist auch die optimale Lösung, da in der Zielfunktion nur mehr negative Ko-
effizienten vorkommen. Egal welche Variable noch erhöht wird, der Wert der Zielfunktion
wird nicht mehr größer.
Als Lösung erhält man also x1 = 1000, x2 = 900 und Z= 930.
Im Bezug auf die Ausgangssituation kann das Ergebnis so interpretiert werden: Der
Betrieb soll 1000 Flaschen mit der Abfüllmaschine 1 abfüllen, 900 Flaschen mit der
Maschine 2. Dann kann er den maximalen Gewinn von e930 erzielen.
Um diese Berechnungen und Gleichungssysteme übersichtlicher darzustellen, wird meist
eine tabellarische Schreibweise verwendet. Man nennt diese Tabellen auch Simplex-
Tabellen. Diese Tabellen sind in einzelne Simplex - Tableaus unterteilt.
Ich möchte an dieser Stelle für das gerade gelöste Beispiel diese Simplex-Tabelle angeben.
Dabei werden jeweils die Koeffizienten der Variablen x1, x2, u1, u2 und u3 in die Spalten 2
und 3 eingetragen. In der ersten Spalte stehen die Variablen, die in den jeweiligen Basis-
lösungen vorkommen. Die Spalte bi gibt jeweils die rechten Seiten der Gleichungssysteme
an. Die Spalte qi gibt jeweils die Berechnung der Einschränkungen an.
40
3 Lösung linearer Optimierungsaufgaben
Basisvariable x1 x2 u1 u2 u3 bi qi
u1 1 0 1 0 0 1000 1000
u2 0 1 0 1 0 1300
u3 1 1 0 0 1 1900 1900
Z1 0,6 0,4 0 0 0 0
x1 1 0 1 0 0 1000
u2 0 1 0 1 0 1300 1300
u3 0 1 -1 0 1 900 900
Z2 0 0,4 -0,6 0 0 -600
x1 1 0 1 0 0 1000
u2 0 0 1 1 -1 400
x2 0 1 -1 0 1 900
Z3 0 0 -0,2 0 -0,4 -930
Mit Hilfe der vorigen, ausführlicheren Beschreibung der Vorgehensweise kann man jetzt
leicht erkennen, dass in den Zeilen 1 bis 4 die Koeffizienten des Gleichungssystems A1
eingetragen sind. Die erste Basislösung kann an den Spalten Basisvariable und bi abgele-
sen werden. Der Wert der Zielfunktion kann ebenfalls in der Spalte bi abgelesen werden
(allerdings mit negativem Vorzeichen).
Diese Zeilen nennt man auch das Ausgangstableau (Daten des Gleichungssystems (A1)
werden übertragen).
Die Spalte mit dem größten positiven Koeffizienten in der Zielfunktion heißt Haupt-
spalte, die Zeile mit dem kleinsten Wert qi heißt Hauptzeile.
Das Element, das Hauptzeile und -spalte angehört, nennt man Hauptelement oder
Pivotelement. Diese sind in der obigen Tabelle durch einen Kreis gekennzeichnet.
Das Hauptelement gibt nun an, welche Variable in die Lösung aufgenommen werden
41
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
soll. Daher wird nun die Variable x1 in die Lösung aufgenommen, die Variable u1 aus
der Lösung entfernt.
Durch Ausführen der oben beschriebenen Rechenoperationen, erhält man das Glei-
chungssystem A2, dessen Koeffizienten nun in den Zeilen 5 bis 8 zu finden sind (zweites
Simplex - Tableau). Ebenso kann die zweite Basislösung wiederum abgelesen werden.
Das Hauptelement ist wieder gekennzeichnet, daher wird nun die Variable x2 in die Lö-
sung aufgenommen und die Variable u3 entfernt.
Durch Umformungen erhält man daraus das Gleichungssystem A3, das nun in den Zeilen
9 bis 12 zu finden ist (drittes Simplex - Tableau). Die dritte Basislösung kann wieder in
der Spalte bi abgelesen werden. Da die Zielfunktion Z3 keine positiven Koeffizienten mehr
enthält ist man am Ende der Rechnung angelangt und die dritte Basislösung entspricht
der Endlösung des linearen Programms.
3.3.3 Allgemeine Formulierung des Simplex-Algorithmus
Im Kapitel 2 - Modellierung - wurde bereits darauf hingewiesen, dass das Maximum
einer Funktion genau dem Minimum der mit Minus multiplizierten Funktion entspricht.
Deshalb möchte ich in diesem Abschnitt das Simplex-Verfahren nur für Maximumsauf-
gaben in Normalform erläutern.
Wie bereits erwähnt, werden die Angaben und Umformungen übersichtlich in der Sim-
plex - Tabelle zusammengefasst. Ich möchte zuerst die Überlegungen/Berechnungen all-
gemein beschreiben und nachher die Tabelle für diese Beschreibung angeben.
Gegeben sei das lineare Programm durch folgendeNormalform (A1): (vgl. [4, S. 102ff])
42
3 Lösung linearer Optimierungsaufgaben
Nichtnegativitätsbedingungen: x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0
Gleichungssystem: a11x1 + a12x2 + ...+ a1nxn + u1 = b1
a21x1 + a22x2 + ...+ a2nxn + u2 = b2...
am1x1 + am2x2 + ...+ amnxn + um = bm
Zielfunktion: Z = c1x1 + c2x2 + ...+ cnxn + 0u1 + 0u2 + ...+ 0um →Max.
Dabei sind die Koeffizienten aij, cj und bi mit i = 1, 2, ...,m und j = 1, 2, ..., n reel-
le Zahlen, wobei bi sogar positive reelle Zahlen sind. Die Schlupfvariablen sind durch
u1, u2, ..., um gegeben.
Das Gleichungssystem aus (A1) besteht aus m Gleichungen (diese Gleichungen sollen
unabhängig sein, das heißt, dass alle Gleichungen notwendig sind, um die Aufgabe zu
modellieren) in n+m Variablen. Da aus m unabhängigen Gleichungen genau m Varia-
blen berechnet werden können, werden zuerst n Variablen null gesetzt.
Wie im einführenden Beispiel wählt man zuerst:
x1 = 0, x2 = 0, ..., xn = 0.
Damit erhält man die erste Basislösung:
u1 = b1, u2 = b2, ..., um = bm
Der Wert der Zielfunktion ist Z1 = 0.
Die Variablen, die null gesetzt werden, nennt man auch Nichtbasisvariablen , die an-
deren Variablen Basisvariablen.
Die erste Basislösung kann sehr einfach bestimmt werden; man wählt die Schlupfvaria-
blen als Basisvariablen. Dadurch erhält man immer die zulässige Lösung x1 = 0, x2 = 0,
..., xn = 0. Die Lösung soll nun schrittweise verbessert werden, bis die optimale Lösung
erreicht ist.
Um festzustellen ob eine Lösung bereits optimal ist, genügt ein Blick auf die Zielfunk-
43
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
tion. Enthält sie noch positive Koeffizienten cj, so lässt sich der Wert der Zielfunktion
noch erhöhen. Die zugehörige Variable xj muss dann in die Basisvariablen aufgenom-
men werden (kommen keine positiven Koeffizienten cj mehr vor, dann liegt die optimale
Lösung vor).
Eine Verbesserung der Lösung erreicht man also, indem eine Basisvariable durch eine
Nichtbasisvariable ersetzt wird (d.h.: die Gesamtzahl der Basisvariablen bleibt gleich).
Praktisch wählt man jene Nichtbasisvariable aus, die den größten Koeffizienten hat. Da-
durch wird der Wert der Zielfunktion am meisten vergrößert.
Welche Variable aus der Basislösung entfernt wird, lässt sich folgendermaßen überlegen:
Die rechten Seiten des Gleichungssystems aus (A1) dürfen nicht negativ sein, also muss
für die Variable, die in die Basislösung aufgenommen werden soll, der „Engpass“ be-
stimmt werden. Es wird nun diejenige Variable aus der Basislösung entfernt, für die
man den kleinsten Wert erhält.
Hat man die Simplex - Tabelle vorliegen, nennt man diese Überlegungen auch die „Be-
stimmung des Pivotelements“. Dadurch wird bestimmt, welche Variable in die Lösung
aufgenommen wird und welche daraus entfernt wird.
Den Variablentausch möchte ich nochmals genauer angeben:
Betrachtet man die Ausgangssituation (A1) und sei ck der größte positive Koeffizient
der Zielfunktion, dann ist xk die zugehörige Variable. Sie soll nun in die Basislösung
aufgenommen werden.
Aus dem Gleichungssystem bestimmt man nun den Engpass für xk:
a1kxk ≤ b1 und a1k > 0⇒ xk ≤b1
a1k
a2kxk ≤ b2 und a2k > 0⇒ xk ≤b2
a2k
...
44
3 Lösung linearer Optimierungsaufgaben
amkxk ≤ bm und amk > 0⇒ xk ≤bm
amk
Falls einer der Koeffizienten a1k, a2k, ..., amk negativ oder null ist, wird der Quotient nicht
gebildet (Nichtnegativitätsbedingung wäre nicht erfüllt bzw. Division nicht definiert). Im
nächsten Schritt wird nun das Minimum der Quotienten bestimmt:
min( b1
a1k
,b2
a2k
, ...,bm
amk
) = bl
alk
.
Der Engpass von xk ist also durch bl
alkbestimmt. Für xk = bl
alkwird die Schlupfvariable
ul = 0.
Damit wird also die Variable ul durch xk ersetzt (d.h.: der Koeffizient alk wurde als
Pivotelement bestimmt).
Dividiert man die l-te Gleichung aus dem Gleichungssystem aus (A1) durch alk, so erhält
die Variable xk den Koeffizienten 1:
al1
alk
x1 + al2
alk
x2 + ...+ alk
alk
xk + ...+ aln
alk
xn + 0 + ...+ 1alk
ul + 0 + ...+ 0 = bl
alk
.
Aus allen anderen Gleichungen wird die Variable xk eliminiert. Dadurch erhält man ein
neues System (A2):
Nichtnegativitätsbedingungen: x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0
Gleichungssystem: al1x1 + al2x2 + ...+ 1xk + ...+ alnxn + 1alkul = bl
für i = 1, 2, ..., m und i 6= l ai1x1 + ai2x2 + ...+ 0xk + ...+ ainxn − aik
alkul + ui = bi
Zielfunktion: Z = c1x1 + c2x2 + ...+ 0xk + ...+ cnxn − ck
alkul
Für die neuen Koeffizienten gilt:
(mit j = 1, 2, ..., n und i = 1, 2, ...,m und i 6= l)
45
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
cj = (cj − alj
alkck) bi = (bi − bl
blkaik) aij = (aij − alj
alkaik).
Diese Vorgangsweise wird so lange wiederholt, bis in der Zielfunktion keine positiven Ko-
effizienten mehr vorkommen. Dann ist keine Verbesserung der Zielfunktion mehr möglich
und man hat die optimale Lösung bestimmt.
Wie im vorigen Abschnitt erwähnt, werden die Koeffizienten des Gleichungssystems und
der Zielfunktion, Lösungen und Engpässe in die Simplex-Tabelle übertragen, um die-
sen Ablauf übersichtlicher darzustellen. Ich möchte an dieser Stelle die Tabelle für die
Normalform (A1) und das System (A2) noch allgemein anführen. Dabei ist das Ausgang-
stableau und das zweite Tableau eingetragen.
Basisvariable x1 x2 ... xk ... xn u1 u2 ... un bi qi
u1 a11 a12 ... a1k ... a1n 1 0 ... 0 b1b1
a1k
u2 a21 a22 ... a2k ... a2n 0 1 ... 0 b2b2
a2k
... ... ... ... ... ... ... ... ... ... ... ... ...
ul al1 al2 ... alk ... aln 0 0 ... 0 blbl
alk
... ... ... ... ... ... ... ... ... ... ... ... ...
um am1 am2 ... amk ... amn 0 0 ... 1 bmbm
amk
Z c1 c2 ... ck ... cn 0 0 ... 0 0
u1 a11 a12 ... 0 ... a1n 1 0 ...−a1kalk
... 0 b1
u2 a21 a22 ... 0 ... a2n 0 1 ...−a2kalk
... 0 b2
... ... ... ... ... ... ... ... ... ... ... ... ...
xk al1 al2 ... 1 ... aln 0 0 ... 1alk
... 0 bl
... ... ... ... ... ... ... ... ... ... ... ... ...
um am1 am2 ... 0 ... amn 0 0 ...−amkalk
... 1 bm
Z c1 c2 ... 0 ... cn 0 0 ...− ckalk
0 0
... ... ... ... ... ... ... ... ... ... ... ... ...
46
Stelle das Ausgangstableau auf.
Ausgangswerte sind die Zahlen aij, bi, cj mit i=1, 2,…, m und j=1, 2,…, n
Die Schlupfvariablen bilden die erste Basislösung
Enthält die Zielfunktion positive Koeffizienten?
ja
Wähle die Spalte mit ck = Max (cj) als Hauptspalte. Die zugehörige
Nichtbasisvariable xk tritt in die Basis des neuen Tableaus.
Die Rechnung ist beendet. Die Lösung ist
in dem Tableau enthalten.
nein
Bestimme den kleinsten Quotienten aus den Werten bi 0 und den Koeffizienten
von der Variable, die in die Basis aufgenommen wird für alle aik > 0. Wähle die Zeile mit qi = bl : alk = Min (bi : aik) als
Hauptzeile. Das Element alk heißt Hauptelement. Die Schlupfvariable ul
scheidet aus der Basis aus.
≥
Gibt es ein qi > 0?
ja
Dividiere die Werte der l - ten Zeile (Hauptzeile) durch das Hauptelement alk und schreibe die Ergebnisse in die l - te
Zeile des neuen Tableaus: Rl
= Rl : alk
Das Problem hat keine endliche Lösung.
Subtrahiere von allen übrigen Zeilen Ri, wobei i ≠ l ist, das aik - fache der Zeile
Rl des neuen Tableaus. Schreibe die Ergebnisse in die i - te Zeile des neuen
Tableaus:
Ri = Ri - aik Rl
⎯
⎯
⎯
・⎯
nein
Der Simplex - Algorithmus kann durch folgenden Ablaufplan übersichtlich beschrieben
werden: [4, S.107]
3.3 Rechnerische Lösung linearer Programme - das Simplex-Verfahren
Ich möchte an dieser Stelle nicht näher auf andere Formen des Simplex - Algorithmus
eingehen, da dies den Rahmen der Arbeit sprengen würde. Ebenso verzichte ich an dieser
Stelle auf die verschiedenen Lösungsfälle. Diese werde ich im Kapitel 5 behandeln, soweit
diese im Schulunterricht besprochen werden.
48
4 Anwendungsbeispiele
In vielen Bereichen der Wirtschaft werden Probleme durch die lineare Optimierung ge-
löst. Im Transportwesen versucht man die Transportkosten verschiedener Güter zu mi-
nimieren; in der Landwirtschaft sollen die Nutzflächen optimal ausgenützt werden, um
einen größtmöglichen Gewinn zu erzielen und in der Organisationsplanung versucht man
kostengünstige Schicht- und Stundenpläne zu erstellen.
Ich möchte hier zwei Anwendungsbeispiele in mehreren Variablen anführen, die solche
Optimierungsprozesse beschreiben.
4.1 Beispiel 1 - Fruchtsäfte
Ein Betrieb stellt vier Fruchtsäfte her, die aus verschiedenen Zutaten (Apfelsaft, Oran-
gensaft, Karottensaft und Mangosaft) zusammengemischt werden. Die genauen Zusam-
mensetzungen der Fruchtsäfte und die Vorräte der Zutaten sind in nachstehender Tabelle
angegeben.
Apfelsaft (l) Orangensaft (l) Karottensaft (l) Mangosaft (l)
Fruchtsaft 1 50 30 0 0
Fruchtsaft 2 0 40 40 0
Fruchtsaft 3 20 20 20 20
Fruchtsaft 4 40 0 0 20
Vorrat 5000 6000 4000 3000
4.1 Beispiel 1 - Fruchtsäfte
Der Betrieb kann für einen Liter Fruchtsaft 1 einen Gewinn von e2,00 erzielen, für
Fruchtsaft 2 e1,50, für Fruchtsaft 3 e3,00 und für Fruchtsaft 4 e2,20. Wie muss der
Betrieb seine Produktion steuern, um maximalen Gewinn zu erzielen?
Dieses Problem wird durch folgende Normalform beschrieben:
x1.................. Herstellungsmenge an Fruchtsaft 1 (in Litern)
x2.................. Herstellungsmenge an Fruchtsaft 2 (in Litern)
x3.................. Herstellungsmenge an Fruchtsaft 3 (in Litern)
x4.................. Herstellungsmenge an Fruchtsaft 4 (in Litern)
u1, u2, u3, u4... nicht negative Schlupfvariablen
I) 58x1 + 1
4x3 + 23x4 + u1 = 5000
II) 38x1 + 1
2x2 + 14x3 + u2 = 6000
III) 12x2 + 1
4x3 + u3 = 4000
IV) 14x3 + 1
3x4 + u4 = 3000
Als Koeffizienten wurden jeweils die relativen Anteile der Zutaten in einem Liter Frucht-
saft verwendet.
Z = 2x1 + 1, 5x2 + 3x3 + 2, 2x4 →Max.
Natürlich müssen auch die Nichtnegativitätsbedingungen erfüllt sein:
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, u1 ≥ 0, u2 ≥ 0, u3 ≥ 0, u4 ≥ 0.
Die Lösung wurde mit dem Simplex - Algorithmus berechnet. Dazu führe ich hier die
Simplex - Tabelle an (die Pivotelemente sind jeweils eingekreist).
50
4 Anwendungsbeispiele
Basisvariable x1 x2 x3 x4 u1 u2 u3 u4 bi qi
u158 0 1
423 1 0 0 0 5000 20000
u238
12
14 0 0 1 0 0 6000 24000
u3 0 12
14 0 0 0 1 0 4000 16000
u4 0 0 14
13 0 0 0 1 3000 12000
Z1 2 1,5 3 2,2 0 0 0 0 0
u158 0 0 1
3 1 0 0 -1 2000 3200
u238
12 0 −1
3 0 1 0 -1 3000 8000
u3 0 12 0 −1
3 0 0 1 -1 1000
x3 0 0 1 43 0 0 0 4 12000
Z2 2 1,5 0 -1,8 0 0 0 -12 -36000
x1 1 0 0 815
85 0 0 −8
5 3200
u2 0 12 0 −8
5 −35 1 0 −2
5 1800 3600
u3 0 12 0 −1
4 0 0 1 -1 1000 2000
x3 0 0 1 43 0 0 0 4 12000
Z3 0 1,5 0 −4315 −16
5 0 0 -8,8 -42400
x1 1 0 0 815
85 0 0 −8
5 3200
u2 0 0 0 −1760 −3
5 1 -1 35 800
x2 0 1 0 −12 0 0 2 -2 2000
x3 0 0 1 43 0 0 0 4 12000
Z3 0 0 0 −12760 −16
5 0 -3 -5,8 -45400
Da in der Zielfunktion nun keine positiven Koeffizienten mehr vorkommen, kann die
optimale Lösung abgelesen werden:
x1 = 3200 x2 = 2000 x3=12000 x4 = 0
Z = 45400
Um den größtmöglichen Gewinn von e45400 zu erzielen, sollte der Betrieb 3200 Liter
51
4.2 Beispiel 2 - Gartenmaschinen
von Fruchtsaft 1, 2000 Liter von Fruchtsaft 2 und 12000 Liter von Fruchtsaft 3 herstellen
(Fruchtsaft 4 sollte nicht hergestellt werden).
4.2 Beispiel 2 - Gartenmaschinen
An diesem Beispiel sollen mögliche Schwierigkeiten, die beim Simplex - Algorithmus
auftreten können, illustriert werden.
Ein Unternehmen produziert und verkauft vier verschiedene Gartenmaschinen: Häcks-
ler, Rasenmäher, Kleintraktoren und Mähmaschinen. Pro Häcksler werden 1500 Euro
Gewinn erzielt, während pro Rasenmäher 3500 Euro, pro Kleintraktor 3000 Euro und
pro Mähmaschine 4000 Euro verdient wird. Das Unternehmen möchte selbstverständlich
seinen Gewinn maximieren.
Die Herstellung erfolgt in einem dreistufigen Prozess:
Stufe 1: Einzelteilfertigung
Stufe 2: Oberflächenvergütung
Stufe 3: Montage
Für die einzelnen Fertigungsstufen sind definierte Fertigungszeiten pro Produktionsein-
heit gegeben. Außerdem sind die Produktionskapazitäten in den einzelnen Fertigungsstu-
fen begrenzt. Folgende Tabelle stellt die Bedingungen dar:
Produkt Häcksler Rasenmäher Traktor Mähmaschine Kapazität
Stufe 1 3,0 1,0 3,0 4,0 315
Stufe 2 1,0 2,0 2,7 4,0 270
Stufe 3 2,0 5,0 5,5 3,0 400
Es wird erwartet, dass maximal 30 Häcksler absetzbar sind. Außerdem sollen aus be-
triebspolitischen Gründen mindestens zwölf Rasenmäher, 20 Kleintraktoren und zehn
52
4 Anwendungsbeispiele
Mähmaschinen abgesetzt werden. [9, S.35]
Es ergibt sich folgende Optimierungsaufgabe:
x1........................ Anzahl der Häcksler, die hergestellt werden
x2........................ Anzahl der Rasenmäher, die hergestellt werden
x3........................ Anzahl der Kleintraktoren, die hergestellt werden
x4........................ Anzahl der Mähmaschinen, die hergestellt werden
Nebenbedingungen: I) 3x1 + x2 + 3x3 + 4x4 ≤ 315
II) x1 + 2x2 + 2, 7x3 + 4x4 ≤ 270
III) 2x1 + 5x2 + 5, 5x3 + 3x4 ≤ 400
IV) x1 ≤ 30
V) x2 ≥ 12
VI) x3 ≥ 20
VII) x4 ≥ 10
Nichtnegativität: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
Zielfunktion: Z = 1500x1 + 3500x2 + 3000x3 + 4000x4 →Max.
Dieses lineare Programm habe ich mit Hilfe der Homepage www.simplexme.com gelöst.
Man erhält folgende Lösung:
x1 = 0 x2 = 36, 57 x3 = 20 x4 = 35, 71 Z = 330857, 14
Die berechnete Lösung löst das Problem des Unternehmers nicht, da er eine ganzzahlige
Lösung für alle Variablen braucht (man kann nur ganze Gartenmaschinen produzieren).
Eine ganzzahlige Lösung könnte zum Beispiel durch Runden erreicht werden. Dann müss-
te der Unternehmer 37 Rasenmäher und 36 Mähmaschinen herstellen. Diese Lösung ist
allerdings nicht zulässig, da die Nebenbedingungen II) und III) nicht erfüllt werden.
53
4.2 Beispiel 2 - Gartenmaschinen
Um eine ganzzahlige zulässige Lösung zu erzwingen, werden nun für die Variablen x2
und x4 weitere Bedingungen angegeben.
Für x2 soll gelten: x2 ≥ 37 oder x2 ≤ 36.
Für x4 soll gelten: x4 ≥ 36 oder x4 ≤ 35.
Daraus ergeben sich vier Kombinationsmöglichkeiten, die zu den Nebenbedingungen
noch dazu kommen. Die Lösungen wurde wieder mit Hilfe der Homepage www.simplexme.
com berechnet:
x2 ≥ 37 x2 ≥ 37 x2 ≤ 36 x2 ≤ 36
x4 ≥ 36 x4 ≤ 35 x4 ≤ 35 x4 ≥ 36
unzulässiges x1 = 0 x1 = 10 x1 = 0
Problem x2 = 37 x2 = 33 x2 = 36
x3 = 20 x3 = 20 x3 = 20
x4 = 35 x4 = 35 x4 = 36
Z = 329500 Z = 330500 Z = 330000
Die Bedingungen x2 ≥ 37 und x4 ≥ 36 liefern ein unzulässiges Problem, da die Neben-
bedingung II) verletzt wird (x1 müsste negativ sein, um die Nebenbedingung zu erfüllen
und das widerspricht den Nichtnegativitätsbedingungen).
Da es sich um eine Maximierungsaufgabe handelt, wird die ganzzahlige Lösung ausge-
wählt, die den größten Gewinn liefert: x1 = 10 x2 = 33 x3 = 20 x4 = 35.
Dabei wird ein Gewinn von e330 500 gemacht.
54
5 Lineare Optimierung im
Schulunterricht
5.1 Gesetzliche Grundlage
Die Lineare Optimierung ist in zwei Schultypen der berufsbildenden Schulen vorgesehen.
Sowohl in den höheren Lehranstalten für wirtschaftliche Berufe (HLW) als auch in den
höheren land- und forstwirtschaftlichen Lehranstalten (HLFS) ist das Thema im Lehr-
plan verankert.
Die ausführlichen Lehrpläne für das Unterrichtsfach Angewandte Mathematik können
unter [10, S.71ff] für die HLW und [11, S.43ff] für die HLFS abgerufen werden. Zur li-
nearen Optimierung sind folgende Bildungs- und Lehraufgaben im dritten bzw. vierten
Semester festgehalten:
• Lösungsbereiche linearer Ungleichungen in zwei Variablen mit Technologieeinsatz
bestimmen
• schulartenspezifische Problemstellungen durch Ungleichungssysteme mit zwei Va-
riablen modellieren
• die Zielfunktion für eine lineare Optimierung formulieren
• die Lösung einer linearen Optimierung mit Technologieeinsatz ermitteln und in-
5.1 Gesetzliche Grundlage
terpretieren sowie den Lösungsweg erklären/begründen
Schülerinnen und Schüler der zwei Schultypen, HLW und HLFS, bekommen im Rahmen
der Zentralmatura an den berufsbildenden höheren Schulen (BHS) dieselben Maturaauf-
gaben gestellt (die zwei Schultypen befinden sich im selben Cluster - W1 - für den Teil
B der Zentralmatura; Aufgaben aus dem Teil A sind für alle BHS gleich). Die genaue
Einteilung der Schultypen in die einzelnen Cluster kann unter [12] nachgelesen werden.
Im Kompetenzkatalog für die schriftliche Reife- und Diplomprüfung [13] sind die Kompe-
tenzen, die die Schüler und Schülerinnen im Bereich der linearen Optimierung erreichen
sollen ebenfalls festgehalten:
• lineare Ungleichungssysteme mit zwei Variablen modellieren
• Lösungsbereich mit Technologieeinsatz ermitteln, interpretieren und im Kontext
argumentieren
• Zielfunktion aufstellen
• die optimalen Lösungen mittels Technologieeinsatz ermitteln und interpretieren
• Lösungsweg erklären
Dort wird auch angemerkt, dass die Begriffe Nichtnegativitätsbedingung (Nichtnega-
tivitätskriterium) und Lösungsbereich (zulässiger Bereich) im Rahmen der Reife- und
Diplomprüfung als bekannt vorausgesetzt werden.
Im Lehrplan wird damit vorgegeben, dass die Schüler und Schülerinnen Kompetenzen
in vier Handlungsdimensionen erreichen sollen:
• Modellieren und Transferieren (A)
• Operieren und Technologieeinsatz (B)
56
5 Lineare Optimierung im Schulunterricht
• Interpretieren und Dokumentieren (C)
• Argumentieren und Kommunizieren (D)
Kompetenzen in diesen vier Handlungsdimensionen werden durch die Zentralmatura
abgeprüft. Dadurch sind auch die Lehrpersonen gefordert, diese Handlungsdimensionen
im Mathematikunterricht einzubauen und regelmäßig zu üben.
Im Bereich der linearen Optimierung können alle Handlungsdimensionen im Unterricht
eingebaut werden (vgl. Schulbeispiele).
5.2 GeoGebra - die Geometrie Software
Im Mathematikunterricht werden eine Vielzahl von Technologien verwendet. So kommen
zum Beispiel grafikfähige Taschenrechner oder Computeralgebrasysteme (CAS) verschie-
dener Hersteller zum Einsatz.
Ich möchte an dieser Stelle die Software GeoGebra näher vorstellen, da ich der Über-
zeugung bin, dass diese für die lineare Optimierung die beste Wahl ist. Ich habe bereits
selber an einer Schule unterrichtet und die Schülerinnen dieser Schule haben GeoGebra
leider nicht verwendet (technische Ausstattung der Klassenräume war nicht gegeben).
Die Schülerinnen mussten also lineare Optimierungsaufgaben mit einem graphikfähigen
Taschenrechner bzw. händisch lösen. Aus Kostengründen wurde ein relativ günstiger Ta-
schenrechner gewählt, daher war das Graphikfenster sehr klein und leider nur schwarz -
weiß. Die graphische Darstellung war unbefriedigend.
In mehreren Mathematikfortbildungen für BHS - Lehrpersonen wurde über den Tech-
nologieeinsatz gesprochen bzw. Erfahrungen mit den verschiedenen Technologien aus-
getauscht. Dort habe ich gehört, dass alle Lehrpersonen, die die technischen Voraus-
setzungen zur Verfügung haben, oder in Laptop - Klassen unterrichten, inzwischen mit
GeoGebra arbeiten (auch bei Schularbeiten). All jene, die noch nicht mit GeoGebra ar-
57
5.2 GeoGebra - die Geometrie Software
beiten streben dies in nächster Zeit an. Ich denke, dass der Großteil der Schulen in den
nächsten Jahren auf GeoGebra umsteigen wird.
Was ist GeoGebra?
Der Name GeoGebra setzt sich aus Geometrie und Algebra zusammen. GeoGebra ist
eine kostenlose dynamische Mathematiksoftware [...]. Sie verbindet Geometrie, Algebra,
Tabellen, Zeichnungen, Statistik und Analysis in einem einfach zu bedienenden Softwa-
repaket [14].
Die Software wurde vom Salzburger Markus Hohenwarter im Jahr 2002 im Zuge seiner
Diplomarbeit an der Universität Salzburg entwickelt und im Rahmen seiner Doktorarbeit
weiterentwickelt. Seither wurde die Software mehrfach ausgezeichnet. Eine Auflistung al-
ler Auszeichnungen kann unter [14] abgerufen werden.
GeoGebra wurde als Open Source Programm entwickelt, das heißt dass sowohl die Pro-
grammierer als auch die Nutzer das Programm verändern können. Dadurch hat sich die
Software sehr schnell weiterentwickelt und es wurden ständig neue Anwendungen hinzu-
gefügt. Aktuell sind die Versionen GeoGebra 5 und GeoGebra 6 verfügbar. Die Software
kann gratis über die Homepage www.geogebra.org/download heruntergeladen werden
(für PC, Tablet oder Smartphone).
Vorteile von GeoGebra:
• kostenlose Software
• Algebra, Geometrie und Tabellenkalkulation sind in einem Programm vereint (ein
Programm für alle Anwendungen)
• Perspektivenwechsel möglich (vor allem zwischen Algebra und Geometrie)
• dynamische Software (Zugmodus - Punkte/Objekte auf der Zeichenebene können
58
5 Lineare Optimierung im Schulunterricht
verschoben werden; alle davon abhängigen Objekte passen sich automatisch an)
• interaktive Unterrichtsmaterialien verfügbar
• benutzerfreundliche Oberfläche (Befehle in der Eingabezeile werden angezeigt)
Nachteil von GeoGebra:
• AnwenderInnen müssen über PC, Tablet oder Smartphone verfügen
Das Grafikfenster:
Im Lehrplan wird vorgeschrieben, den Lösungsbereich eines Ungleichungssystems in zwei
Variablen ermitteln zu können. Da der Lösungsbereich einem Vieleck im R2 entspricht,
kann dies in GeoGebra mit dem Graphikfenster ermittelt werden. Die folgende Abbil-
dung 5.1 zeigt den Startbildschirm mit dem Graphik- und Algebrafenster.
Abbildung 5.1: Startbildschirm bei GeoGebra 5
Wird in der Eingabezeile eine Ungleichung in zwei Variablen x und y eingegeben, so er-
59
5.3 Anwendung in der Schule
scheint direkt im Graphik - Fenster die zugehörige Gerade und der Lösungsbereich wird
farbig markiert (vgl. Abbildungen 3.1 und 3.2). Die Ungleichung erscheint im Algebra -
Fenster.
Um Elemente in der Graphik zu bewegen, muss das Pfeil - Symbol in der Werzeugleis-
te aktiviert sein. Bei der linearen Optimierung kann auch der Schieberegler verwendet
werden. dazu muss dieser in der Werkzeugleiste ausgewählt werden. Die genauen Vor-
gangsweisen werde ich später noch genauer erläutern.
5.3 Anwendung in der Schule
5.3.1 Lineare Ungleichungen und Ungleichungssysteme
Bevor man das Thema „lineare Optimierung“ beginnen kann, muss als Vorbereitung das
graphische Lösen einer linearen Ungleichung in zwei Variablen x und y besprochen wer-
den. Da im Vorfeld (1. Klasse) das Lösen linearer Gleichungssysteme in 2 oder mehreren
Variablen behandelt wird, kann darauf aufgebaut werden. Die Schüler und Schülerinnen
wissen bereits, dass die Lösungen einer Gleichung in zwei Variablen ax + by = c (mit
a, b und c ∈ R) auf einer Geraden liegen.
Diese Gerade teilt die Ebene in 2 Halbebenen, die jeweils durch eine Ungleichung be-
schrieben werden (vgl. Abschnitt 3.1.1). Ist die Ungleichung ax+ by ≤ c gegeben, so ist
eine Halbebene die Lösungsmenge der Ungleichung. Um festzustellen, welche Halbebene
nun die Lösungsmenge darstellt, setzt man einen Punkt einer Halbebene, der nicht auf
der Geraden liegt, in die Ungleichung ein. Erfüllt dieser Punkt die Ungleichung, so ist
jene Halbebene, in der der Punkt liegt die Lösungsmenge. Sonst ist es die andere Halb-
ebene.
Das Relationszeichen entscheidet, ob die Gerade selbst zur Lösungsmenge gehört.
60
5 Lineare Optimierung im Schulunterricht
Wird eine lineare Ungleichung in 2 Variablen graphisch mit GeoGebra gelöst, so wird
die Lösungsmenge automatisch gefärbt und die Randgerade je nach Relationszeichen
durchgezogen oder strichliert gezeichnet (siehe Abb. 3.1 und 3.2). Es entfällt also die
Überprüfung welche Halbebene der Lösungsmenge entspricht.
In der Praxis würde ich am Beginn des Themas trotzdem ein paar Übungen händisch
lösen. Einerseits kann so die Konstruktion von Geraden im Koordinatensystem wieder-
holt werden und andererseits sollen die Schüler und Schülerinnen auch selbst in der Lage
sein, die richtige Halbebene auszuwählen. Es ist meiner Meinung nach sehr wichtig, dass
die mathematischen Hintergründe zuerst verstanden werden. Erst wenn klar ist, welche
Entscheidungen oder Rechenschritte notwendig sind, sollte man den Vorteil einer Soft-
ware ausnützen. Ansonsten besteht die Gefahr, dass sich die Schüler und Schülerinnen
zu sehr auf die Software verlassen.
Eingabe bei GeoGebra:
Die Ungleichung wird in der Eingabezeile eingegeben. Dabei verwendet man <= für ≤
und >= für ≥. Falls Dezimalzahlen als Koeffizienten auftreten, schreibt man in Geo-
Gebra einen Punkt für das Komma. Die Randgerade und die gefärbte Lösungsmenge
erscheinen im Graphikfenster.
Lineare Ungleichungssysteme bestehen aus zwei oder mehreren linearen Ungleichungen.
Jede Ungleichung legt eine Halbebene fest. Der Durchschnitt aller Lösungsmengen bil-
det die Lösungsmenge des Ungleichungssystems (das sind also all jene Punkte, die alle
Ungleichungen erfüllen).
Eingabe bei GeoGebra:
Bei GeoGebra können Ungleichungssysteme auf zwei Arten eingegeben werden. Man
kann jede Ungleichung einzeln eingeben und bekommt jeweils eine gefärbte Halbebene als
61
5.3 Anwendung in der Schule
Lösungsmenge. Der Bereich der am Ende am dunkelsten gefärbt ist, ist die Lösungsmenge
des Systems. Oder man gibt in der Eingabezeile alle Ungleichungen des Systems ein
und trennt diese durch &&. Dann werden alle Randgeraden gezeichnet, aber nur die
Lösungsmenge aller Ungleichungen gefärbt. Wenn ein System aus vielen Ungleichungen
besteht, ist die zweite Variante zu empfehlen, da die Übersichtlichkeit erhöht wird. Beide
Möglichkeiten werden in den Abbildungen 5.2 und 5.3 für ein Ungleichungssystem mit
drei Ungleichungen dargestellt.
Abbildung 5.2: Einzelne Eingabe der Ungleichungen
Abbildung 5.3: Gemeinsame Eingabe der Ungleichungen
62
5 Lineare Optimierung im Schulunterricht
Nach der Eingabe der Ungleichungen kann die Größe der Achsen bearbeitet werden, um
den ganzen Lösungsbereich zu sehen. Dazu kann entweder bei den Graphik - Einstellun-
gen (rechter Mausklick auf das Graphik - Fenster) unter Grundeinstellungen der Bereich
der Achsen festgelegt werden, den man sehen will. Dort kann auch die Beschriftung und
die Skalierung verändert werden. Oder man verwendet die Scroll - Funktion der Maus.
Dadurch verändert sich die Größe der Achsen.
Der Lösungsbereich eines Ungleichungssystems kann beschränkt, unbeschränkt oder leer
sein. Dies wird in den folgenden Abbildungen 5.4, 5.5 und 5.6 veranschaulicht.
Abbildung 5.4: beschränkt Abbildung 5.5: unbeschränkt Abbildung 5.6: leer
Das graphische Lösen einer linearen Ungleichung in zwei Variablen und das Bestimmen
der Lösungsmenge eines Ungleichungssystems muss im Vorfeld mit den Schülern und
Schülerinnen gut eingeübt werden; bildet es doch die Grundlage der linearen Optimie-
rung. In Schulbüchern ( [15], [16] oder [17]) wird diesen Themen eine große Anzahl an
Beispielen gewidmet. Es gibt dazu auch sehr viele Beispiele, bei denen ein Lösungsbereich
graphisch vorgegeben ist und die Schüler und Schülerinnen das passende Ungleichungs-
system dazu aufstellen sollen. Solche Aufgaben fallen in die Handlungsdimensionen A
und C; diese Dimensionen sind besonders wichtig, um das mathematische Verständnis
zu fördern. Besonders wenn die graphische Lösung mittels GeoGebra ermittelt wird,
können solche Beispiele helfen die mathematischen Hintergründe und Grundlagen zu
wiederholen bzw. verfestigen.
63
5.3 Anwendung in der Schule
Meist sind auch einige Beispiele zum Modellieren von linearen Ungleichungen angeführt
(Dimension A). Aus eigener Unterrichtserfahrung kann ich berichten, dass sich Schüler
und Schülerinnen teilweise sehr schwer tun, aus einem Text eine Ungleichung zu mo-
dellieren. Deshalb finde ich es wichtig auch diesen Typ von Aufgaben gut zu üben. Die
Kompetenz des Modellierens/Transferierens spielt nicht nur in der linearen Optimie-
rung eine große Rolle, sondern wird bei vielen weiteren Themen, die im Schulunterricht
behandelt werden (Polynomfunktionen vom Grad 2, 3 und 4; lineare und quadratische
Gleichungen; Aufstellen von Formeln) benötigt.
Um die Modellierung eines Ungleichungssystems etwas zu erleichtern, kann meistens
eine Tabelle zur übersichtlicheren Darstellung der Textangabe aufgestellt werden. Die
Ungleichungen können dann abgelesen werden. Ich möchte dazu ein Beispiel aus einem
Schulbuch angeben.
Ein Hersteller für Modeschmuck hat 800 Glasperlen und 500 Metallperlen gekauft. Die-
se werden nun in zwei verschiedenen Arten von Schmuckstücken verarbeitet. Für jede
Kette „Melanie“ werden 20 Glasperlen und 10 Metallperlen verarbeitet, für jede Kette
„Sophia“ werden 30 Glasperlen und 20 Metallperlen verarbeitet. Stelle in einem geeig-
neten Koordinatensystem dar, welche Möglichkeiten der Hersteller zur Produktion von x
Stück „Melanie“ und y Stück „Sophia“ hat. [16, S.26, Aufgabe 116]
Dieses Beispiel wird den Handlungsdimensionen A und B zugeordnet.
Der Sachverhalt wird nun übersichtlich in einer Tabelle dargestellt, die Wahl der Varia-
blen ist schon vorgegeben.
Kette Melanie (x) Kette Sophia (y) Verfügbarkeit
Anzahl Glasperlen 20 30 800
Anzahl Metallperlen 10 20 500
64
5 Lineare Optimierung im Schulunterricht
Nun können die Ungleichungen zeilenweise abgelesen werden. Die erste Zeile beschreibt
den Verbrauch an Glasperlen, die zweite Zeile den Verbrauch an Metallperlen (bei Her-
stellung von x Ketten „Melanie“ und y Ketten „Sophia“). Die Nichtnegativitätsbedin-
gungen müssen ebenfalls angegeben werden:
I) 20x+ 30y ≤ 800
II) 10x+ 20y ≤ 500
III) x ≥ 0
IV) y ≥ 0
Die Lösung dieses Ungleichungssystems soll nun graphisch in einem Koordinatensystem
dargestellt werden. Die Lösungsmenge wurde mit GeoGebra bestimmt; siehe Abbildung
5.7.
Abbildung 5.7: Möglichkeiten der Produktion für x Ketten „Melanie“ und y Ketten „Sophia“
Der blau markierte Lösungsbereich gibt nun alle möglichen Produktionsmengen an. So
kann der Hersteller zum Beispiel jeweils 10 Ketten beider Modelle herstellen. Er könnte
auch 40 Ketten des Modells „Melanie“ und keine Kette des Modells „Sophia“ produ-
zieren. Da der Hersteller nur ganze Ketten herstellen kann, kommen alle ganzzahligen
Zahlenpaare des Lösungsbereiches als Möglichkeit in Frage.
65
5.3 Anwendung in der Schule
Im folgenden Teil der Arbeit gehe ich davon aus, dass die Schüler und Schülerinnen
das Modellieren und Lösen von linearen Ungleichungssystemen bereits gut geübt haben.
Ebenso können sie den Lösungsbereich mit GeoGebra ermitteln.
5.3.2 Lineare Optimierung - Maximumsaufgaben
Bevor ich in der Schule mit den ersten Beispielen starte, möchte ich den Schülern und
Schülerinnen einen kurzen Einblick in die Geschichte der linearen Optimierung geben.
Dazu würde ich die Entwicklung in den 40er Jahren mit den ersten Anwendungen erläu-
tern und die Verleihung des Nobelpreises für Wirtschaftswissenschaften 1975 erwähnen
(siehe Kapitel 1). Dadurch sollte die wirtschaftliche Bedeutung dieses Themas hervor-
gehoben werden.
Sehr oft bekommen Lehrpersonen an Schulen die Fragen gestellt: „Warum lernen wir
das? Wozu brauchen wir das?“
Solchen Fragen kann man mit einem kurzen geschichtlichen Einblick bei der linearen
Optimierung zuvorkommen. Ebenso glaube ich, dass der Hintergrund der Optimierung
sehr gut nachvollziehbar ist. Jede/r kann wohl zustimmen, dass man beim Verkauf von
einem beliebigen Produkt den größtmöglichen Gewinn herausholen will bzw. beliebige
Kosten möglichst gering halten will.
Ich möchte nun die Begriffe „lineare Optimierungsaufgabe“, „Zielfunktion“, „zulässiger
Bereich“ und „optimaler Punkt“ einführen, so wie sie im Schulunterricht gebraucht wer-
den.
Zielfunktion:
Eine Zielfunktion ist eine lineare Funktion Z in zwei Variablen x und y von R2 nach
R; dabei gilt für alle Zahlenpaare (x, y) ∈ R2: Z(x, y) = ax + by mit a, b ∈ R. Die
Zielfunktion wird für die Zielvorgabe formuliert (Gewinn bzw. Kosten).
66
5 Lineare Optimierung im Schulunterricht
Lineare Optimierungsaufgabe:
Eine lineare Optimierungsaufgabe ist durch ein lineares Ungleichungssystem in zwei Va-
riablen und durch eine lineare Zielfunktion gegeben.
Zulässiger Bereich:
Der Lösungsbereich des Ungleichungssystems heißt zulässiger Bereich.
Optimaler Punkt:
Im zulässigen Bereich wird jener Punkt gesucht, dessen Funktionswert bezüglich der
Zielfunktion Z möglichst groß bzw. klein ist. Man nennt diesen Punkt den optimalen
Punkt.
Anhand zweier Schulbeispiele möchte ich nun die Vorgehensweise beim Lösen von Ma-
ximumsaufgaben erläutern. Dazu werde ich auch immer die notwendigen Schritte zur
Lösung mit GeoGebra angeben.
Eine Textilfabrik stellt Hemden und Pullover her. Täglich können 70 Hemden und 100
Pullover erzeugt werden, jedoch besteht ein Produktionslimit von insgesamt 140 Stück.
Die Herstellungskosten pro Hemd betragen e20, pro Pullover e15. Hemden werden zu
e45 pro Stück, Pullover zu e35 pro Stück verkauft.
a) Ermitteln Sie, wie viele Hemden und Pullover erzeugt werden müssen, um maximalen
Gewinn zu erzielen.
b) Berechnen Sie den maximalen Gewinn.
[15, S.13, Aufgabe 1.17]
Diese Aufgabe wird den Handlungsdimensionen A und B zugeordnet.
Zuerst muss aus der Angabe das lineare Ungleichungssystem modelliert werden. In die-
sem Fall können die Ungleichungen direkt über die Stückzahlen für Hemden und Pull-
over aufgestellt werden (Darstellung in Tabellenform braucht man hier nicht), dabei gilt:
x ... Anzahl der Hemden, die erzeugt werden
67
5.3 Anwendung in der Schule
y ... Anzahl der Pullover, die erzeugt werden
I) x ≤ 70
II) y ≤ 100
III) x+ y ≤ 140
IV) x ≥ 0
V) y ≥ 0
Für die Beschreibung des Gewinns wird die Zielfunktion aufgestellt. Der Gewinn pro
Hemd bzw. Pullover wird durch die Differenz aus Verkaufspreis und Herstellungskosten
bestimmt: Z(x, y) = 25x+ 20y →Max.
Dieses Ungleichungssystem wird graphisch mit GeoGebra gelöst. Zusätzlich wird die
Zielfunktion eingezeichnet. Dazu wählt man einen Wert für Z. Meistens wählt man am
Beginn den Wert 0, sodass die Zielfunktion durch den Ursprung des Koordinatensystems
verläuft. Alle Punkte auf dieser Geraden liefern bezüglich Z den Wert 0. Diese Gerade
wird dann parallel verschoben. Dadurch ändert sich jeweils der Wert von Z. Durch die
Wertänderung kann auch die Richtung bestimmt werden, in die die Zielfunktion verscho-
ben werden muss (bei Maximumsaufgaben sollt der Wert ständig vergrößert werden).
Diese Verschiebung wird solange durchgeführt, bis der Wert der Zielfunktion möglichst
groß ist, aber die Gerade noch durch einen Punkt des zulässigen Bereiches verläuft. Dies
ist dann der optimale Punkt.
Die Koordinaten des optimalen Punktes geben dann die optimalen Produktionsmengen
für Hemden und Pullover an.
Vorgehensweise bei GeoGebra:
Als erstes wird das Ungleichungssystem bei GeoGebra eingegeben. Ich bevorzuge die
gemeinsame Eingabe der Ungleichungen, da der zulässige Bereich besser ersichtlich ist.
Dieser Schritt wurde im Vorfeld bereits geübt, sodass dabei im Unterricht keine Proble-
68
5 Lineare Optimierung im Schulunterricht
me entstehen sollten.
Zusätzlich wird dann die Zielfunktion mit dem Wert null eingegeben; dies ist in der
Abbildung 5.8 dargestellt. Die Größe des Koordinatensystems muss angepasst werden.
Abbildung 5.8: Lösungsbereich und Zielfunktion mit Wert 0
Nun soll die Zielfunktion parallel verschoben werden. Dazu wird das Pfeil - Symbol in
der Werkzeugleiste aktiviert. Die Zielfunktion kann in der Graphik - Ansicht verschoben
werden. Gleichzeitig ändert sich der Wert von Z im Algebra - Fenster. Damit kann sofort
die Richtung des Verschiebens ermittelt werden; der Wert von Z soll sich vergrößern. In
der folgenden Abbildung 5.9 ist das Verschieben der Zielfunktion dargestellt. Es fällt auf,
dass durch das Vergrößern des Zielfunktion - Wertes die Gerade „nach oben“ verschoben
wird. Das heißt, man soll die Zielfunktion bei Maximumsaufgaben so verschieben, dass
sich ihr Ordinatenabschnitt vergrößert.
Der optimale Punkt muss noch im zulässigen Bereich liegen. Die Koordinaten können
abgelesen werden: x = 70 und y = 70.
Die Textilfabrik soll 70 Stück Hemden und 70 Stück Pullover erzeugen um maximalen
69
5.3 Anwendung in der Schule
Gewinn zu erzielen.
Der maximale Gewinn wird durch Einsetzen des optimalen Punktes in die Zielfunktion
bestimmt: Z(70, 70) = 25 · 70 + 20 · 70 = 3150 Euro.
Abbildung 5.9: Parallelverschieben der Zielfunktion und optimaler Punkt
Ein Nachteil der gemeinsamen Eingabe der Ungleichungen liegt darin, dass der opti-
male Punkt nicht als Schnittpunkt der Geraden, die den zulässigen Bereich begrenzen,
bestimmt werden kann. Für die Schnittpunktsberechnung müssen bei GeoGebra zwei
Geraden ausgewählt werden. Die begrenzenden Geraden gelten aber als ein Element, da
sie gemeinsam eingegeben wurden.
Sollte das Ablesen der Koordinaten also nicht genau möglich sein, muss der Schnitt-
punkt noch extra bestimmt werden. Das kann man entweder in der CAS - Ansicht
durch Gleichsetzen der beiden Geraden machen oder in einer separaten Datei graphisch
(die zwei begrenzenden Geraden getrennt als zwei Geraden eingeben und dann Schnitt-
punkt bestimmen).
Bei diesem Beispiel kann der optimale Punkt gut abgelesen werden, sodass eine separate
Berechnung nicht nötig ist. Eventuell muss man in das Graphik - Fenster hineinzoomen
(mit Maus scrollen).
70
5 Lineare Optimierung im Schulunterricht
An einem zweiten Beispiel möchte ich nun eine andere Möglichkeit zeigen, um bei Geo-
Gebra den optimalen Punkt zu finden.
Lieselotte möchte 180.000 e in zwei verschiedene Aktien investieren. Die erste Aktie
kostet 25 e pro Stück, die zweite Aktie kostet 45 e pro Stück. Bei der ersten Aktie
ist eine Gewinnausschüttung von 5,30 e pro Stück zu erwarten, bei der zweiten Aktie
2,10 e pro Stück. Lieselotte möchte mindestens 20.000 e, aber höchstens ein Drittel des
Geldes in die erste Aktie investieren. Sie möchte allerdings mindestens 1000 Stück von
der zweiten Aktie kaufen.
a) Stelle die von Lieselotte geforderten Bedingungen als Ungleichung auf.
b) Berechne, wie viele Stück von jeder Aktie Lieselotte kaufen sollte, damit ein maximaler
Gewinn erzielt werden kann. Bestimme den maximalen Gewinn.
[17, S. 13, Aufgabe 1.24]
Diese Aufgabe wird den Handlungsdimensionen A, B und C zugeordnet.
Zuerst werden die Variablen festgelegt und die Ungleichungen modelliert. Ich verzichte
an dieser Stelle darauf, die Angabe übersichtlich in einer Tabelle zusammenzufassen. Im
Schulunterricht würde ich diese Tabelle im Vorfeld anschreiben, wenn ich das Gefühl
habe, dass die Schüler und Schülerinnen noch Schwierigkeiten beim Modellieren haben.
x ... Stückzahl von Aktie 1
y ... Stückzahl von Aktie 2
71
5.3 Anwendung in der Schule
I) 25x ≥ 20000 (Investition in e in Aktie 1)
II) 25x ≤ 60000 (Investition in e in Aktie 1)
III) 25x+ 45y ≤ 180000 (Gesamtinvestition in e)
IV) y ≥ 1000 (Mindestanzahl der Aktie 2)
V) x ≥ 0 (Nichtnegativität)
VI) y ≥ 0 (Nichtnegativität)
Als Zielfunktion wird die Höhe des Gewinns formuliert: Z(x, y) = 5, 30x+2, 10y →Max.
Vorgehensweise bei GeoGebra:
Das Ungleichungssystem wird graphisch wieder mit GeoGebra dargestellt. Bei diesem
Beispiel wähle ich die Variante, die Ungleichungen einzeln einzugeben. Für die Sicht-
barkeit des zulässigen Bereiches muss die Bildgröße durch Scrollen angepasst werden.
Der zulässige Bereich ist das dunkelste Vieleck im Koordinatensystem (die Nichtnegati-
vitätsbedingungen lässt man bei der Einzeleingabe meist weg, um die Übersichtlichkeit
zu erhöhen), siehe dazu Abbildung 5.10.
An diesem Beispiel möchte ich die Verwendung des sogenannten Schiebereglers für die
Gewinnfunktion erläutern. Zuerst muss in der Werkzeugleiste der Schieberegler akti-
viert werden und man klickt auf die Position im Graphikfenster, wo der Schieberegler
positioniert werden soll. Es öffnet sich ein eigenes Fenster um die Eigenschaften des
Schiebereglers anzulegen. Dabei werden folgende Einstellungen benötigt:
• Zahl (da der Gewinn durch eine Zahl ausgedrückt wird)
• Namen für diese Zahl wählen, z.B.: Gewinn
• unter Intervall wird die Größe des Gewinns festgelegt: von null (kleinstmöglicher
Gewinn) bis 20000 (größtmöglicher Gewinn - muss abgeschätzt werden); Schritt-
weite ist bereits vorgegeben
72
5 Lineare Optimierung im Schulunterricht
• unter Schieberegler wird die Ausrichtung des Schiebereglers festgelegt (automatisch
horizontal oder man stellt auf vertikal um)
Zum Abschluss wird noch die Gewinnfunktion eingegeben und zwar unter dem Namen
des Schiebereglers, also Gewinn = 5, 30x + 2, 10y. Dadurch erscheint die Gewinnfunkti-
on im Graphikfenster (siehe Abb. 5.10). Der Gewinn ist auf null (kleinstmöglicher Wert)
gestellt, daher verläuft die Gerade durch den Ursprung. Um die Zielfunktion nun zu
Abbildung 5.10: Zulässiger Bereich und Zielfunktion Z mit Schieberegler
verschieben, muss der „Bewegen - Button“ aktiviert werden. Direkt beim Schieberegler
kann der Gewinn erhöht werden und dadurch wird die Gerade der Zielfunktion paral-
lelverschoben. In der Abbildung 5.11 ist die Zielfunktion für einen Gewinn von e17400
dargestellt.
73
5.3 Anwendung in der Schule
Abbildung 5.11: Verstellen des Schiebereglers
Der Schieberegler kann nun soweit erhöht werden, bis der optimale Punkt erreicht wird.
Dazu kann auch ein Zoomen notwendig sein. Um den optimalen Punkt genau zu be-
stimmen ist es am Besten, den entsprechenden Eckpunkt des zulässigen Bereiches zu
berechnen.
Dazu müssen die beiden Randgeraden geschnitten werden, die den Eckpunkt bestimmen.
Man öffnet die CAS - Ansicht und kann unter dem Befehl „Löse (<Liste von Gleichun-
gen>, <Liste von Variablen>)“ die zwei Geradengleichungen in den Variablen x und y
eingeben, also Löse({25x = 60000, 25x + 45y = 180000}, {x, y}). Diese Vorgehensweise
im CAS kennen die Schüler und Schülerinnen bereits vom Thema lineare Gleichungssys-
teme (in zwei oder mehreren Variablen).
Dadurch erhält man nun den Schnittpunkt (2400|2666,67). Dieser kommt als optimaler
Punkt allerdings nicht in Frage, weil Lieselotte nicht 2666,67 Stück der Aktie 2 kaufen
kann. Man sucht also eine ganzzahlige Lösung.
74
5 Lineare Optimierung im Schulunterricht
Nun zoomt man soweit zum berechneten Schnittpunkt, dass man ganzzahlige Lösungen
im zulässigen Bereich „sehen kann“. In der Abbildung 5.12 sind drei mögliche ganzzah-
lige Lösungen markiert (Punkte A, B, C), die in der Nähe des berechneten Schnitt-
punktes liegen. Man wählt nun jenen Punkt als optimalen Punkt aus, der bezüglich
der Gewinnfunktion den größten Wert liefert. Graphisch bedeutet das, dass die Gerade
der Zielfunktion einen möglichst großen Ordinatenabschnitt besitzt. Für dieses Beispiel
bedeutet das, dass der Punkt A der optimale Punkt ist. Seine Koordinaten können ab-
gelesen und der Gewinn berechnet werden:
x = 2400 und y = 2666.
Lieselotte soll also 2400 Stück der Aktie 1 und 2666 Stück der Aktie 2 kaufen. Sie kann
einen Gewinn von e18 318,6 erwarten.
Abbildung 5.12: Aufsuchen einer ganzzahligen Lösung
5.3.3 Lineare Optimierung - Minimumsaufgabe
Im Schulunterricht werden sowohl Maximal- als auch Minimalprobleme behandelt. Ich
gebe an dieser Stelle ein Schulbeispiel zu einem Transportproblem an, um das Auffinden
des optimalen Punktes zu erläutern. Die Vorgehensweise bei der Modellierung und dem
75
5.3 Anwendung in der Schule
graphischen Lösen des Ungleichungssystems bleibt gleich wie im vorigen Abschnitt.
Ein Holzhändler verfügt über zwei Lagerplätze P1 und P2, auf denen er 360 bzw. 240
Paletten Brennholz lagert. Drei Hotels H1, H2 und H3 sollen mit 240, 160 bzw. 200 Pa-
letten beliefert werden. Die Transportkosten in Euro werden in der Tabelle dargestellt:
von
zuHotel 1 Hotel 2 Hotel 3
Lagerplatz 1 6 8 4
Lagerplatz 2 6 6 6
a) Stellen Sie das Ungleichungssystem zur Ermittlung der minimalen Kosten auf.
b) Berechnen Sie die minimalen Transportkosten.
[15, S.15, Aufgabe 1.24]
Diese Aufgabe wird den Handlungsdimensionen A und B zugeordnet.
Bei den Aufgaben zu den Transportproblemen bietet sich eine Tabelle zur Darstellung
der beförderten Mengen an. Zuerst werden jedoch die Variablen festgelegt. Es sei
x ... Anzahl der Paletten, die von P1 zu H1 geliefert werden
y ... Anzahl der Paletten, die von P1 zu H2 geliefert werden.
von
zuH1 H2 H3 Verfügbarkeit
P1 x y 360− (x+ y) 360
P2 240− x 160− y 200− [360− (x+ y)] 240
benötigte Menge 240 160 200
76
5 Lineare Optimierung im Schulunterricht
Anhand dieser Tabelle kann das Ungleichungssystem aufgestellt werden. Die Anzahl der
transportierten Paletten soll jeweils größer oder gleich null sein (die Klammerausdrücke
wurden soweit wie möglich vereinfacht):I) x ≥ 0
II) y ≥ 0
III) 360− x− y ≥ 0
IV) 240− x ≥ 0
V) 160− y ≥ 0
VI) −160 + x+ y ≥ 0
Die Zielfunktion wird für die entstehenden Kosten aufgestellt:
Z(x, y) = 6x+8y+4 ·(360−x−y)+6 ·(240−x)+6 ·(160−y)+6 ·(−160+x+y)→Min.
Die Zielfunktion kann noch ausmultipliziert und zusammengefasst werden; dadurch er-
gibt sich:
Z(x, y) = 2880 + 2x+ 4y →Min.
Vorgehensweise bei GeoGebra:
Die Abbildung 5.13 zeigt den zulässigen Bereich (die Ungleichungen wurden einzeln
eingegeben, daher ist das „dunkelste“ Vieleck der zulässige Bereich). Nach Eingabe der
Zielfunktion bei GeoGebra mit dem Wert Z = 0, verläuft diese unterhalb des Ursprungs.
Die Gerade der Zielfunktion kann durch den „Bewegen - Button“ in den Ursprung ver-
schoben werden.
Da die Zielfunktion nun die Kosten des Holzhändlers beschreibt, wird ein Punkt des zu-
lässigen Bereiches gesucht, sodass der Wert der Zielfunktion möglichst gering ist. Dazu
wird die Zielfunktion in Richtung des zulässigen Bereiches parallel verschoben. Bereits
der erste Punkt des zulässigen Bereiches, der durch das Verschieben getroffen wird,
kommt als optimaler Punkt in Frage. Dieser ist in der Abbildung 5.13 ebenfalls mar-
kiert.
77
5.3 Anwendung in der Schule
Die Zielfunktion soll bei Minimalproblemen also einen möglichst kleinen Ordinatenab-
schnitt aufweisen.
Abbildung 5.13: Graphische Lösung zum Beispiel Holzhändler
Die Koordinaten des optimalen Punktes können abgelesen werden: (160|0). Dadurch er-
geben sich folgende Liefermengen:
von
zuH1 H2 H3
P1 160 0 200
P2 80 160 0
Die dabei entstehenden Transportkosten ergeben sich durch Einsetzen des optimalen
Punktes in die Zielfunktion: Z(160, 0) = 2880 + 2 · 160 + 4 · 0 = 3200 e.
78
5 Lineare Optimierung im Schulunterricht
5.3.4 Mehrdeutige Lösung bei der linearen Optimierung
Nicht in allen Fällen gibt es eine eindeutige Lösung des Optimierungsproblems. Auch im
Schulunterricht wird darauf eingegangen. Ich finde es wichtig, dass Schüler und Schü-
lerinnen auch wissen, dass nicht jedes Optimierungsproblem eindeutig lösbar ist bzw.
manche Probleme auch unlösbar sein können. Damit sollen die Schüler und Schülerin-
nen Grenzen und Einschränkungen der linearen Optimierung kennen lernen. Ich möchte
dazu wieder ein Beispiel aus einem Schulbuch anführen.
Ein Landwirt lagert 2 Arten von Düngemittel D1 und D2. Diese enthalten pro Kilogramm
Phosphor, Stickstoff und Kalium in den in der Tabelle angegebenen Mengeneinheiten
(ME).
Stickstoff Phosphor Kalium
D1 6 3 10
D2 6 6 4
Die Mischung beider Düngemittel muss mindestens 54 ME Stickstoff, 30 ME Phosphor,
und 48 ME Kalium enthalten. Die Preise pro ME des Düngemittels sind gleich hoch,
nämlich 3,5 GE/ME.
a) Erstelle eine graphische Darstellung des möglichen Lösungsbereichs.
b) Ermittle, welche Menge von beiden Düngemitteln verwendet werden sollten, um eine
möglichst billige Mischung herzustellen. Berechne die Höhe der Kosten für die optimale
Mischung.
[17, S. 17, Aufgabe 1.35]
Diese Aufgabe wird den Handlungsdimensionen A, B und C zugeordnet.
Zuerst muss man wieder das Ungleichungssystem und die Zielfunktion aufstellen. Dabei
sei
x ... Menge an Düngemittel D1 in kg
79
5.3 Anwendung in der Schule
y ... Menge an Düngemittel D2 in kg.
I) 6x+ 6y ≥ 54
II) 3x+ 6y ≥ 30
III) 10x+ 4y ≥ 48
IV) x ≥ 0
V) y ≥ 0
Die Zielfunktion wird für die Kosten formuliert: Z(x, y) = 3, 5x+ 3, 5y →Min.
Vorgehensweise bei GeoGebra:
Die Ungleichungen werden eingegeben und ebenso die Zielfunktion mit dem Wert 0. In
der Abbildung 5.14 ist der blau gefärbte Lösungsbereich und die Zielfunktion Z in rot
durch den Ursprung dargestellt. Durch Parallelverschieben der Zielfunktion in den zu-
lässigen Bereich erkennt man, dass die Zielfunktion parallel zur Geraden 6x + 6y = 54
verläuft. Daher ist es nicht möglich einen eindeutigen optimalen Punkt des zulässigen
Bereiches zu finden. Die Lösung ist daher mehrdeutig.
Alle Punkte der roten Strecke zwischen den Endpunkten (2|7) und (8|1) sind optimale
Lösungen.
Der Landwirt kann zum Beispiel 2 kg vom Düngemittel 1 und 7 kg vom Düngemittel
2 mischen. Oder er verwendet für die Mischung 5 kg vom Düngemittel 1 und 4 kg vom
Düngemittel 2. Es lassen sich einige ganzzahlige Lösungen einfach ablesen, aber natürlich
kann der Landwirt auch nicht ganzzahlige Mischungen herstellen.
Die Zielfunktion liefert für alle optimalen Punkte Kosten in Höhe von 31,5 Geldeinheiten
(GE).
80
5 Lineare Optimierung im Schulunterricht
Abbildung 5.14: Mehrdeutige Lösung beim Beispiel Düngemittel
Es ist auch möglich, dass ein Optimierungsproblem unlösbar ist. Dazu möchte ich eine
graphische Darstellung angeben. In der Abbildung 5.15 liegt ein unbeschränkter zulässi-
ger Bereich vor. Bei einer Maximierungsaufgabe kann die Zielfunktion nun beliebig große
Werte annehmen. Daher kann kein Punkt als optimaler Punkt ausgewählt werden.
Abbildung 5.15: Unlösbarkeit einer Maximumsaufgabe
5.3.5 Maturaaufgaben
In den Schulbüchern kommen hauptsächlich Aufgaben zur linearen Optimierung vor,
die den Handlungsdimensionen A und B zugeordnet werden. Teilweise ist auch die Di-
81
5.3 Anwendung in der Schule
mension C dabei. Da sowohl im Lehrplan als auch im Kompetenzkatalog für die Reife-
und Diplomprüfung alle Handlungsdimensionen vorgeschrieben sind, finde ich es wichtig
auch Aufgaben der Dimensionen C und D im Unterricht einzubauen.
Die Dimension C verlangt das Interpretieren und Dokumentieren. Dies kann teilwei-
se bei den Schulbuchaufgaben leicht hinzugefügt werden, indem man die Schüler und
Schülerinnen zum Beispiel vor Beginn der Rechnung die notwendigen Schritte für Opti-
mierungsaufgaben beschreiben lässt. Durch Zusatzfragen kann die Interpretation geübt
werden; die Interpretation des Ergebnisses ist ohnehin immer zu machen. Bei Aufgaben
mit mehrdeutigen Lösungen kann die Interpretation besonders gut geübt werden.
Aber es finden sich kaum Aufgaben zur Handlungsdimension D (Argumentieren und
Kommunizieren) in den Schulbüchern. Da aber über den Link https://aufgabenpool.
srdp.at/bhs/index.php?action=14&cmd=3 Übungsbeispiele zur Reife- und Diplom-
prüfung der BHS abgerufen werden können, kann man auf diese Beispiele zurückgreifen
(die Beispiele können dort nach dem Aufgabennamen gesucht werden).
Ich möchte hier Teilaufgaben zweier Beispiele angeben, die besonders die Handlungs-
kompetenzen C und D abprüfen. Beide Beispiele wurden bereits im Rahmen der Reife-
und Diplomprüfung gestellt; die gesamten Angaben inklusive Lösungsweg können über
den oben genannten Link mit dem entsprechenden Aufgabennamen abgerufen werden.
5.3.5.1 Fruchtsäfte
Ein Unternehmen erzeugt Fruchtsäfte (Apfel-, Birnen-, Trauben- und Orangensaft).
b) Das folgende Ungleichungssystem beschreibt die Produktionseinschränkungen für x
ME Apfelsaft und y ME Traubensaft:
x+ 10 · y ≤ 200
82
5 Lineare Optimierung im Schulunterricht
x+ 5 · y ≤ 125
x ≤ 100
x ≥ 0
y ≥ 0
- Zeichnen Sie den Lösungsbereich dieses Ungleichungssystems in der nachstehenden
Abbildung ein.
c) In der nachstehenden Abbildung ist der Lösungsbereich der Produktionseinschränkun-
gen für die tägliche Produktion von x ME Apfelsaft und y ME Orangensaft dargestellt.
Der Gewinn beim Verkauf jeder Flasche Apfelsaft beträgt e0,12. Der Gewinn beim Ver-
kauf jeder Flasche Orangensaft beträgt e0,20. Dabei gilt: 1 ME = 1000 Flaschen.
83
5.3 Anwendung in der Schule
- Stellen Sie eine Gleichung der Zielfunktion zur Beschreibung des Gewinns auf.
- Zeichnen Sie diejenige Gerade, für die der optimale Wert der Zielfunktion angenom-
men wird, in der obigen Abbildung ein.
- Ermitteln Sie den maximalen Gewinn pro Tag in e.
Aufgrund einer weiteren Produktionseinschränkung können pro Tag nur maximal 60 ME
Apfelsaft hergestellt werden.
- Begründen Sie, warum sich der maximale Gewinn pro Tag dadurch nicht verändert.
Ich möchte an dieser Stelle nicht auf den genauen Lösungsweg eingehen, da dieser mit
der Angabe abrufbar ist. Allerdings möchte ich ein paar Anmerkungen zu den Aufgaben
zu den Dimensionen C und D machen.
Bei der Teilaufgabe b) wird das richtige Markieren des Lösungsbereiches der Handlungs-
dimension C zugeordnet. Bei Verwendung von GeoGebra ist der Lösungsbereich leicht
zu erkennen, da dieser automatisch markiert wird. Die Schüler und Schülerinnen müs-
sen die Randgeraden und den Lösungsbereich noch richtig in die vorgegebene Graphik
übertragen.
Bei der Teilaufgabe c) wird der letzte Arbeitsauftrag (Begründung) der Handlungsdi-
mension D zugeordnet. In die vorgegebene Graphik kann die zusätzliche Einschränkung
leicht eingezeichnet werden. Man kann erkennen, dass sich zwar der zulässige Bereich
verkleinert, aber die Zielfunktion und der optimale Punkt nicht beeinflusst werden. Der
optimale Punkt und der Gewinn bleiben somit gleich.
84
5 Lineare Optimierung im Schulunterricht
5.3.5.2 Gürtelproduktion
Ein Unternehmen stellt unterschiedliche Ledergürtel her.
c) In der nachstehenden Abbildung ist der Lösungsbereich der Produktionseinschränkun-
gen für die Gürtelproduktion der Marken red und long dargestellt.
Die Zielfunktion Z beschreibt den Gewinn in Euro: Z(x, y) = 2 · x+ 3 · y
x ... Anzahl der Gürtel der Marke red
y ... Anzahl der Gürtel der Marke long
Dieser Gewinn soll maximiert werden.
- Zeichnen Sie diejenige Gerade, für die der optimale Wert der Zielfunktion angenom-
men wird, in der obigen Abbildung ein.
- Lesen Sie die optimalen Produktionsmengen näherungsweise ab.
- Ermitteln Sie den maximalen Gewinn.
85
5.3 Anwendung in der Schule
d) In der nachstehenden Abbildung ist der Lösungsbereich der Produktionseinschränkun-
gen für die Gürtelproduktion der Marken blue und deep dargestellt.
Jemand behauptet, dass der maximale Gewinn erreicht wird, wenn 60 Gürtel der Marke
blue und 120 Gürtel der Marke deep produziert und verkauft werden.
- Erklären Sie, warum man ohne Kenntnis der Zielfunktion beurteilen kann, dass diese
Behauptung falsch ist.
Der genaue Lösungsweg kann wieder mit der gesamten Angabe im Internet unter dem
obigen Link abgerufen werden.
Bei der Teilaufgabe c) wird das richtige Ablesen des optimalen Punktes der Handlungsdi-
mension C zugeordnet. Dabei kann GeoGebra nur bedingt zur Hilfe genommen werden.
Die Ungleichungen zur Beschreibung des zulässigen Bereiches sind nicht angegeben. Da-
her kann der Lösungsbereich in GeoGebra nicht dargestellt werden (außer man liest
die Gleichungen der Randgeraden ab und stellt die Abbildung nach). Die Zielfunkti-
86
5 Lineare Optimierung im Schulunterricht
on soll also händisch in die vorgegebene Abbildung gezeichnet und in den optimalen
Punkt verschoben werden. Da bei den Abbildungen meist nur die positiven Achsen des
Koordinatensystems dargestellt sind, wird das Einzeichnen der Zielfunktion durch den
Ursprung erschwert. Das sollte unbedingt im Unterricht geübt werden.
Die Teilaufgabe d) wird der Handlungsdimension D zugeordnet. Hier kann die Erklärung
mit dem Hauptsatz der linearen Optimierung erfolgen (der Punkt, der den angegebenen
Produktionsmengen entspricht ist kein Eckpunkt bzw. Randpunkt des zulässigen Berei-
ches).
Anhand dieser zwei ausgewählten Beispiele sieht man, dass nicht alle Teilaufgaben der
linearen Optimierung mit Hilfe von GeoGebra gelöst werden können. Teilweise müssen
Geraden händisch gezeichnet werden und im Fall von Argumentationen bzw. Interpre-
tationen ist es notwendig auch theoretisches Hintergrundwissen zu haben.
Es ist meiner Meinung nach also besonders wichtig, alle Arten von Beispielen im Schulun-
terricht zu üben. Sowohl die Übungen aus Schulbüchern, um die Handlungskompetenzen
A und B gut abzudecken, aber auch die Übungsbeispiele aus dem Aufgabenpool der Ma-
turaaufgaben, um speziell die Handlungsdimensionen C und D zu trainieren. Dabei soll
auch ein guter Mix aus Technologieeinsatz und händischem Rechnen / Konstruieren
eingesetzt werden. Auf keinen Fall sollen die Schüler und Schülerinnen den Eindruck
bekommen, dass mit GeoGebra alle Aufgaben gelöst werden können. Ein solides Hinter-
grundwissen ist unbedingt notwendig.
87
6 Schlusswort
Zum Abschluss der Arbeit möchte ich noch gerne einige persönliche Erfahrungen anbrin-
gen. Wie bereits erwähnt, konnte ich schon Unterrichtserfahrung an einer HLW sammeln.
Leider war es mir nicht möglich beim Thema der linearen Optimierung auf GeoGebra
zurückzugreifen, da die technische Ausstattung nicht gegeben war. Daher mussten alle
Beispiele händisch bzw. mit einem graphikfähigen Taschenrechner (TI-82stats) gelöst
werden. Die graphische Darstellung des Lösungsbereiches am Taschenrechner ist lei-
der nicht optimal. Das Graphikfenster ist sehr klein und eine Färbung der jeweiligen
Halbebenen würde zur Unkenntlichkeit führen. Daher muss auf eine Färbung verzichtet
werden. Ebenso ist es nicht möglich die Gerade der Zielfunktion zu verschieben. Also
muss man erst wieder händisch mit einem Geodreieck die Parallelverschiebung vorneh-
men, um den optimalen Punkt zu finden. Diese Vorgangsweise war sehr unbefriedigend
und ich hatte im Unterricht immer das Gefühl, dass dieses interessante Thema durch
die umständliche graphische Darstellung unbeliebt wurde.
Ich habe sehr schnell auf den Einsatz des Taschenrechners verzichtet. Aber auch die
graphische Darstellung durch händische Zeichnungen war teilweise schwierig. Die Kon-
struktion des zulässigen Bereiches dauerte eine „gefühlte Ewigkeit“. Oft konnte in einer
Unterrichtsstunde nur ein einziges Beispiel gelöst werden. Dies war ebenso unbefriedi-
gend.
Schlussendlich habe ich auf die Übungsbeispiele zur Reife- und Diplomprüfung zurückge-
griffen. Dadurch wurde der Unterricht wieder interessanter und kurzweiliger. Die Schüler
und Schülerinnen haben wieder deutlich mehr Interesse an der linearen Optimierung ge-
zeigt. Ich denke, dass dies am Aufbau der Maturaaufgaben liegt. Die Unterteilung in
Teilaufgaben wurde sehr gut aufgenommen. So konnten auch Schüler bzw. Schülerinnen,
denen zum Beispiel die Modellierung der Aufgabe sehr schwer fällt, bei den Teilaufgaben
zur Konstruktion des zulässigen Bereiches oder dem Auffinden des optimalen Punktes
ihr Wissen und Können unter Beweis stellen. Bei Aufgaben aus den Schulbüchern ist
diese Unterteilung leider nicht gegeben. Scheitert man an der Modellierung der Opti-
mierungsaufgabe, so kann das restliche Beispiel nicht mehr gelöst werden.
Ebenso habe ich die Erfahrung gemacht, dass die Schüler und Schülerinnen sehr stolz
auf sich selber waren, wenn sie Maturabeispiele lösen können. Ich denke, dass sich der
Einsatz dieser Übungsaufgaben im Unterricht lohnt (nicht nur bei der linearen Optimie-
rung) um den Schülern und Schülerinnen auch die Angst vor der Mathematikmatura zu
nehmen.
Für mich persönlich war durch diese Erfahrungen klar, dass es doch eine bessere Tech-
nologie geben muss, um mathematische Themen, bei denen graphische Darstellungen
eine große Rolle spielen, im Unterricht zu behandeln. Privat nutze ich GeoGebra schon
mehrere Jahre. Daher werde ich in Zukunft auf jeden Fall GeoGebra auch im Unterricht
verwenden und speziell bei der linearen Optimierung nicht darauf verzichten.
90
Literaturverzeichnis
[1] K. G. Murty. Linear Programming. John Wiley & Sons, 1983. ISBN 0-471-09725-X.
[2] L. Euler. Methodus inveniendi lineas curvas maximi minimive proprietate gauden-
tes, sive solutio problematis isoperimetrici latissimo sensu accepti, volume 24. 1744.
[3] R. Tichatschke. „Auf den Schultern von Giganten“ Zur Geschichte der ma-
thematischen Optimierung. https://www.uni-trier.de/fileadmin/fb4/INF/
TechReports/History-article.pdf, 2008. Online am 31.1.2018.
[4] K. Schick. Lineares Optimieren: Einführung in die mathematische Behandlung mo-
derner Probleme in den Wirtschaftswissenschaften, volume 3. Verlag Moritz Dies-
terweg, 1981. ISBN 3-425-05316-7.
[5] W. Hochstättler. Lineare Optimierung. Springer Spektrum, 2017. ISBN 978-3-662-
54425-9.
[6] J. Piehler. Einführung in die lineare Optimierung. BSB B. G. Teubner Verlagsge-
sellschaft, 1970.
[7] T. Ruen. https://commons.wikimedia.org/wiki/File:Gyroelongated_
square_pyramid.png, 2009. Online am 12.2.2018.
[8] T. Ladermann, T. Huke. Lineare Optimierung, was ist das? users.minet.
uni-jena.de/~bezi/Didaktik4/TLadermannTHukeLineareOptimierung.doc,
2006. Online am 20.2.2018.
Literaturverzeichnis
[9] H. W. Hamacher, S. Müller. Lineare Optimierung im Mathematikun-
terricht. http://optimierung.mathematik.uni-kl.de/mamaeusch/projekte/
wimstems/opt1.pdf. Online am 7.3.2018.
[10] https://www.abc.berufsbildendeschulen.at/download/2074/HLW.pdf. Online
am 14.3.2018.
[11] https://www.abc.berufsbildendeschulen.at/download/2121/
HLA-Land-und-Forstwirtschaft_-Anlage1_2016.pdf. Online am 14.3.2018.
[12] https://www.srdp.at/fileadmin/user_upload/downloads/Begleitmaterial/
08_AMT/srdp_am_clustereinteilung_2018_2017-01-27.pdf. Online am
14.3.2018.
[13] https://www.srdp.at/fileadmin/user_upload/downloads/Begleitmaterial/
08_AMT/Begriffekatalog_ab_2018/srdp_am_kompetenzen_begriffe_2018_
hlfs_hum_2017-10-16.pdf. Online am 14.3.2018.
[14] https://www.geogebra.org/about. Online am 15.3.2018.
[15] C. Allerstorfer, M. Langer, A. Siegl. Angewandte Mathematik @ HUM 2. Veritas
Verlag, 2016. ISBN 978-3-7101-0635-4.
[16] F. Pauer, M. Scheirer-Weindorfer, A. Simon. Mathematik anwenden HUM 2. Ös-
terreichischer Bundesverlag Schulbuch GmbH & Co KG, 2015. ISBN 978-3-209-
08088-2.
[17] B. Wessenberg, P.Hofbauer, H. Metzger-Schuhäker. Kompetenz: Mathematik, Band
2 HUM. Hölder-Pichler-Tempsky GmbH, 2015. ISBN 978-3-230-03871-5.
92
Eidesstattliche Erklärung
Ich erkläre hiermit an Eides statt durch meine eigenhändige Unterschrift, dass ich die vorliegende Arbeit selbständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel verwendet habe. Alle Stellen, die wörtlich oder inhaltlich den angegebenen Quellen entnommen wurden, sind als solche kenntlich gemacht.
Die vorliegende Arbeit wurde bisher in gleicher oder ähnlicher Form noch nicht als Magister-/Master-/Diplomarbeit/Dissertation eingereicht.
Datum Unterschrift