Technische Universität Kaiserslautern, Fachbereich Mathematik

SS 2004

Projektstudie zum Thema:

„Einsatz von Software zur Lösung linearer Optimie-

rungsprobleme im Mathematikunterricht“

Prof. Dr. H. W. Hamacher

geschrieben von

Evelyn Stephan

Evelyn.Stephan@web.de

8. Fachsemester

2

Inhaltsverzeichnis

1 Was ist lineare Optimierung? 3

1.1 Einführung 3

1.2 Lineare Optimierung in der Schule: WelcheVorschriften macht der Lehrplan? 5

2 Eine Unterrichtseinheit zur linearen Optimierung 6

2.1 Einstieg in die Unterrichtseinheit ohne Computereinsatz 6

2.2 Weiterführung mit dem Rechner und Vorstellung verschiedener Programme 7

2.2.1 Das Tabellenkalkulationsprogramm

EXCEL 11

2.2.2 Das Computeralgebrasystem MuPAD 20

2.2.3 Xpress – MP 29

2.2.4 Das Computeralgebrasystem DERIVE 33

2.2.5 Das Computeralgebrasystem MATHEMATICA 38

2.3 Schlussbetrachtung 44

3 Literaturverzeichnis 46

4 Versicherung über die selbstständige Anfertigung und die verwendeten Hilfsmittel 48

3

1. Kapitel

Was ist lineare Optimierung?

1.1 Einführung

Die lineare Optimierung ist ein noch recht junger Zweig der Mathematik, der sich erst im 20. Jahrhundert entwickelte und sich mit der Anwendung der Mathematik in der Wirtschaft beschäftigt. Dabei handelt es sich um Aufgaben, bei denen nach einem Extremwert (Mini-mum oder Maximum) einer Größe gesucht wird, welche von mehreren Variablen abhängt. Diese Variablen sind einschränkenden Nebenbedingungen unterworfen. „Optimal“ bedeutet also in diesem Zusammenhang soviel wie „extremal unter gewissen Bedingungen“. Die Ne-benbedingungen sind meistens durch Gleichungen oder Ungleichungen gegeben, können aber z.B. auch die Ganzzahligkeit der Lösung fordern. Es gibt heute eine Fülle von Beispielen, in denen die Methoden der linearen Optimierung ihre Anwendung finden: Im Transportwesen kann so berechnet werden, wie umfangreiche Trans-porte mit einem möglichst geringen Aufwand durchgeführt werden können, in der Ernäh-rungswissenschaft und in der Futtermittelindustrie bestimmt man mit diesen Methoden, wie preiswerte Rationen mit einem vorgegebenen Gehalt an Nährstoffen hergestellt werden kön-nen und in der Stahlherstellung ermittelt man so die optimale Ausnutzung der Walzstraßen, um nur einige Beispiele zu nennen.

Die lineare Optimierung entwickelte sich besonders in den letzten fünfzig Jahren sehr rasant. 1939 legte der russische Mathematiker Kantorowicz mit seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion“ die erste Arbeit über das Gebiet der mathematischen Optimierung vor. Der Amerikaner F. L. Hitchcock veröffentlichte eben-falls zu dieser Zeit eine Arbeit über ein Transportproblem. Beide Arbeiten wurden jedoch lange Zeit nicht beachtet. Erst nach dem zweiten Weltkrieg erkannten Mathematiker und Ö-konomen die Möglichkeiten, die hier versteckt waren. Alles ging daraufhin sehr schnell vor-an. 1947 entwickelte G. B. Dantzig den Simplexalgorithmus, von dem in der vorliegenden Arbeit auch immer wieder die Rede sein wird. Von dort an wurden immer neue und schnelle-re Methoden zur Lösung verschiedenster Probleme entwickelt.

Schließlich gelangte man auch zu der Einsicht, dass die lineare Optimierung in der Schule nicht fehlen sollte, was sich auf den Lehrplan und selbstverständlich auch auf die Lehrbücher niederschlug. In dem Buch von Behnke, Bertram und Sauer [16] heißt es noch im Jahr 1966 in Kapitel 5: „Es sollen vielmehr einige Grundzüge der neueren angewandten und numerischen Mathematik skizziert werden, die dem Gymnasialunterricht nahe liegen. Die Meinung ist dabei nicht, dass diese Dinge in den Unterricht einzubauen sind. Sie sollen nur Aufgabenmaterial für die eine oder andere Mathematikstunde liefern.“ Auf dieses Zitat folgt in dem Buch ein Kapitel zur linearen Optimierung. Heute findet sich dagegen ein Kapitel zu

4

diesem Themenbereich in den meisten Mathematiklehrbüchern, beispielsweise in [12]1 und [13].

Durch die Aufnahme dieses sehr anwendungsbezogenen Themengebiets in den Unter-richt soll den Schülern gezeigt werden, dass Mathematik nicht nur zum Selbstzweck betrieben wird, wie es in der Schule häufig den Anschein hat, sondern auch wirklich in der Praxis zur Lösung von Problemen herangezogen werden kann. Dadurch soll ein besonderer Motivations-schub von dieser Unterrichtsreihe ausgehen. Insbesondere der Einsatz von Rechnern, der die Entwicklung der linearen Optimierung in der vorliegenden Art erst möglich gemacht hat, soll dabei auch im Unterricht eine wichtige Rolle spielen und die Schüler für dieses Thema be-geistern.

In der vorliegenden Arbeit geht es in erster Linie um die Einsatzmöglichkeiten, die fünf ausgewählte Softwareprogramme in einer Unterrichtsreihe zur linearen Optimierung bieten. Um jedoch zunächst zu klären, welche Probleme die Programme überhaupt bewältigen kön-nen müssen, betrachte ich zuerst die Vorschriften, die der Lehrplan bezüglich dieses Themas macht. Danach werde ich mir überlegen, welche Inhalte in der Schule vermittelt werden soll-ten bzw. vermittelt werden können. Anhand dieser Überlegungen möchte ich schließlich in groben Zügen eine Unterrichtseinheit entwerfen, die diese Inhalte berücksichtigt und die Softwareprogramme mit ihren jeweiligen Eigenarten zu integrieren versucht. Der Vergleich der verschiedenen Programme erfolgt an einer Beispielaufgabe, die vor Behandlung der Pro-gramme vorgestellt wird.

1.2 Lineare Optimierung in der Schule: Welche Vorschriften macht der

Lehrplan?

Die wachsende Bedeutung der Linearen Optimierung spiegelt sich, wie bereits erwähnt,

in der Formulierung der Lehrpläne wieder, so heißt es im Lehrplan Mathematik für die Klas-sen 7- 9/10 von Hauptschule, Realschule und Gymnasium, Rheinland – Pfalz, auf Seite 6:

„...Neue mathematische Stoffgebiete, die durch veränderte gesellschaftliche oder wirt-schaftliche Bedingungen auch für die schulische Ausbildung relevant wurden und neue Methoden, die, durch die didaktische Forschung entwickelt, sich im Unterricht als er-folgreich erwiesen, werden ebenfalls berücksichtigt. Hierzu zählen z.B. die Statistik und in Realschule und Gymnasium das lineare Optimieren.“ In diesem Lehrplan werden fachspezifisch-allgemeine Lernziele des Mathematikunter-

richts aufgeführt, die durch das Lösen von linearen Optimierungsaufgaben meiner Meinung nach erfüllt werden und somit die Aufnahme der linearen Optimierung in den Lehrplan bei weitem rechtfertigen. Unter anderem sind dabei zu nennen: Die Förderung von Fähigkeiten wie Abstraktionsvermögen, problemlösendes Verhalten und mathematisches Modellieren, sowie die Einübung von fachlichen Kompetenzen wie dem Lö-sen von Gleichungen und Ungleichungen, die Anfertigung von Skizzen und Zeichnungen und nicht zuletzt dem Einsatz von Computern zur Lösung dieser Probleme. All diese Fähigkeiten werden beim Modellieren einer linearen Optimierungsaufgabe geschult, da zunächst die Problemstellung erkannt, wichtige von unwichtigen Informationen getrennt, ein mathematisches Modell formuliert und gelöst, sowie eine Interpretation der mathemati-schen Lösung vorgenommen werden muss.

1 Die Zahlen in eckigen Klammern beziehen sich auf die Literaturliste auf Seite 47.

5

Allerdings wird der linearen Optimierung dann doch nur ein eher geringer Platz im Lehrplan eingeräumt. In den Hauptschulen wird die Problematik gar nicht besprochen, in den Realschulen und Gymnasien soll sie in der neunten Klasse am Ende eines Blocks über „linea-re Gleichungen und Ungleichungen mit zwei Lösungsvariablen“ behandelt werden. Dabei sollen die Schüler am Ende der Unterrichtseinheit in der Lage sein, einfache Aufgaben zum linearen Optimieren lösen zu können. Konkret heißt es hier: [1] S.132

„Beim Lösen von Aufgaben zum linearen Optimieren steht der Prozess der Mathemati-sierung von Sachproblemen im Vordergrund und nicht das schematische Einüben von Lösungsverfahren. Es sollen deshalb auch den Schülern nur „einfache“ Aufgaben zur selbstständigen Bearbeitung vorgelegt werden. „Einfach“ bedeutet hier: Aus dem vorgegebenen Aufgabentext müssen unmittelbar zu entnehmen sein:

• Die Variablen x und y des Ungleichungssystems • Die Bedingungen für diese Variablen • Die zu optimierende Größe und deren Abhängigkeit von x und y

Es ist möglich, auf die Zielfunktion ganz zu verzichten und die optimale Lösung durch systematisches Probieren am Planungsvieleck zu ermitteln.“ Im Lehrplan für die Oberstufe [2] wird die lineare Optimierung nicht explizit erwähnt,

könnte aber wohl als Anwendungsgebiet in einer Unterrichtsreihe zur linearen Algebra be-handelt werden.

Besonders dem Ruf nach häufigerem Computereinsatz im Mathematikunterricht, der auch im Lehrplan immer wieder auftaucht, kann mit dieser Themenreihe nachgekommen werden, wie im Abschnitt 2.2 deutlich wird.

6

Kapitel 2

Eine Unterrichtseinheit zur Linearen Optimierung

Im folgenden Teil meiner Projektstudie möchte ich versuchen, in groben Zügen eine Unterrichtsreihe zum Thema lineare Optimierung zu umreißen, die insbesondere die Lösung von Optimierungsproblemen mithilfe verschiedener Softwareprogramme berücksichtigt, und damit wohl über den Rahmen des im Lehrplan vorgesehenen Unterrichtsbausteins zu diesem Thema hinausgeht. Zielgruppe ist hierbei eine Klasse ab der achten Jahrgangsstufe, durch entsprechende Erweiterungen wie z.B. die Einführung des Simplexalgorithmus, kann die Un-terrichtsreihe aber auch auf Leistungskursniveau gebracht werden.

Zunächst möchte ich in diesem Kapitel meiner Arbeit kurz ansprechen, wie das Thema in den ersten Stunden der Unterrichtsreihe anhand einer praktisch, ohne Computereinsatz zu lösenden Aufgabe eingeführt werden kann.

Im zweiten Teil, wenn die Schüler bereits über Grundkenntnisse der linearen Optimie-rung verfügen, soll der Computer zum Einsatz kommen, um die erworbenen Fähigkeiten aus-zubauen und zu vertiefen. Diesen Teil möchte ich ausführlicher besprechen. Dabei sollen fünf verschiedene Softwareprogramme vorgestellt werden, die an dieser Stelle Verwendung finden könnten. Ein Vergleich ihrer jeweiligen Fähigkeiten und Eigenarten erfolgt durch die Bearbei-tung einiger Beispielaufgaben.

Eine Behandlung des Themas der linearen Optimierung ausschließlich am Rechner halte ich für ungeeignet, da vermutlich, besonders beim Einstieg in das Thema, nicht nur ma-thematische Probleme, sondern auch technische Probleme bzw. Probleme der Schüler mit dem Programm das Verständnis behindern.

Ein einführender Kurs zu diesem Thema in der Schule könnte, meiner Meinung nach, die

folgenden Aspekte enthalten:

• Lösen von Maximums – und Minimumsaufgaben (graphisch und mit einem Soft-wareprogramm) mit beschränktem, unbeschränktem und leerem zulässigen Bereich bzw. eindeutiger und nicht eindeutiger Lösung

• Aufstellen des Linearen Programms bei einer Zielfunktion mit mehr als zwei Variab-len und lösen des Problems mit dem Rechner

• Eventuell Ausblick auf ganzzahlige oder nichtlineare Optimierung • Im Leistungskurs: Hauptsatz der linearen Optimierung, Simplexverfahren

Ich werde versuchen diese Bereiche hier abzudecken.

2.1 Einstieg in die Unterrichtseinheit ohne Computereinsatz

Zum Einstieg in diese Themenreihe bietet sich ein fächerübergreifender Ansatz an. Beispielsweise im Fach Sozialkunde kann bei der Behandlung des Themas „Wirtschaftsord-

7

nung und Wirtschaftspolitik“ auf die Probleme bei der möglichst kostengünstigen, aber ge-winnbringenden Produktion einer Ware eingegangen werden. Somit wäre der Grundstein für eine „sinnvolle“ Mathematikaufgabe gelegt. Es würde sich z.B. die in [11] S.166 gestellte Aufgabe 2: “Stellt die Tätigkeiten zusammen, die bei der Entwicklung, der Produktion und dem Vertrieb eines neuen Autos anfallen...“ mit entsprechenden Zusatzformulierungen für einen solchen Ansatz eignen. Die Schüler könnten zur Aufgabe gestellt bekommen, sich über die Kosten eines bestimmten Autos zu informieren und sich auch über die darin enthaltenen Herstellerkosten Gedanken zu machen. In welcher Größenordnung liegen sie? Was möchte der Produzent erreichen? Welche Bedingungen z.B. bezüglich des Personal muss er beachten? So kann schrittweise eine „aus dem Leben entnommene“ Optimierungsaufgabe erstellt wer-den. Dabei wird natürlich in diesem Fach noch nicht mathematisch formuliert, sondern nur allgemein die Nebenbedingungen in mündlicher Form ausgedrückt. Als Hausaufgabe für die nächste Mathematikstunde sollen sich die Schüler eine geeignete Lösung des Herstellerprob-lems überlegen. Somit erfahren sie deutlicher als in vielen anderen Mathematikstunden, dass der Stoff, den sie erlernen, auch wirklich praktisch anwendbar ist.

In der folgenden Mathematikstunde sollten die Lösungen der Schüler verglichen und die beste ausgesucht werden. Dann kann man zur mathematischen Lösung des Problems ü-bergehen. Es wird ein Arbeitsblatt mit einem sehr einfachen Maximierungs- oder Minimie-rungsproblem ausgeteilt, das graphisch gelöst werden soll und das die Schüler in Zweier- oder Dreiergruppen bearbeiten.

Dabei wird vorausgesetzt, dass die Schüler mit der graphischen Lösung eines Systems linearer Ungleichungen mit zwei Variablen vertraut sind oder zumindest die Themen „Lineare Funktionen und ihre Graphen“ und „Lineare Gleichungssysteme“ (Schnittpunktberechnung bei Geraden) behandelt wurden. Eine ausführliche und schrittweise Erklärung sowie eine Rei-he von Aufgaben finden sich beispielsweise in den Schulbüchern [12] S.47 und [13] S.44. Als Hausaufgabe kann eine analoge Aufgabe gestellt werden. Dieser Teil der Unterrichtsreihe sollte nicht mehr als zwei Mathematikstunden in Anspruch nehmen und an ihrem Ende müs-sen die Schüler in der Lage sein, mit den Begriffen Zielfunktion, Nebenbedingungen, Nicht-negativitätsbedingung, zulässiger Bereich, zulässige Lösung und Zielfunktionswert umzuge-hen. Nun ist ein Übergang zum computergestützten Unterricht möglich, da die Grundbegriffe geklärt wurden. Wurden bisher nur Minimierungsaufgaben bearbeitet, so sollten in den fol-genden Stunden Maximierungsaufgaben gestellt werden und umgekehrt.

2.2 Weiterführung mit dem Rechner und Vorstellung verschiedene Pro-

gramme

Nachdem den Schülern nun allgemein bekannt ist, mit welchen Problemen sich die li-neare Optimierung beschäftigt und Grundbegriffe geklärt wurden, können die erworbenen Fähigkeiten am Rechner vertieft und schwierigere Probleme in Angriff genommen werden. Es bieten sich hierzu verschiedene Softwareprogramme an, die teilweise sehr unterschiedliches leisten. Ich habe fünf Programme ausgewählt, die geeignet zu sein scheinen und jetzt vorge-stellt werden. Dabei handelt es sich um das Tabellenkalkulationsprogramm EXCEL, die Computeralgebrasysteme (CAS) DERIVE, MATHEMATICA und MuPAD und das speziell für die mathematische Optimierung entwickelte Programm Xpress MP.

Dabei werde ich die Programme zur Lösung der folgenden Aufgaben einsetzen, um einen Vergleich zwischen ihnen zu ermöglichen. (Aufgabe 1 und 2 aus [3] S. 4, S. 41 in ab-gewandelter Form übernommen, Aufgabe 3 aus [14] S.14)

8

Aufgaben 1. Aufgabe:

Eine Firma stellt zwei verschiedene Handytypen her. Bei der Produktion muss folgen-des beachtet werden: Die Abteilung, die die Gehäuse herstellt, kann in einer Woche höchstens 1000 Gehäuse des einen oder des anderen Typs herstellen. Die Montageabteilung kann aus logistischen Grün-den höchstens 800 Handys des zweiten Typs in der Woche zusammenbauen. Die Abteilung für elektrische Installation kann höchstens 800 Handys des ersten Typs oder 1200 Handys des zweiten Typs oder eine entsprechende Kombination in der Woche fertig stellen. Das Management der Firma möchte wissen, wie viele Handys des ersten bzw. des zweiten Typs hergestellt werden müssen, um den Gewinn pro Woche zu maximieren, wenn Handytyp eins 120 Euro und Handytyp zwei 90 Euro kosten soll. (Hinweis: Für ein Handy des Typs eins ist 1/800, für ein Handy des Typs zwei 1/1200 der wöchentlichen Arbeitszeit aufzuwenden)

a) Formuliere das lineare Programm und löse es graphisch. b) Löse das Problem mit dem (jeweiligen) Softwareprogramm. c) Ändere den Preis von Handytyp eins auf 135 Euro. Welche Lösung ergibt sich

jetzt? (kein Eckpunkt sondern Randstrecke) d) Verändere die Nebenbedingungen nach Wahl, lass zum Beispiel einige Nebenbe-

dingungen weg oder ändere die Zahlen. Was siehst du? (unbeschränkt, nicht ganz-zahlige Lösungen, leerer zulässiger Bereich)

2. Aufgabe:

Die Firma möchte ihr Angebot erweitern und produziert künftig auch zwei weitere Handytypen. Die Abteilung für die Gehäuseabteilung steigert ihre Produktion auf 1800. Der dritte Handytyp soll 150 Euro kosten und kann höchstens 400 mal pro Woche in der Monta-geabteilung zusammengebaut werden. Der vierte Handytyp kostet nur 70 Euro, kann dafür aber 900 mal zusammengebaut werden. Die Installationsabteilung kann höchstens 400 Han-dys des dritten Typs oder 1200 Handys des vierten Typs fertig stellen. Sonstige Bedingungen gelten wie in Aufgabe 1.

a) Formuliere das dazugehörige lineare Programm, kann es graphisch gelöst werden? b) Löse die Aufgabe mit einem Softwareprogramm. Ist die Lösung realistisch? (Wie

könnte eine ganzzahlige Lösung aussehen?) Bemerkung:

Die Worte in Klammern sollten auf einem Aufgabenblatt für Schüler nicht enthalten sein. Sie dienen lediglich der Orientierung, was mit dem jeweiligen Aufgabenteil bezweckt werden soll.

9

Die zugehörigen linearen Programme sehen folgendermaßen aus: Aufgabe 1:

yx 90120max +

0,

240023

800

1000.u.d.N

≥

≤+

≤

≤+

yx

yx

y

yx

(1)

Aufgabe 2:

wzyx 7015090120max +++

0,,,

24002623

900

400

800

1800.u.d.N

≥

≤+++

≤

≤

≤

≤+++

wzyx

wzyx

w

z

y

wzyx

(2)

Bemerkung:

Wie bereits oben erwähnt, halte ich es für möglich, in einem Mathematikleistungskurs

den Hauptsatz der linearen Optimierung sowie das Simplexverfahren einzuführen. Dabei würde ich mit der Einführung des Themenbereichs der linearen Optimierung genauso begin-nen wie oben beschrieben, nur können die Aufgaben etwas schneller abgehandelt werden. Dann stellt sich die Frage nach der prinzipiellen Form des Zulässigkeitsbereichs. An dieser Stelle kann der Begriff der konvexen Menge mit den Schülern erarbeitet werden. Durch die Frage nach den Stellen an denen optimale Punkte überhaupt liegen können, gelangt man schließlich zum Hauptsatz der linearen Optimierung (Formulierung nach [14]): Eine n-stellige reelle lineare Funktion, die auf einem durch reelle lineare Ungleichungen mit n Variablen beschriebenen konvexen Bereich (Zulässigkeitsbereich) definiert ist, nimmt ihr Maximum bzw. ihr Minimum – sofern ein solches existiert – stets am Rand dieses Bereiches an.

Nun ist es möglich, die Arbeitsweise des Simplexalgorithmus anschaulich als „Ab-wandern von Ecken mit Richtungshinweisen“ zu erklären. Eine stark vereinfachte, aber sehr leicht verständliche Erklärung findet sich auch in [5], S.61. Eine mathematische Begründung des Simplexverfahrens würde zu weit führen, ist aber für Interessierte in [15] ausführlich dar-gestellt. Die Schritte des Algorithmus sollten lediglich an Beispielen vorgestellt werden, um dann von den Schülern nachvollzogen werden zu können. So lernen sie eine Möglichkeit ken-nen, mit der Probleme mit mehr als zwei Variablen bearbeitet werden bzw. mit der die Soft-wareprogramme diese Aufgaben lösen. Ich werde auch untersuchen, inwieweit sich die später vorgestellten Programme in dieser Unterrichtseinheit einsetzen lassen.

10

Zum Ende der Unterrichtsreihe ist es möglich einen Ausblick auf nichtlineare Opti-mierungsprobleme zu geben. Dafür eignet sich beispielsweise folgende Aufgabe:

Es ist also

yx ⋅max

0,

32...

≥

=+

yx

yxNdu (3)

zu lösen.

Nun komme ich zur Bearbeitung dieser Aufgaben mit den erwähnten Programmen.

3. Aufgabe:

Viktoria will für ihr Zwergkaninchen ein rechteckiges Gehege direkt an der Haus-wand einrichten. Sie hat dafür 3 Meter passenden Drahtzaun auf einer Rolle. Wie soll sie die Seitenlängen wählen, damit der Flächeninhalt maximal wird?

11

2.2.1 Das Tabellenkalkulationsprogramm EXCEL

Das Tabellenkalkulationsprogramm Excel ist eine Standardsoftware, die auf jedem Rechner vorhanden ist. Mit Excel können Tabellen erstellt werden, in deren Zellen sowohl Texte als auch Größen sowie Zahlen eingegeben werden können. Das Besondere einer Tabel-lenkalkulation ist aber, dass in die einzelnen Zellen einer Tabelle auch Rechenvorschriften eingeschrieben werden können, nach denen die in anderen Zellen eingegebenen Zahlen mit-einander verknüpft werden. Auf diese Weise lassen sich schnell Tabellen unter Annahme un-terschiedlicher Bedingungen berechnen. Die erstellten Tabellen lassen sich als Diagramme darstellen [17].

In diesem Programm ist ein Tool „SOLVER“ enthalten, das zur Lösung von linearen und nichtlinearen Extremwertproblemen dienen kann. In dieser Unterrichtsreihe zur linearen Optimierung kann dadurch der Simplexalgorithmus als sogenannte Black Box eingesetzt wer-den. EXCEL ermöglicht außerdem auch eine grafische Lösung von Problemen mit zwei Vari-ablen. Meine Darstellung orientiert sich hier an [6].

Zusätzlich besteht die Möglichkeit mit dem Tool „SIMPLEX“ Pivotoperationen an Simplextableaus vorzunehmen. Ich bearbeite nun die oben gestellten Aufgaben, um die eben erwähnten Möglichkeiten dieses Programms vorzustellen. Lösung zu Aufgabe 1:

zu Aufgabe 1. b) Löse das Problem mit dem (jeweiligen) Softwareprogramm. Graphische Lösung:

Zunächst erfolgt die Bestimmung der „Spurgeraden“ (Begrenzungsgeraden der Halb-ebenen) aus (1), die dann aufgrund der Nichtnegativitätsbedingungen im ersten Quadranten gezeichnet werden.

xy

y

xy

5,11200

800

1000

3

2

1

−=

=

−=

Die Schnittmenge der drei Halbebenen bestimmen den zulässigen Bereich. Für die

Zielfunktion gilt:

steht)GewinnerzieltendenfürGwobei(,3

4

90x

Gy z −=

Durch paralleles Verschieben der Zielgeraden über dem zulässigen Bereich ergibt sich

dann der gesuchte maximale Wert an dessen Rand (bzw. einem Eckpunkt). Diese Vorge-hensweise ist natürlich allen Programmen gemeinsam.

Zur Realisierung dieses Vorgehens mit Excel erstellt man zunächst eine Wertetabelle für die Spurgeraden. Diese ist in Abb.2.1 zu sehen, in der ersten Spalte befinden sich die Wer-te für die Variable x. Die drei folgenden Spalten enthalten die Werte für die jeweilige Spurge-rade. Der zulässige Bereich ergibt sich bei diesem Maximierungsproblem dann als Minimum der jeweiligen Werte, dargestellt in der fünften Spalte. (Die in Abb.2.1 in jeder Zelle enthalte-nen Anführungsstriche bewirken lediglich eine Ausgabe der Formel statt des berechneten

12

Werts, sie müssen bei einer Anwendung ausgelassen werden.) Weiterhin benötigt man die sechste Spalte für den Wert der Zielfunktion in jeder Zeile.

Abbildung 2.1: Formeln zur Berechnung des zulässigen Bereichs und der Zielfunktion

Um die Zielfunktion im späteren Diagramm bewegen zu können, verknüpft man zu-

nächst die Spalte mit der Zielfunktion mit der Zelle für G (über die Eingabe von $F$1 in den Zellen F3 – F5). Zuletzt muss die Zelle für G noch mit einer Bildlaufleiste verknüpft werden, wie im Folgenden beschrieben wird. Später ist es dann möglich durch Ziehen an der Bildlauf-leiste die Zielfunktion im Diagramm zu verschieben. Die Bildlaufleiste befindet sich im Menü „Ansicht > Symbolleisten > Formular“.

Abbildung 2.2: Bildlaufleiste

Sie kann mit der Maus aufgezogen und entsprechend positioniert werden (wie z.B. in

Zelle $G$1 in Abb.2.1). Die Zellverknüpfung muss noch hergestellt werden: Das Kontextme-nü öffnet sich durch einen Klick mit der rechten Maustaste und durch „Steuerelemente forma-tieren“ erhält man eine Dialogbox, in der die Ausgabeverknüpfung zur entsprechenden Zelle in unserer Tabelle hergestellt werden muss:

Abbildung 2.3: Zellverknüpfung herstellen

13

Der Maximalwert einer Bildlaufleiste beträgt lediglich 30 000, der Gewinn G sollte

aber in Bereichen bis 200 000 veränderbar sein, daher wird der Wert der Bildlaufleiste durch eine Multiplikation mit 2000 in der Zelle $F$1 heraufgesetzt (siehe Abb.2.1).

Nun ist es möglich ein Diagramm mit Zielfunktion und zulässigem Bereich zu erstel-len. Hierzu verfolgt man den Pfad „Einfügen > Diagramme > Punkt (XY)“ und wählt den Untertyp „Punkte mit Linien ohne Datenpunkte“ aus. Durch entsprechendes Markieren der ersten Spalte und der Spalte für den zulässigen Bereich bzw. die Zielfunktion entsteht so das folgende Diagramm:

Eindeutige Lösung

0

200

400

600

800

1000

1200

0 200 400 600 800 1000

zulässiger Bereich

Zielfunktion

Abbildung 2.4 : Zulässiger Bereich und Zielfunktion

Im Eckpunkt (400/600) erreicht G den Maximalwert 102 000. Also müssen 400 Han-

dys des Typs eins und 600 Handys des Typs zwei produziert werden, um den maximalen Ge-winn von 102 000 Euro zu erzielen. In diesem Fall sieht die zugehörige Wertetabelle folgen-dermaßen aus:

Abbildung 2.5: Wertetabelle im Zielbereich

14

Wie man aus dieser Tabelle und dem Diagramm erkennt, schneiden sich in diesem

Punkt die Spurgeraden y1 und y2. Lösung mit dem SOLVER:

Excel verfügt über ein leistungsstarkes Werkzeug zur Lösung von linearen Optimie-

rungsaufgaben, den SOLVER. Dieses Tool findet sich im Menü EXTRAS. Sollte der SOL-VER dort nicht aufgeführt sein, muss er über „EXTRAS > ADD-IN-Manager > SOLVER“ aktiviert werden. Der SOLVER verwendet zur Lösung von linearen und ganzzahligen Prob-lemen die Simplexmethode und die „Branch and Bound“ – Methode, weitere Informationen zu den verwendeten Algorithmen finden sich in der Hilfe zum SOLVER.

Man gibt zunächst das Optimierungsproblem etwa folgendermaßen ein:

Abbildung 2.6: Eingabe der Aufgabe

In dieser Abbildung 2.6 enthalten die Zellen B3 und C3 die zu verändernden Variab-len. Diese werden dann mit der Zelle H2, die die Formel für die Zielfunktion beinhaltet, ver-knüpft. Weiterhin verknüpft man sie mit den Zellen F5–F7, in denen, zusammen mit E5-E7, die Nebenbedingungen stehen.

Dann wird der SOLVER mit folgenden Angaben für Zielzelle (Zielfunktion), Zielwert (Max/Min), veränderbare Zellen (Variablen) und Nebenbedingungen gefüllt:

Abbildung 2.7: EXCEL - SOLVER

15

Dabei ist noch zu beachten, dass unter Optionen die Nichtnegativität der Variablen ausgewählt wird. Somit erhält man die erwartete Lösung x = 400, y = 600, maximaler Gewinn 102 000 Euro:

Abbildung 2.8: optimale Lösung

zu Aufgabe 1. c) Ändere den Preis von Handytyp eins auf 135 Euro. Welche Lösung ergibt sich jetzt? Als neue Zielfunktion erhält man somit:

,2

3

90x

Gy z −=

Durch entsprechendes Abändern der Funktion in der Tabelle ergibt sich folgendes Diagramm:

nicht eindeutige Lösung

0

200

400

600

800

1000

1200

1400

0 200 400 600 800 1000

zulässiger Bereich

Zielfunktion

Abbildung 2.9 : Lösung ist Randstrecke

Wie man sieht, ist die Lösung hier zum ersten Mal nicht eindeutig bestimmt (also kein

Eckpunkt), sondern es ergibt sich eine Strecke. Ziel ist es hiermit den Schülern zu veran-schaulichen, dass alle Punkte dieser Strecke optimale Lösungen sind und nicht immer nur eine optimale Lösung existieren muss.

Der SOLVER liefert, wie erwartet, die bereits oben gefundene Lösung x = 400, y = 600 in Abb.2.10. Nur der maximale Gewinn hat einen anderen Betrag, da ja die Zielfunktion verändert wurde. Er beträgt jetzt 108 000 Euro.

16

Abbildung 2.10: Lösung mit dem SOLVER zu Aufgabe 1. d) Verändere die Nebenbedingungen nach Wahl, lass zum Beispiel einige Ne-benbedingungen weg oder ändere die Zahlen. Was siehst du? (unbeschränkt, nicht ganzzahli-ge Lösungen)

Lässt man beispielsweise die erste und die dritte Nebenbedingung im LP (1) weg, so ergibt sich ein zulässiger Bereich, der unbeschränkt ist. Oder durch Hinzufügen der Bedin-gung y >= 1000 wird das lineare Problem unlösbar. Außerdem werden bei Änderung der Ne-benbedingungen mit Sicherheit nicht-ganzzahlige Lösungen auftreten. So werden die Schüler spielerisch an häufig auftretende Probleme und Spezialfälle herangeführt und erhalten einen kleinen Ausblick auf andere Gebiete der Optimierung. Diese Veränderungen lassen sich mit dem SOLVER sehr einfach und schnell durch Abände-rung der Zahlenwerte oder durch die Befehle „Hinzufügen/Ändern/Löschen“ im Feld für die Nebenbedingungen durchführen. Änderungen in der graphischen Lösung erfordern dagegen mehr Geschick im Umgang mit Excel und sind daher wohl eher nicht für die Schülerhand geeignet. Lösung zu Aufgabe 2:

Diese Aufgabe enthält vier Variablen und ist daher natürlich nur noch mit dem SOLVER lös-bar:

Abbildung 2.11: Lösung zu Aufgabe 2

Diese Lösung x = 266,67, y = 800, z = 0, w = 0 und optimalem Gewinn von 104 000 Euro ist in der Praxis unbrauchbar, da eine Anzahl von x = 266,67 Handys in der Praxis nicht hergestellt werden kann. Falls die Schüler nicht selbst Einwände gegen diese Lösung erheben, sollte darauf hingewiesen werden. Dieses Problem kann behoben werden, indem man zusätz-liche Nebenbedingungen im SOLVER hinzufügt. Dazu wählt man „Extras > SOLVER > Ne-

17

benbedingung Hinzufügen“, dann sollte in die Zielzelle die jeweilige Zelle für eine Variable eingegeben und der Operator „ganzzahlig“ ausgewählt werden.

Abbildung 2.12:Ganzzahlige Lösung von Aufgabe 2

Somit ergibt sich die in Abb. 2.12 gezeigte Lösung x = 266, y = 800, z = 0, w = 1, mit

der ein Gewinn von 103 990 Euro erzielt wird. Lösung zu Aufgabe 3:

Auch nichtlineare Probleme lassen sich mit dem SOLVER lösen:

Abbildung 2.13: Lösung zu Aufgabe 3

Es ergibt sich x = 0,75 m und y = 1,5 m. Dann hat der Käfig die maximale Fläche von

1,125 m². Einsatz von Excel im Leistungskurs zur Einführung des Simplexalgorithmus

Zusätzlich bietet Excel mit dem Tool „SIMPLEX“ die Möglichkeit, nach Eingabe ei-

nes Simplextableaus und dem Aussuchen einer Pivotspalte, Pivotoperationen durchführen zu lassen. Dabei muss das Simplextableau in folgender Form in die Zellen eingegeben werden:

AAB

1− bAB

1−

AAcc BB

1−− bAc BB

1−−

Hier ein Beispiel:

18

Abbildung 2.14: Eingabe des Simplextableaus

Zuerst müssen alle Zellen markiert werden, um dann mit „Simplex -> SetTableau“ (siehe Abbildung 2.14) das Simplextableau festlegen zu können. Dann wird mithilfe von „Se-lectPivotCol“ die Spalte ausgewählt, in der ein Pivotelement gesucht werden soll:

Abbildung 2.15: Aussuchen der Pivotspalte

In Abbildung 2.15 wurde die erste Spalte ausgesucht. Nach Markieren der Spalte er-scheint am Ende des Tableaus eine zusätzliche Spalte, die die Wahl des Pivotelements be-stimmt. Nach dem Simplexalgorithmus muss dasjenige Element der Pivotspalte ausgesucht werden, für das tr,n+1/trj (hier in der Spalte H enthalten) minimal wird. Hier entspricht diese Regel dem Element in B3. Nach Markieren von B3 und Auswahl von „Simplex -> Pivot“ ergibt sich folgendes Tableau:

Abbildung 2.16: Durchführung der Pivotoperation

Dieser Vorgang wird wiederholt und man erhält das optimale Tableau:

19

Abbildung 2.17: optimales Simplextableau

Nach der Besprechung des Simplexalgorithmus (lediglich der Reihenfolge der Schrit-

te) und Vorführung eines Beispiels, das die Funktionsweise dieses „Simplex“ – Tools ver-deutlicht, sollten die Schüler in der Lage sein selbst einige Aufgaben mit dem Simplexalgo-rithmus zu lösen bzw. durch Herumprobieren eigene Erfahrungen zu machen. Ich denke, dass sich die einzelnen Schritte des Algorithmus so leichter im Gedächtnis der Schüler verankern und nicht einfache, aber langwierige Rechnungen den Blick auf das Wesentliche versperren.

Excel bietet also viele Möglichkeiten des sinnvollen Einsatzes beim Thema „Lineare Optimierung“ im Mathematikunterricht. Ein besonderer Vorteil dieses Programms ist, dass es an jeder Schule vorhanden sein müsste, was bei den folgenden Programmen nicht unbedingt der Fall sein muss. Nachteilig wirkt sich aus, dass die graphische Lösung nicht ganz einfach realisierbar ist. Bereits kleine Tippfehler führen zu großen Problemen und lassen sich schwer beseitigen. Die Veränderungen der Nebenbedingungen gestalten sich schwierig und sind nur mit viel Verständnis für das Programm durchführbar. Müssen die Schüler selbst die Tabellen zur Zeichnung aufstellen, wird das viel Zeit in Anspruch nehmen. Allerdings eignet sich ein fertiges Diagramm für eine Demonstration des Verschiebens der Zielgeraden über den zuläs-sigen Bereich sehr gut.

Man muss aber auch beachten, dass dieses Verfahren zur Zeichnung des zulässigen Bereichs in dieser Form nur anwendbar ist, wenn die untere Begrenzung des zulässigen Be-reichs durch die positive x – Achse erfolgt. Ist das nicht der Fall, muss man sich ein anderes Verfahren zur Darstellung des zulässigen Bereichs überlegen. Dies dürfte zwar nicht allzu schwierig sein, jedoch muss daher schon vorher bekannt sein, wie der zulässige Bereich aus-sieht. Dieses Problem tritt beim CAS MuPAD, das im nächsten Teil vorgestellt wird, nicht auf.

Die beiden Tools SOLVER und SIMPLEX sind dagegen relativ schnell zu verstehen und auch recht einfach zu bedienen. Beim Gebrauch des SOLVER lassen sich Veränderungen der Nebenbedingungen und der Zielfunktion schnell durchführen und der „SIMPLEX“ er-möglicht es, die Schritte des Simplexalgorithmus zu verfolgen. Sie eignen sich daher recht gut für den Unterricht.

20

2.2.2 Das Computeralgebrasystem MuPAD

MuPAD pro ist ein Computeralgebrasystem, das durch eine Kombination aus interak-tiven Arbeitsblättern, einer umfangreichen mathematischen Bibliothek und vielen Grafikmög-lichkeiten vielseitig in den mathematischen Unterricht integriert werden kann. Es ermöglicht Modelle in einer Mathematik – nahen Syntax zu definieren, zu kommentieren und zur Unter-stützung des Modellbildungsprozesses auch zu visualisieren. Die Funktionen der linearen Op-timierung basieren hierbei auf dem 2-Phasen Simplexalgorithmus. Zum Auffinden ganzzahli-ger Lösungen wird der Algorithmus von Land – Doig benutzt. MuPAD pro ist keine reine Schulsoftware, sondern ist auch im Studium und Beruf einsetzbar. Das Programm wurde von SciFace Software und der MuPAD Forschungsgruppe der Universität Paderborn, NRW, ent-wickelt [7].

Die in MuPAD enthaltene Bibliothek für lineare Optimierung liefert einige wichtige Be-fehle, die hier kurz vorgestellt werden sollen. Ich halte es für sinnvoll in einer Unterrichtsein-heit, in der dieses Programm eingesetzt werden soll, die folgende Liste in ausgedruckter Form den Schülern zur Verfügung zu stellen: • linopt::corners([constr,obj],vars)

Berechnet alle zulässigen Ecken des durch die Restriktionen constr und die Zielfunktion obj gegebenen linearen Optimierungsproblems mit den Variablen vars. Zusätzlich wird die optimale Lösung mit dem zugehörigen Zielfunktionswert zurückgegeben. linopt::corners([constr,obj], vars, All) Berechnet alle Ecken des linearen Optimierungsproblems (auch unzulässige). Beinhaltet die Definition des linearen Programms zusätzlich die Option „NonNegative“, so dürfen alle Variablen nur nicht-negative Werte annehmen.

• linopt::maximize([constr, obj])

Berechnet die Lösung der linearen oder gemischtganzzahligen Optimierungsaufgabe, die durch die Restriktionen constr und die Zielfunktion obj beschrieben wird und maxi-miert werden soll. Die Option All würde zusätzlich bewirken, dass alle Variablen nur ganzzahlige Werte annehmen. Eine Option DualPrices ermöglicht eine Ausgabe der Schattenpreise, was aber in der Schule weniger interessant sein dürfte. Dieser Befehl kann die Zustände OPTIMAL (optimale Lösung gefunden), EMPTY (es existiert keine Lösung) oder UNBOUNDED (unbeschränkter Zulässigkeitsbereich) zurückgeben. Der folgende Be-fehl arbeitet analog für ein Minimierungsproblem:

linopt::minimize([constr, obj])

• linopt::plot_data([constr, obj], vars)

Liefert eine grafische Darstellung des zulässigen Bereiches des linearen Optimierungs-problems und einer Geraden, die orthogonal zum Zielfunktionsvektor ist und durch die Ecke mit dem optimalen gefundenen Zielfunktionswert geht. (Um diesen Befehl benutzen

21

zu können, müssen zuvor durch den linopt::corners Befehl die Ecken ausgerechnet worden sein.)

Diese Befehle müssten zur Behandlung der linearen Optimierung in der Mittelstufe bereits ausreichen. In der Oberstufe, bei der Einführung des Simplexalgorithmus, bieten sich noch folgende Kommandos an: • linopt::Transparent([constr,obj])

Dieser Befehl berechnet das kanonische Simplex – Tableau des linearen Optimierungs-problems, das durch die Restriktionen constr und die Zielfunktion obj beschrieben wird. (Achtung: Alle Prozeduren der linopt Bibliothek, die das von li-

nopt::Transparent gelieferte Tableau benutzen, dienen der Minimierung des gegebe-nen Problems! Es kann also notwendig sein, die Zielfunktion zuerst mit –1 zu multiplizie-ren.) Im zurückgegebenen Simplex – Tableau des Domaintyps linopt::Transparent wird eine eigene Notation benutzt. „linopt“ steht hier für das Tableau, „obj“ beschreibt die lineare Zielfunktion, „restr“ steht für die Beschränkungen, slk [1], slk[2], ... sind die Schlupfvariablen und die Namen der anderen Variablen stehen jeweils für sich selbst. Eine Variable, die als Zeilenbeschriftung auftaucht, zeigt an, dass diese Variable Basisvariable ist.

• linopt::Transparent::autostep(tableau)

Führt den nächsten Simplexschritt für das gegebene Simplextableau tableau aus. Es wird entweder ein Simplextableau des Domaintyps linopt::Transparent oder eine Menge, die eine Lösung des linearen Optimierungsproblems enthält, zurückgegeben.

• linopt::Transparent::result(tableau)

Bestimmt die zum gegebenen Simplex – Tableau zugehörige Ecke und gibt die Werte der benutzerdefinierten Variablen zurück.

• linopt::Transparent::simplex(tableau)

Beendet die aktuelle Phase des 2 – Phasen Simplexalgorithmus, auf dem gegebenen Sim-plex – Tableau tableau (springt also direkt zum optimalen Tableau).

• linopt::Transparent::suggest(tableau)

Schlägt den nächsten Simplexschritt des Simplexalgorithmus für das gegebene Simplex – Tableau tableau vor. Zurückgegeben werden die beiden Variablen, die ausgetauscht werden sollen, oder OPTIMAL.

• linopt::Transparent::userstep(tableau,basvar,nonbasvar)

Führt einen benutzerdefinierten Simplexschritt im Tableau tableau um das durch bas-var und nonbasvar spezifizierte Pivotelement aus.

22

Die Bibliothek enthält auch Befehle mit denen beispielsweise eine explizite erste Phase des 2 – phasigen Simplexalgorithmus erzwungen, die Schlupfvariablen der ersten Phase aus der Basis entfernt oder die dualen Lösungen zu einem gegebenen Tableau bestimmt werden können. Dies führt allerdings weit über den zu behandelnden Schulstoff hinaus. Zur genaue-ren Beschreibung der Befehle siehe im Programm MuPAD „Hilfe -> Hilfe-Assistent -> Inhalt -> Lineare Optimierung“. Das Eingabefenster von MuPAD gestaltet sich folgendermaßen:

Abbildung 2.18: MuPAD Oberfläche

Nun möchte ich die beschriebenen Befehle auf die oben genannten Aufgaben anwenden:

Lösung zu Aufgabe 1

zu Aufgabe 1. b) Lösung mit Computeralgebrasystem MuPAD: Eingabe des linearen Progamms:

• LP := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y ], 120*x +

90*y, NonNegative]:

Lösung des Problems:

• linopt::maximize(LP)

☯OPTIMAL, �x = 400, y = 600�, 102000�

Berechnung der Ecken: • linopt::corners(LP,[x,y])

☯�☯0, 0�, ☯0, 800�, ☯800, 0�, ☯200, 800�, ☯400, 600��, 102000, ☯400, 600��

Die letzte aufgeführte Ecke ist optimal mit dem Zielfunktionswert 102 000.

Zeichnung des zulässigen Bereichs (rote Fläche) und der Zielfunktion (gestrichelt): • G:=linopt::plot_data(LP,[x,y]):plot(G):

23

Maximize 120*x + 90*y

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

x-axis

y-axis

zu Aufgabe 1. c) Änderung des Preises auf 135 Euro:

• LP2 := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y ], 135*x +

90*y, NonNegative]:

Lösung: • linopt::maximize(LP2)

☯OPTIMAL, �x = 800, y = 0�, 108000�

• linopt::corners(LP2,[x,y])

Error: Problem in Variables and List of these Variables expected

[linopt::corne\

rs]

Scheinbar liegen hier Probleme bei der Ausgabe der Ecken vor, da die Zielfunktion mit einer der Begrenzungsgeraden übereinstimmt, die Zeichnung liefert jedoch richtig:

• H:=linopt::plot_data(LP2,[x,y]):plot(H):

24

Maximize 135*x + 90*y

100 200 300 400 500 600 700 800

100

200

300

400

500

600

700

800

x-axis

y-axis

zu Aufgabe 1. d) Änderung der Nebenbedingungen, z.B. Weglassen von Nebenbedingungen, Problem wird unbe-schränkt

• LP3 := [[ y <= 800], 120*x + 90*y, NonNegative]:

• linopt::maximize(LP3)

☯UNBOUNDED, �x = PHI1, y = 0�, 120 ⋅ PHI1�

• G3:=linopt::plot_data(LP3,[x,y]):plot(G3):

Maximize 120*x + 90*y

-80 -60 -40 -20 20 40 60 80 100

100

200

300

400

500

600

700

800

x-axis

y-axis

oder: Hinzufügen einer Bedingung, Problem wird unlösbar, da zulässiger Bereich leer • LP4 := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y , y + x

>= 1500], 120*x + 90*y, NonNegative]:

• linopt::maximize(LP4)

25

☯EMPTY, ∅, − ∞�

• G4:=linopt::plot_data(LP4,[x,y]):plot(G4):

Warning: Uninitialized variable 'bestcorner' used;

during evaluation of 'linopt::corners'

" No feasible corners found! Feasible Area is

empty! "

-1.0 -0.8 -0.6 -0.4 -0.2 0.2 0.4 0.6 0.8 1.0

-1.0

-0.8

-0.6

-0.4

-0.2

0.2

0.4

0.6

0.8

1.0

x

y

• delete LP,LP2,LP3,LP4,G,H,G3,G4

Lösung zu Aufgabe 2

Formulierung des LP und Ausgabe der Lösung:

• LP:=[[x+y+z+w<=1800,y<=800,z<=400,w<=900,3*x+2*y+6*z+2*w<=2400],

120*x+90*y+150*z+70*w, NonNegative]:

• linopt::maximize(LP)

�

OPTIMAL,

�

w = 0, y = 800, z = 0, x =800

3���

�

, 104000

Diese Lösung ist nicht ganzzahlig, also muss bei der Formulierung des LP die Option "All" ge-wählt werden, es ergibt sich:

• LP:=[[x+y+z+w<=1800,y<=800,z<=400,w<=900,3*x+2*y+6*z+2*w<=2400],

120*x+90*y+150*z+70*w, NonNegative, All]:

• linopt::maximize(LP)

26

☯OPTIMAL, �w = 1, x = 266, y = 800, z = 0�, 103990�

Zum Schluss soll noch gezeigt werden, wie das Programm bei der Einführung des Simplexal-gorithmus eingesetzt werden kann. Dazu lösen wir Aufgabe 1 noch einmal in einzelnen Sim-plexschritten:

Bearbeitung der Aufgabe 1 mit dem Simplexverfahren

• LP := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y ], 120*x +

90*y, NonNegative]:

• linopt::maximize(LP)

☯OPTIMAL, �x = 400, y = 600�, 102000�

Änderung zum Minimierungsproblem: • LP2 := [[1000 >= x + y, y <= 800, 2400 >= 3*x + 2*y ], -120*x

- 90*y, NonNegative]:

Anzeigen des ersten Simplextableaus • T1:=linopt::Transparent(LP2)

"linopt" "restr" slk1 slk2 slk3 y x

"obj" 0 0 0 0 − 90 − 120slk1 1000 1 0 0 1 1slk2 800 0 1 0 1 0slk3 2400 0 0 1 2 3

Ausgabe der erreichten Ecke: • linopt::Transparent::result(T1)

�x = 0, y = 0�

Vorschlag des Programms zum Basisaustausch (slk3 gegen x): • linopt::Transparent::suggest(T1)

slk3, x

Automatische Durchführung des nächsten Schrittes (Austausch der vorgeschlagenen Variablen): • T2:=linopt::Transparent::autostep(T1)

27

"linopt" "restr" slk1 slk2 slk3 y x

"obj" 96000 0 0 40 − 10 0

slk1 200 1 0 −13� 1

3� 0

slk2 800 0 1 0 1 0

x 800 0 0 13� 2

3� 1

Diese Vorgehensweise wird wiederholt, bis das Tableau optimal ist: • linopt::Transparent::result(T2)

�x = 800, y = 0�

• linopt::Transparent::suggest(T2)

slk1, y

• T3:=linopt::Transparent::autostep(T2)

"linopt" "restr" slk1 slk2 slk3 y x

"obj" 102000 30 0 30 0 0y 600 3 0 − 1 1 0

slk2 200 − 3 1 1 0 0x 400 − 2 0 1 0 1

Wie man bereits sieht, ist das Tableau optimal: • linopt::Transparent::result(T3)

�x = 400, y = 600�

• linopt::Transparent::suggest(T3)

OPTIMAL

• T4:=linopt::Transparent::autostep(T3)

�x = 400, y = 600�

Man kann das Programm auch zu einem selbst gewählten Schritt zwingen: • T5 := linopt::Transparent::userstep(T1,slk[1],x)

28

"linopt" "restr" slk1 slk2 slk3 y x

"obj" 120000 120 0 0 30 0x 1000 1 0 0 1 1

slk2 800 0 1 0 1 0slk3 − 600 − 3 0 1 − 1 0

Wie man sieht, ist es mit Hilfe dieses Programms möglich die einzelnen Schritte des

Simplexalgorithmus sehr genau zu verfolgen. Man kann sich entweder nur die auszutau-schenden Variablen anzeigen lassen und die Rechnung selbst durchführen oder die auszutau-schenden Variablen angeben und dann vom Programm das nächste Tableau erzeugen lassen. Natürlich ist es auch möglich sich jeden einzelnen Schritt nur anzusehen, ohne selbst zu re-chen. Zusätzlich lässt sich durch den Befehl linopt::Transparent::result(T1) sehr genau mitverfolgen, an welcher Ecke des zulässigen Bereichs sich der Simplex gerade befin-det. Es sind also viele Möglichkeiten vorhanden, mit denen die Schüler experimentieren kön-nen und so die Arbeitsweise des Algorithmus kennen lernen.

Außerdem lassen sich die linearen Programme in einfacher und intuitiver Form einge-ben und die graphische Darstellung des zulässigen Bereichs bei einem Problem mit zwei Va-riablen lässt sich hier, aufgrund der vorhandenen Befehle in der Bibliothek, ohne Probleme durchführen. Damit unterscheidet sich das Programm wesentlich von allen anderen Program-men, die vorgestellt werden.

Das Programm ist nach Erlernen der wichtigsten Befehle sehr leicht und intuitiv zu be-dienen, daher erscheint es mir äußerst geeignet für den Schulunterricht. Allerdings löst es nur lineare Optimierungsprobleme, daher kann Aufgabe 3 nicht bearbeitet werden.

Im Gegensatz zu Excel muss zur Nutzung des Programms MuPAD im Unterricht eine Schullizenz erworben werden. Deren Kosten belaufen sich für eine unbegrenzte Schullizenz von MuPAD Pro auf Euro 398,-. Eine leicht eingeschränkte Lizenz (Funktionsumfang wie MuPAD Pro, jedoch ohne Entwicklungsumgebung) ist für Euro 145,- zu haben. Die Preise sind auf der Webseite www.additive-net.de/software/mupadpro/mupadpro.schule.shtml nach-lesbar. Weiterhin findet sich dort eine kostenlose Demoversion zum Herunterladen, deren Nutzung aber auf 30 Tage beschränkt ist.

29

2.2.3 XPRESS – MP

Xpress – MP ist ein Softwareprogramm, das ausschließlich der mathematischen Opti-mierung dient und sich daher von den bisher behandelten Programmen unterscheidet. Es soll auf seine „Schultauglichkeit“ untersucht werden, hilfreich erwies sich dabei [8],[9] und [10]. Mit diesem Programm können lineare, gemischt – ganzzahlige oder quadratische Optimie-rungsaufgaben gelöst werden. Wichtige Elemente von Xpress – MP sind Xpress – Mosel und der Xpress - Optimizer:

• Xpress – Mosel: in diesem Programm verwendete Programmiersprache • Xpress – Optimizer: Optimierungsbibliothek

Zunächst muss den Schülern die Struktur eines LP im Mosel–Quellcode und die Vorgehens-weise mit diesem Programm erläutert werden: Model model_name

[ Directives ]

[ Parameters ]

[ Body ]

end – model

Vorgehensweise: • Starte Xpress IVE • Klick: File > new • Save “Aufgabe1.mos” • Schreibe den gewünschten Kode in das Hauptfenster in der Mitte • Zum Kompilieren des Modells: Build > Compile, es wir die Datei model-name.bim

erzeugt • Zum Ausführen und starten des Optimizers: Build > Run: • Im rechten Fenster erscheint die Lösung

Die Xpress-MP Oberfläche gliedert sich in mehrere Fenster:

Abbildung 2.19: Xpress - MP

30

Das Hauptfenster in der Mitte dient der Eingabe des Quellcodes, Befehle gibt man im Fenster links unten an (z.B. Fehler beim Kompilieren werden ebenfalls hier angezeigt). Das Fenster am rechten Rand zeigt die gewünschte Ausgabe, dort können auch weitere Informati-onen wie z.B. die benötigte Anzahl an Simplexschritten abgelesen werden.

Der Quellcode zur ersten Aufgabe sollte mit den Schülern gemeinsam erarbeitet werden,

es ergibt sich (wobei Kommentare durch ein vorangestelltes ! gekennzeichnet werden): Lösung zu Aufgabe 1

model Aufgabe1b

uses "mmxprs" !importiert das Modul mmxprs,

declarations !Angabe der Variablen

x: mpvar

y: mpvar

end-declarations

!Zielfunktion:

Profit := 120*x + 90*y

!1.Nebenbedingung

Bed1 := x + y <= 1000

!2.Nebenbedingung

Bed2 := y <= 800

!3.Nebenbedingung

Bed3 := 3*x + 2*y <= 2400

!Maximierung der Zielfunktion

maximize(Profit)

!Ausgabe des maximalen Profits und

!zugehöriger Mengen

writeln("Der maximale Profit beträgt ",getobjval) writeln("Die Anzahl der Handytypen 1 beträgt ",getsol(x))

writeln("Die Anzahl der Handytypen 2 beträgt ",getsol(y))

end-model

An diesem Beispiel sieht man, dass das Modell in einem sogenannten „Modellblock“ eingeschlossen wird (model... > end–model). Mit dem Befehl “uses mmxprs” signali-siert man Mosel, dass der Xpress Optimizer zur Lösung des Problems herangezogen werden soll. Die Variablen sind im “declarations”- Block zu deklarieren und sind vom Typ mpvar für LP (lineare Programme), MIP (gemischt-ganzzahlige Programme) und QP (quadratische Pro-gramme) gleichermaßen. Mosel setzt voraus, dass alle Variablen nicht–negativ sind, daher muss diese Bedingung im Block der Nebenbedingungen nicht mehr angegeben werden. Die Zielfunktion Profit wird wie die Nebenbedingungen deklariert und anschließend durch den Befehl maximize(Profit) maximiert. Die letzten writeln- Statements bewirken eine Ausgabe des Zielfunktionswerts und der zugehörigen Variablenwerte. Nun ist das Programm bereit zum Kompilieren und Ausführen. Man erhält nach dem Kompilieren und Ausführen des Modells die erwartete Ausgabe:

Der maximale Profit beträgt 102000

Die Anzahl der Handytypen 1 beträgt 400

Die Anzahl der Handytypen 2 beträgt 600

31

Durch entsprechende Änderung des Quellcodes und erneutes Kompilieren und Ausfüh-ren ergeben sich schnell auch die Lösungen zu den Aufgaben 1. c) und 1. d).

Die Schüler sollten nach ausführlicher Behandlung der ersten Aufgabe auch in der Lage sein, den folgenden Quellcode zur Aufgabe 2 zu entwerfen: Lösung zu Aufgabe 2

model Aufgabe2

uses "mmxprs" !importiert das Modul mmxprs

declarations !Angabe der Variablen

x, y, z, w : mpvar

end-declarations

Profit:= 120*x + 90*y + 150*z + 70*w

Bed1:= x + y + z + w <= 1800

Bed2:= y <= 800

Bed3:= z <= 400

Bed4:= w <= 900

Bed5:= 3*x + 2*y + 6*z + 2*w <= 2400

x is_integer

y is_integer

z is_integer

w is_integer

maximize(Profit) !Maximierung der Zielfunktion

writeln("Der maximale Profit beträgt ",getobjval)

writeln("Die Anzahl der Handytypen 1 beträgt ",getsol(x))

writeln("Die Anzahl der Handytypen 2 beträgt ",getsol(y))

writeln("Die Anzahl der Handytypen 3 beträgt ",getsol(z))

writeln("Die Anzahl der Handytypen 4 beträgt ",getsol(w))

end-model Somit erhält man folgende Ausgabe:

Der maximale Profit beträgt 103990

Die Anzahl der Handytypen 1 beträgt 266

Die Anzahl der Handytypen 2 beträgt 800

Die Anzahl der Handytypen 3 beträgt 0

Die Anzahl der Handytypen 4 beträgt 1

Hier wurden die Bedingungen, dass die Variabeln nur ganzzahlige Werte annehmen dür-

fen, mit in den Quellcode aufgenommen. Lässt man diese Bedingungen weg (wie dies die Schüler vermutlich zunächst tun werden), ergibt sich folgende Lösung:

Der maximale Profit beträgt 104000

Die Anzahl der Handytypen 1 beträgt 266.667

Die Anzahl der Handytypen 2 beträgt 800

Die Anzahl der Handytypen 3 beträgt 0

Die Anzahl der Handytypen 4 beträgt 0

32

Dass diese Lösung in der Praxis keinen Sinn ergibt, ist offensichtlich. Xpress kann auch quadratische Optimierungsprobleme lösen: Lösung zu Aufgabe 3

model Aufgabe3

uses "mmxprs","mmquad"

declarations

x: mpvar

y: mpvar

end-declarations

F:= x*y

Bed:= 2* x+ y =3

maximize(F)

writeln("Die maximale Fläche beträgt ",getobjval)

end-model

Man erhält folgende Ausgabe:

Die maximale Fläche beträgt 1.125

Meiner Meinung nach ist dieses Programm zum Einsatz in der Schule nur bedingt ge-

eignet. Die Schüler müssen zunächst den (teilweise für größere Probleme) komplizierten Quelltext verstehen bzw. selbst schreiben. Dadurch besteht die Gefahr, dass weniger die Op-timierung als die Programmierung im Vordergrund stehen. Zudem lässt sich das Programm zur Veranschaulichung des Simplexalgorithmus (wie beispielsweise MuPAD) nicht einsetzen. Ist der Quellcode allerdings erstellt (und ausreichend gut verstanden), lässt er sich schnell und einfach nach Wunsch verändern.

Dieses Programm kann natürlich auch wesentlich größere Probleme aus der Praxis be-arbeiten als das durch MuPAD oder Excel der Fall wäre. Dies könnte den Schülern durch ein Beispiel erläutert werden. Beispiele finden sich unter anderem auf www.dashoptimization.com.

33

2.2.4 Das Computeralgebrasystem DERIVE

Derive ist das wohl in den Schulen am häufigsten eingesetzte Computeralgebrasystem. Es ermöglicht unter anderem das Aufstellen von Gleichungen und deren Lösungen mit belie-biger Genauigkeit. Umfangreiche algebraische Umformungen werden schnell ausgeführt und es können Kurven gezeichnet werden.

Im Folgenden sollen Möglichkeiten gefunden werden, Derive im Mathematikunter-richt zur Einführung der linearen Optimierung einzusetzen.

In diesem Programm werden die Ausdrücke in eine Kommandozeile eingetragen und mit Return bestätigt. Sie erscheinen dann im Algebrafenster. Dann können durch „2-D Gra-phikfenster > Ausdruck zeichen“ die hier benötigten Geraden, die vorher im Algebrafenster markiert wurden, in einem separaten Graphikfenster gezeichnet werden. Durch „Datei > Ein-betten“ wir die Graphik aus dem Graphikfenster dann in das Algebrafenster übertragen. Zwei weitere wichtige Befehle sind Solve([u(x,y),v(x,y),...],[x,y]), mit dem ein Gleichungssystem gelöst, sowie „Vereinfachen > Variablensubstitution“, mit dem Werte in eine Gleichung ein-gesetzt werden können .

Ich beschreibe in diesem Abschnitt genau, wie die Aufgabe 1. b) schrittweise mit De-rive sehr anschaulich gelöst werden kann. In Derive gibt es keine speziellen Befehle zur linea-ren Optimierung, wie das beispielsweise in MuPAD der Fall ist. Daher kann hier nur eine Art „graphische Lösung am Rechner“ durchgeführt werden, bzw. eine Berechnung aller vorhan-denen Eckpunkte mit anschließendem Vergleich der Zielfunktionswerte (siehe Lösung zur Aufgabe 2). Dieses Vorgehen ist natürlich für größere Probleme nicht mehr sinnvoll. In meinen Ausführungen orientiere ich mich an den beiden Artikeln [18] und [19]. Lösung zu Aufgabe 1

zu Aufgabe 1. b) :

1 : x + y = 1000

2 : y = 800

3 : 3·x + 2·y = 2400

4 : „ Berechnung der Schnittpunkte der Geraden zur Zeichnung des

Zulässigkeitsbereichs“

5 : SOLVE([x + y = 1000, y = 800], [x, y])

6 : [x = 200 , y = 800]

7 : SOLVE([x + y = 1000, 3·x + 2·y = 2400], [x, y])

34

8 : [x = 400 , y = 600]

9 : [800·CHI(0, x, 200), (1000 - x)·CHI(200, x, 400), (1200 –

3/2·x)·CHI(400, x, 800)]

10 : 120·x + 90·y = 20000

11 : “Zeichnen liefert:”

12 : 120·x + 90·y = 40000

13 : 120·x + 90·y = 60000

35

14 : 120·x + 90·y = 80000

15 : 120·x + 90·y = 100000

16 : 120·x + 90·y = 120000

17 : “Der Schnittpunkt der beiden Geraden 1 und 3 muss den opti-

malen Zielfunktionswert liefern:“

18 : SOLVE([x + y = 1000, 3·x + 2·y = 2400], [x, y])

19 : [x = 400 , y = 600]

20 : „Einsetzen von x = 400 und y = 600 in die Zielfunktion er-

gibt :“

21 : 120·x + 90·y

22 : 120·400 + 90·600

23 : 102000

zu Aufgabe 1. c)

24 : „neue Zielfunktion und Zeichnung:“

25 : 135·x + 90·y

26 : 135·x + 90·y = 90000

27 : 135·x + 90·y = 110000

36

26 : „Man sieht deutlich, dass nun keine eindeutige optimale Lö-

sung mehr existiert.“

zu Aufgabe 1. d) (Beispiel)

27 : „Weglassen der ersten und dritten Nebenbedingung ergibt:“

28 : Der zulässige Bereich ist unbeschränkt.

Lösung zu Aufgabe 2:

Mit den Schülern sollte zuvor besprochen worden sein, dass die optimale Lösung am

Rand der zulässigen Menge zu finden ist. Daher ist es theoretisch möglich durch Berechnen der Eckpunkte die optimale Lösung zu finden. Dies wäre ohne CAS viel zu aufwendig, ist hier aber für kleinere Probleme noch durchführbar. Allerdings bereits bei diesem Beispiel mit

=

4

870 möglichen Eckpunkten, die berechnet werden sollen, wird den Schülern klar wie

aussichtslos dieses Verfahren bei noch größeren Problemen ist. Die Klasse sollte in zweier Gruppen aufgeteilt werden, die jeweils verschiedene Ecken folgendermaßen bearbeiten:

1 : „Eingabe der Nebenbedingungen in Gleichungsform :“

2 : x + y + z + w = 1800

3 : y = 800

4 : z = 400

5 : w = 900

37

6 : 3·x + 2·y + 6·z + 2·w = 2400

7 : x = 0

8 : y = 0

9 : z = 0

10 : w = 0

11 : „Berechnung eines beliebigen Eckpunktes:“

12 : SOLVE([x + y + z + w = 1800, y = 800, z = 400, w = 900],

[x, y, z, w])

13 : [x = -300 , y = 800 , z = 400 , w = 900]

14 : „Diese Lösung ist unzulässig !“

12 : „Berechnung eines weiteren Eckpunktes:“

13 : SOLVE([y = 0, w = 0, x + y + z + w = 1800, z = 0], [x, y,

z, w])

14 : [x = 1800, y = 0 , z = 0 , w = 0]

15 : „Die Zielfunktion lautet:“

16 : 120·x + 90·y + 150·z + 70·w

17 : „Damit ist der Zielfunktionswert:“

18 : 120·1800 + 90·0 + 150·0 + 70·0

19 : 216000

20 : Es muss überprüft werden ob alle Nebenbedingungen erfüllt

sind, z.B.:

21 : 3·x + 2·y + 6·z + 2·w = 2400

22 : 3·1800 + 2·0 + 6·0 + 2·0 = 2400

23 : 5400 = 2400

24 : Diese Nebenbedingung ist nicht erfüllt! Lösung ist unzuläs-

sig

...

Auf diese Art und Weise können alle Eckpunkte mit Derive untersucht werden und so

auch die optimale Lösung (die in diesem Fall nicht ganzzahlig sein wird) gefunden werden. Diese Vorgehensweise kann natürlich auch mit den beiden anderen CAS MuPAD und MA-THEMATICA verfolgt werden. Allerdings sehe ich mit diesem Programm keine Möglichkeit, die optimale ganzzahlige Lösung zu ermitteln. Auch bietet sich keine Möglichkeit, den Sim-plexalgorithmus so einfach, wie beispielsweise mit MuPAD, einzuführen.

Mit diesem Programm erschließen sich also wenig Möglichkeiten zur Behandlung von linearen Optimierungsaufgaben, ich würde daher, falls vorhanden, ein anderes Programm be-vorzugen.

Die Kosten für eine Derive 5/6 Schullizenz (alle Computer einer Schule, sowie private

Computer der Lehrer zur Unterrichtsvorbereitung) liegen mit 399 Euro in ähnlicher Höhe wie die des Programms MuPAD. Die Kosten sind beispielsweise nachlesbar auf der Homepage www.shop.bk-teachware.com/k.asp?session=2397944&kat=8. Dort ist ebenfalls eine 30-Tage De-moversion erhältlich.

38

2.2.5 Das Computeralgebrasystem MATHEMATICA

Zuletzt möchte ich das Computeralgebrasystem Mathematica untersuchen. Es ist ein sehr leistungsfähiges Werkzeug und kann unter anderem in den Bereichen Fourier – Trans-formation, lineare Algebra, Kurvenanpassung, numerische Integration und lineare Optimie-rung eingesetzt werden. Wie an diesen Themengebieten schon deutlich wird, kann es weit über den normalen Mathematikunterricht hinaus auch im Studium und Beruf eingesetzt wer-den.

Die Eingabe erfolgt hier in Zellen, die am Rand angezeigt werden, in einem Notebook:

Abbildung 2.20: Mathematica Notebook

Die lineare Optimierungsbibliothek von Mathematica enthält allerdings wesentlich weni-ger Befehle als die vom vergleichbaren CAS MuPAD. Im Wesentlichen beschränkt sie sich auf die folgenden Befehle:

• Maximize[{f,cons},{x,y,...}] Maximiert die Funktion f unter den Nebenbedingungen cons und den Variablen x, y,... Der Befehl Minimize[{f,cons},{x,y,...}]arbeitet analog. Mit diesen Befehlen können auch nichtlineare und ganzzahlige Optimierungsprobleme gelöst werden.

Es gibt noch eine zweite Möglichkeit lineare Probleme zu lösen:

• LinearProgramming[c, m, b] Sucht einen Vektor x, der c minimiert (soll maximiert werden, muss die Zielfunktion mit –1 multipliziert werden). Die Nebenbedingungen müssen in der Form m.x >= b

und x >= 0 vorliegen. Um auch Probleme mit Nebenbedingungen in einer anderen Form lösen zu können, muss der Befehl variiert werden:

• LinearProgramming[c, m, {{b1, s1}, {b2, s2}, … }]

39

Hier gilt: Falls si = 1 ist, liegt eine Nebenbedingung der Form mi.x >= bi vor, für si = 0 eine Nebenbedingung der Form mi.x = bi und für si = -1 eine Nebenbedingung der Form mi.x <= bi .

Es gibt hier keinen Befehl, der speziell den zulässigen Bereich zeichnet, man kann je-doch folgendermaßen vorgehen (fett gedruckt ist jeweils die Eingabe, schmal die Ausgabe): Lösung zu Aufgabe 1

Aufgabe 1. b) Graphische Lösung: Eingabe der Nebenbedingungen und Umformung in Geradenform: Solve[x+y���� 1000,y] {{y→1000-x}} f[x_]:=1000-x Solve[3 x + 2 y���� 2400,y]

::y® -

3

2H- 800 + xL>>

g[x_]:=-3/2(-800+x) h[x_]:=800 Plot[{{1000-x},800,{-3/2(-800+x)}},{x,0,1000}]

200 400 600 800 1000

-200

200

400

600

800

1000

1200

� Graphics� Berechnung der Geradenschnittstellen zur Zeichnung des zulässi-gen Bereichs: Simplify[h[x_]==f[x_]] x_� 200 f[200] 800 Simplify[f[x_]���� g[x_]] x_� 400 f[400] 600 Wir haben also (0/ 800), (200/ 800), (400/ 600), (800/ 0). g=ListPlot[{{0,800},{200,800},{400,600},{800,0}},PlotJoined→→→→True,PlotRange→→→→{{0,1000}, {0,1000 }},AxesLabel→→→→{x,y}]

40

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� Zeichnen der Zielfunktion: Solve[120x+90 y���� Z,y]

::y®

1

90H- 120x+ ZL>>

g1=Show[g, Plot[1/90(-120 x+60000),{x,0,1000}]]

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� g2=Show[g1, Plot[1/90(-120 x+80000),{x,0,1000}]]

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� g3=Show[%, Plot[1/90(-120 x+100000),{x,0,1000}]]

41

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� g4=Show[%, Plot[1/90(-120 x+120000),{x,0,1000}]]

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� Zusammenfassung Show[GraphicsArray[{{g1,g2},{g3,g4}}]]

2004006008001000x

2004006008001000

y

2004006008001000x

2004006008001000

y

2004006008001000x

2004006008001000

y

2004006008001000x

2004006008001000

y

� GraphicsArray� Man kann ablesen, dass der optimale Zielfunktionswert an der Ecke (400/600), die oben berechnet wurde, angenommen wird. Zielfunktionswert: x=400;y=600;120 x+ 90 y 102000 Clear All All Clear Clear[x, y] "Rechnerische" Lösung: Maximize[{120 x+90 y,x+y≤≤≤≤1000,y≤≤≤≤800,3 x+2 y≤≤≤≤2400},{x,y}]

42

{102000,{x→400,y→600}} oder LinearProgramming[{-120,-90},{{1, 1},{0, 1},{3, 2}},{{1000, -1},{800, -1},{2400, -1}}] {400,600} Aufgabe 1. c) Änderung der Zielfunktion: g=ListPlot[{{0,800},{200,800},{400,600},{800,0}},PlotJoined→→→→True,PlotRange→→→→{{0,1000}, {0,1000 }},AxesLabel→→→→{x,y}] � Graphics� g1=Show[g, Plot[1/90(-135 x+90000),{x,0,1000}]]

200 400 600 800 1000x

200

400

600

800

1000

y

� Graphics� Maximize[{135 x+90 y,x+y≤≤≤≤1000,y≤≤≤≤800,3 x+2 y≤≤≤≤2400},{x,y}] {108000,{x→400,y→600}} Aufgabe 1. d) Änderung der Nebenbedingungen: z.B. Weglassen von Bedingung 1 und 3 Plot[{{1/90(-120 x+90000)},800},{x,0,1000}]

200 400 600 800 1000

-200

200

400

600

800

1000

� Graphics� Maximize[{120 x+90 y,x≤≤≤≤800},{x,y}]

43

Maximize ::natt : The maximum is not attained at

any point satisfying the given constraints . More… {∞,{x→Indeterminate,y→Indeterminate}} Clear All All Clear

Lösung zu Aufgabe 2

Aufgabe 2: Maximize[{120 x+90 y+150 z+70 w,x+y+z+w≤≤≤≤1800,y≤≤≤≤800,z≤≤≤≤400,w≤≤≤≤900,3 x+2 y+6 z+2 w≤≤≤≤2400},{x,y,z,w}]

Maximize ::natt : The maximum is not attained at

any point satisfying the given constraints . More…

{∞,{x→Indeterminate,y→Indeterminate,z→Indeterminate,w→Indeterminate}} LinearProgramming[{-120,-90,-150,-70},{{1, 1, 1, 1},{0, 1, 0, 0},{0, 0, 1, 0},{0,0,0,1},{3, 2, 6, 2}},{{1800, -1},{800, -1},{400,-1},{900,-1},{2400, -1}}]

:800

3, 800, 0, 0>

Das Programm sollte eigentlich in der Lage sein, mit dem Befehl „Maximize“ Probleme mit mehr als zwei Variablen zu lösen. Jedoch auch nach mehrmaliger Eingabe und Überprü-fung erhielt ich immer das oben gezeigte Ergebnis

Maximize ::natt : The maximum is not attained at

any point satisfying the given constraints . More…

Daher gehe ich davon aus, dass hier Probleme im Programm vorliegen. Der Befehl „Linear Programming“ löst zwar, wie oben gezeigt, Probleme mit mehr als zwei Variablen mit der erwarteten Lösung, jedoch ist es hier nicht möglich, eine gewünschte ganzzahlige Lö-sung zu erhalten. Außerdem ist dieser Befehl aufgrund seiner Matrixschreibweise wesentlich schwerer zu verstehen und anzuwenden. Auch findet sich kein Befehl zur Darstellung des Simplextableaus. Als Lösung für die nichtlineare Aufgabe ergibt sich leicht: Lösung zu Aufgabe 3 Maximize[{x y, 2 x+y==3},{x,y}]

:98,:x®

3

4, y ®

3

2>>

Dieses Programm ist sicherlich sehr leistungsstark und vielseitig einsetzbar, jedoch er-scheint es mir teilweise etwas zu kompliziert für den Einsatz in der Schule. Dabei denke ich vor allem an den Befehl LinearProgramming... . Es ist ein Vorteil dieses Programms, dass hier Befehle zur linearen Optimierung integriert wurden, jedoch fällt beispielsweise die linea-re Optimierungsbibliothek von MuPAD umfangreicher aus. Ein einschneidender Unterschied

44

sind die Befehle zur Zeichnung des zulässigen Bereichs und der Ausgabe des Simplex-tableaus. Dafür löst Mathematica im Gegensatz zu MuPAD auch nicht-lineare Programme.

Über die Kosten für eine Schullizenz für dieses Programm habe ich leider keine verläss-lichen Angaben gefunden.

2. 3 Schlussbetrachtung

Im Abschnitt 2.2 wurden fünf teilweise sehr verschiedene Softwareprogramme unter-sucht, die in der Schule bei der Einführung des Themas „Lineare Optimierung“ zum Einsatz kommen können. Dabei erhebe ich selbstverständlich keinen Anspruch auf Vollständigkeit. Es gibt natürlich noch sehr viele Programme, die sich hierfür eignen würden. Ich habe ledig-lich eine Auswahl der zur Zeit am häufigsten erwähnten Programme auf ihre Fähigkeiten hin untersucht und hoffe dabei deren Möglichkeiten gerecht geworden zu sein. Die Programme unterscheiden sich teilweise sehr stark in der Handhabung und den vorhandenen Möglichkei-ten.

Besonders hervorgetan hat sich meiner Meinung nach das Computeralgebrasystem MuPAD, das durch seine umfangreiche Bibliothek besticht. Lineare Programme lassen sich somit einfach eingeben und bearbeiten. Die gestellten Aufgaben konnten, bis auf die nicht-lineare Aufgabe 3, leicht und anschaulich gelöst werden. Somit ergeben sich bei Verwendung dieses Programms vermutlich keine technisch bedingten Probleme auf Seiten der Schüler bzw. keine durch langwierige Rechungen verursachten Probleme mehr. Speziell die Möglich-keiten zur Darstellung des Simplextableaus verdienen Beachtung. Kein anderes Programm weist hier auch nur ähnliche Möglichkeiten auf.

Auch das Tabellenkalkulationsprogramm Excel überrascht durch vielfältige Möglich-keiten. Besonders die Bildlaufleiste lässt sich hier sehr effektiv bei der Einführung des The-mas einsetzen, die Parallelverschiebung der Zielfunktion über den zulässigen Bereich wird mit keinem anderen Programm besser deutlich. Auch der SOLVER wird vermutlich, nach kleineren Anfangsschwierigkeiten beim ersten Einsatz, später keine Probleme mehr bereiten.

Die Einführung von Xpress MP würde ich dagegen in der Schule, wie bereits erwähnt, vermeiden. Dieses Programm ist zu spezialisiert auf den Einsatz in der linearen Optimierung und auch nicht für die Anwendung in der Schule gedacht. Mathematica geht mit seinen Mög-lichkeiten, wie bereits besprochen, weit über die in der Schule benötigten Anwendungen hin-aus und ist in der Handhabung schwieriger als MuPAD oder Derive. Daher würde ich die zu-letzt genannten Programme vorziehen.

Es ist vermutlich am besten, ein Computeralgebrasystem im Mathematikunterricht einzuführen, mit dem dann immer gearbeitet werden kann. Somit ergeben sich nicht in jeder Stunde am Rechner wieder Einführungsschwierigkeiten in das jeweilige Programm. Wo finde ich das Programm? Wie gebe ich eine einfache Gleichung ein? etc. Probleme dieser Art sollen so vermieden werden. Hierfür empfiehlt sich nach meinen Erfahrungen bei dieser Arbeit eines der Programme MuPAD oder Derive (oder Mathematica). Die Schüler lernen so die Möglich-keiten eines Programmes ausführlich kennen und können diese später auch schnell auf andere Programme übertragen.

Insgesamt lässt sich wohl sagen, dass sich der Rechner in dieser Unterrichtsreihe sehr sinnvoll einsetzen lässt. Die Schüler erfahren, wie viel Arbeit durch den PC eingespart werden kann und erlernen gleichzeitig den Umgang mit Mathematiksoftware bzw. bekommen einen Einblick in deren Einsatzgebiete. Diese Erfahrungen mit dem Rechner können dann auch in anderen Gebieten des Mathematikunterrichts weiter vertieft werden.

45

3. Literaturverzeichnis

[1] Lehrplan Mathematik, Klassen 7 – 9/10, Hauptschule, Realschule, Gymnasium,

Rheinland – Pfalz, Grünstadt 1984 [2] Lehrplan Mathematik, Grund – und Leistungsfach, Jahrgangsstufen 11 bis 13 der

gymnasialen Oberstufe, Rheinland – Pfalz, 1998 [3] Karl Schick, Lineares Optimieren, Einführung in die mathematische Behandlung mo-

derner Probleme in den Wirtschaftswissenschaften, 3.Auflage, Verlag Moritz Diester-weg, Frankfurt am Main

[4] Reichel, Müller, Lehrbuch der Mathematik 5, öbv&hpt, Wien 2002, S.228 – 249 [5] Mathematik in der Praxis, Anwendungen in Wirtschaft, Wissenschaft und Politik,

Spektrum Verlag, Heidelberg [6] Markus Paul, Extremwertprobleme mit EXCEL, Teil 1: Lineare Optimierung und Ex-

tremwertaufgaben, www.minic.ac.at/ammu/15/15_2.htm [7] MuPAD Homepage, www.schule.mupad.de [8] Susanne Scholl, Introduction to Xpress – MP, december 2003 [9] Xpress – Mosel: User Guide,

www.ingre.unimo.it/OR/corsi/MSS/MaterialeDidattico/mosel_userguide.pdf [10] Yves Colombani & Susanne Heipcke, Mosel: An Overview,

www.dashoptimization.com/pdf/Mosel1.pdf [11] Heute und Morgen, Sozialkunde Rheinland-Pfalz, Ernst Klett Schulbuchverlag,

1.Auflage, Stuttgart 1987 [12] Mathematik heute, Differenzierte Ausgabe für Realschulen und Gymnasien,

9.Schuljahr, Schroedel Schulbuchverlag, Hannover 1982 [13] Lambacher Schweizer 9, Ausgabe für Rheinland – Pfalz, Ernst Klett Schulbuchverlag,

1. Auflage, Stuttgart 1992 [14] Handreichungen, V4 Lineare Optimierung, www.mint-

hamburg.de/Handreichungen/Ma-gyO/Vorstufe/V4.pdf [15] Horst W.Hamacher, Kathrin Klamroth, Lineare und Netzwerk- Optimierung, Ein bi-

linguales Lehrbuch, Vieweg, 1. Auflage September 2000, Braunschweig/ Wiesbaden [16] Behnke, Bertram, Sauer, Grundzüge der Mathematik IV, Praktische Methoden und

Anwendungen der Mathematik für Lehrer an Gymnasien sowie für Mathematiker in Industrie und Wirtschaft, Göttingen, Vandenhoeck & Ruprecht 1966

46

[17] Modellieren mit Mathe: Werkzeug: Excel www.schule.suedtirol.it/blikk/angebote/modellmathe/ma1905.htm

[18] Anke Wieschendorf, Sabine Lassahn, Marianne Meyer, Lineare Optimierung unter

Verwendung von Derive, Der Mathematikunterricht. Beiträge zu seiner wissenschaft-lichen und methodischen Gestaltung, Jan 1998

[19] U. Keusen, H.J. Kayser, Lineare Optimierung. Stufe 8, Mathematik. Betrifft uns. 1994

47

4. Versicherung über die selbstständige Anfertigung der Projektstudie und

der verwendeten Hilfsmittel

Hiermit versichere ich, dass ich die vorliegende Projektstudie selbstständig verfasst und keine anderen als die angegebenen Hilfsmittel verwendet habe.

Ort /Datum Unterschrift