Lineare OptimierungMathematikreferat von Matthias Faß FG 99 im Mai 2002 Inhaltsverzeichnis: Seite
2. Geschichte der „linearen Optimierung“ 1 3. Graphisches Verfahren 2 3.1 Aufgabenstellung 2 57158hnl89gjo6g 3.2 Graphische Lösung 3 4. Die reguläre Simplexmethode 6 5. Simplex – Tableau 12 5.1 Rechenregeln 13 nj158h7589gjjo Quellenangaben – Literaturverzeichnis 14 1. Einleitung: Was ist eigentlich „lineare Optimierung“? Die lineare Optimierung ist ein Teilgebiet der Optimierungsrechnung. Diese Rechnung ist ein Hilfsmittel zur optimalen Entscheidungsfindung bei komplizierten Problemen. Unter einschränkenden Bedingungen wird mit Hilfe der linearen Optimierung das Minimum beziehungsweise das Maximum einer linearen Funktion ermittelt. Die zu maximierende Funktion ist dabei meistens die Gleichung für den Gewinn, die zu minimierende Funktion die Gleichung für die Kosten eines Unternehmens. Die einschränkenden Bedingungen, die Einfluss auf das Ergebnis haben, müssen herausgefunden werden, um sie dann mit dem zu erreichenden Maximum / Minimum in Verbindung zu setzen. 2. Geschichte der „linearen Optimierung“ Die lineare Optimierung gehört zu den jüngeren Anwendungsgebieten der Mathematik. Vor einem halben Jahrhundert begann der richtige Durchbruch der linearen Optimierung mit der Simplexmethode, die von G.B. Dantzig entwickelt wurde. Die ersten Arbeiten der Linearen Optimierung wurden im Jahre 1939 von dem russischen Mathematiker Leonid W. Kantorowicz in diesem Gebiet veröffentlicht. Besonders in den USA wurden am Ende des zweiten Weltkrieges neue Lösungsmöglichkeiten für Probleme der mathematischen Optimierung, die für den militärischen Bereich von Bedeutung waren, entwickelt. Die Simplexmethode, mit der alle linearen Optimierungsprobleme gelöst werden können, ist bis heute das wichtigste Verfahren zur Lösung von Problemen dieser Art. J. von Neumann und O. Morgenstern gelang es schon kurz nach Dantzig diese Methode beträchtlich weiterzuentwickeln. Seit Beginn der 50er Jahre erlebte dieser Bereich der Mathematik erneut eine rapide Aufwärtsentwicklung. Dieser große Aufschwung wirkte sich besonders günstig auf Großrechenanlagen aus, die Berechnungen nach dem Simplexverfahren in einer kurzen Zeit bewältigen konnten. Schon im Jahre 1956 konnten mit einer IBM- Maschine Probleme der linearen Optimierung mit mehr als 200 Gleichungen mit großer Genauigkeit gelöst werden. Die erste wichtige Anwendung auf wirtschaftliche Probleme erfolgte bei der Planung und Entwicklung von Erdölraffinerien. Im Jahre 1979 entwickelte der Russe Khasian einen neuen Algorithmus, mit dem bei linearen Optimierungsproblemen mit einer großen Anzahl von Variablen und einschränkenden Bedingungen die optimale Lösung schneller bestimmt werden konnte. Der wesentliche Vorteil dieses Verfahrens liegt darin, dass der Rechenaufwand geringer ist, als beim Simplexverfahren. Heute gehört die lineare Optimierung zu den best erforschten Gebieten der Wirtschaftsmathematik. 3. Graphisches Verfahren 3.1 Aufgabenstellung Eine Unternehmung stellt zwei Produkte P1 und P2 her. Die Fertigung erfolgt auf den Maschinen M1, M2 und M3 und erfordert unterschiedliche Belegungszeiten. Die Bearbeitungsdauer (bezogen auf Minuten) und die Kapazitäten (bezogen auf Mengeneinheiten) der Maschine sind in der folgenden Tabelle angegeben.
Der Deckungsbeitrag pro ME beträgt 90 GE von P1 und 120 GE von P2. Wie viele ME sind von P1 und von P2 herzustellen, damit der gesamte Deckungsbeitrag möglichst groß ist. Wie hoch ist dieser maximale Deckungsbeitrag? xi sei die Zahl der Produkte Pi Z = 90x1 + 120x2 } Zielfunktion 20x1 + 40x2 “ 8000 Maschine M1 15x1 + 10x2 “ 3000 Maschine M2 30x1 + 10x2 “ 5400 Maschine M3 x1 ’ 0 x2 ’ 0 Nichtnegativitätsbedingungen Die Zielfunktion ist das Optimierungskriterium, welches minimal oder maximal werden soll. In diesem Fall geht es um den Deckungsbeitrag, der maximal werden soll. Die Nebenbedingungen sind Restriktionen (Beschränkungen), die sich in diesem Fall aus den Kapazitätsbeschränkungen der Maschinen ergeben. Es gibt nämlich keinen Sinn negative Werte für x1 und x2 zuzulassen, denn die produzierte Menge kann nicht negativ sein. Deshalb unterliegen die Variablen x1 und x2 den Nichtnegativitätsbedingungen. 3.2 Graphische Lösung Für Systeme mit zwei Variablen lassen sich die möglichen Lösungsmengen in einer Ebene (zweidimensional) graphisch veranschaulichen: Für das Gleichheitszeichen wird mit jeder Nebenbedingung eine Gerade definiert, die die Ebene in zwei Halbebenen teilt. Durch das Ungleichheitszeichen wird die Halbebene spezifiziert, in der die mögliche Lösungsmenge liegt. Im Ergebnis entsteht ein Polygon (=Vieleck). Dazu stellt man zunächst die Nebenbedingungen nach x2 um. 20x1 + 40x2 “ 8000 / - 20x1 40x2 “ 8000 - 20x1 / : 40 x2 “ 200 - 0,5x1 x2 “ 300 - 1,5x1 x2 “ 540 - 3x1 Die Zielfunktion löst man auch nach x2 auf: Z = 90x1 + 120x2
3 Z x2 = - ——— + ————— 4 120
Die Graphen dieser Funktionenschar sind parallele Geraden, die danach unterschieden werden können, in welchen Punkten PZ „ Z † ¦0/ —————¦ sie die y- Achse schneiden. … 120 ‡ Man konstruiert die Gerade der Zielfunktion für Z = 0. Die Gerade wird solange parallel nach oben verschoben, bis sie an einem Eckpunkt das Polygon verlässt. Dieser Eckpunkt ist ein Optimum unseres Problems. Z=0 : 3 0 x2 = - ——— x1 + ———
3 x2 = - ——— x1 4
PMAX (100/150) ist der optimale Punkt. Man erzielt den höchsten Deckungsbeitrag, wenn 100 ME von P1 und 150 ME von P2 hergestellt werden. Berechnung des maximalen Deckungsbeitrags: ZMax = 90x 1 + 120x2 = 90*100 + 120*150 = 27000 Der maximale Deckungsbeitrag beträgt 27000 GE. Pmax(100/150) I x2 “ 200 – 0,5x1 II x2 “ 300 – 1,5x1 III x2 “ 540 – 3x1 Z = - 0,75x1 (Parallelverschiebung von Z nach Z1) 4. Die reguläre Simplexmethode Das graphische Verfahren zur Lösung von linearen Optimierungsproblemen ist nur anwendbar bei zwei, höchstens drei Variablen. Aber schon bei drei Variablen trifft man auf erhebliche Schwierigkeiten, weil drei Variablen eine räumliche Darstellung in der Zeichenebene verlangen. Bei n Variablen werden die Lösungsmengen von Hyperebenen im n – dimensionalen Raum begrenzt. Es ensteht ein Polyeder (= Vielflächner). Die Simplexmethode ist eine algebraische Methode, die es ermöglicht, lineare Optimierungsprobleme mit beliebig vielen Variablen einfach und übersichtlich zu lösen. Ein Simplex ist ein Polyeder des R n (n – dimensionalen Raums) mit n + 1 Ecken. zum Beispiel: R2: Dreieck R3: Tetraeder
Das Simplexverfahren ist ein Iterationsverfahren (schrittweises Rechenverfahren zur Annäherung an die exakte Lösung). Man beginnt mit einer Startnäherung (meist xi = 0) und verbessert sukzessive (allmählich eintretend) die Zielfunktion. Das Verfahren wird an dem obigen Beispiel erläutert: a) Durch Einführen von Schlupfvariablen (ui ’ 0) wird das Optimierungsproblem als lineares Gleichungssystem formuliert. Die Schlupfvariable füllt den noch vorhandenen „Spielraum“ aus, wenn die Werte für x1 und x2 des linken Teils der Ungleichung kleiner als der Wert des rechten Teils sind. Die Schlupfvariablen u1, u2 und u3 übernehmen also die Werte der jeweils noch freien Kapazität der Maschinen M1, M2 und M3. 20x1 + 40x2 + u1 = 8000 15x1 + 10x2 + u2 = 3000 30x1 + 10x2 + u3 = 5400
90x1 + 120x2 = Z (4 Gleichungen, 6 Unbekannte) Basisvariable: Variable, die nach Vorgabe von zwei Variablen berechnet wird (u1, u2, u3)
Nichtbasisvariable: frei vorgebbare Variablen (= 0) (x1, x2) b) Startpunkt: x1 = x2 = 0 (Nichtbasisvariablen)
Berechnen der Basisvariablen I u1 = 8000 – 20x1 – 40x2 II u2 = 3000 – 15x1 – 10x2 III u3 = 5400 – 30x1 – 10x2 IV Z = 90x1 + 120x2
u1 = 8000 u2 = 3000 u3 = 5400 Z = 0 Bei dieser Ausgangslösung hat die Zielgröße den Wert Null; die Lösung ist im Sinne der Maximierung von Z aber eine „schlechte“ Lösung. c) Zur Verbesserung der Lösung soll nun ein Variablenaustausch erfolgen. Da x2 den größten Einfluss auf die Zielfunktion hat, wird x2 in die Basis aufgenommen (x2 hat den größten Einfluss auf die Zielfunktion, da der Deckungsbeitrag um 120 GE steigt, wenn der Wert von x2 um eine ME steigt. Bei x2 steigt der Deckungsbeitrag nur um 90 GE). Gegen welche Variable wird x2 getauscht? x1 = 0, u1 = 0 Versuch 1: x2 u1 : aus I folgt: x2: u1 = 8000 – 20x1 – 40x2 / - 8000 + 20x1 u1 – 8000 + 20x1 = - 40x2 - 8000 = - 40x2 / : (- 40) x2 = 200 aus II folgt: u2: u2 = 3000 – 15x1 – 10x2 u2 = 3000 – 10 * 200 u2 = 1000 aus III folgt: u3: u3 = 5400 – 30x1 – 10x2 u3 = 5400 – 10 * 200 u3 = 3400 x1 = 0, u2 = 0 Versuch 2: x2 u2 : aus II folgt: x2: u2 = 3000 – 15x1 – 10x2 / - 3000 + 15x1 u2 – 3000 + 15x1 = - 10x2 - 3000 = - 10x2 / : (- 10) x2 = 300
aus I folgt: u1: u1 = 8000 – 20x1 – 40x2 u1 = 8000 – 40 * 300 u1 = -4000 ( Widerspruch, da u1 < 0 !) ui ’ 0
x1 = 0, u3 = 0 Versuch 3: : x2 u3 : aus III folgt: x2: u3 = 5400 – 30x1 – 10x2 / -5400 + 30x1 u3 – 5400 + 30x1 = -10x2 -5400 = -10x2 / :(-10) x2 = 540 aus II folgt: u2: u2 = 3000 – 15x1 – 10x2 u2 = 3000 – 10 * 540 u2 = - 2400 ( Widerspruch, da u2 < 0 !) ui ’ 0
Die erste Gleichung stellt den Engpass dar, denn die „engste“ Einschränkung wird durch die erste Maschine verursacht. Dort ist x2 nur 200. Deshalb wird x2 gegen u1 getauscht. Die neuen Nichtbasisvariablen heißen x1 und u1. d) Umschreiben auf die neuen Basisvariablen: I u1 = 8000 – 20x1 – 40x2 / - 8000 + 20x1 u1 – 8000 + 20x1 = - 40x2 / : (- 40)
u1 x2 = - ———— + 200 – 0,5x1 40 u1 II u2 = 3000 – 15x1 – 10 (- ———— + 200 – 0,5x1) 40 1u1 u2 = 3000 - 15x1 - ——— - 2000 + 5x1 4 1 u2 = 1000 – 10x1 - ——— 4 u1 u2 = 1000 – 10x1 - ——— 4
III u3 = 5400 – 30x1 – 10x2 u1 u3 = 5400 – 30x1 - 10(- —— + 200 – 0,5x1) 40 u1 u3 = 5400 – 30x1 + —— - 2000 + 5x1 4 u1 u3 = 3400 - 25x1 + —— 4 u1 IV Z = 90x1 + 120(- —— + 200 – 0,5x1) 40 Z = 90x1 – 3u1 + 24000 – 60x1 Z = 30x1 – 3u1 + 24000 Nichtbasisvariable, also x1 und u1 sind 0 ! Z = 30 * 0 – 3 * 0 + 24000 Z =24000 Die Variable x1 in die Basis aufzunehmen vergrößert Z. Für den Engpass folgt aus der Gleichung I: x1 = 400, aus Gleichung II x1 = 100 und aus Gleichung III x1 = 136. Den Engpass stellt somit die zweite Gleichung dar. Deshalb wird x1 gegen u2 getauscht.
u1 II u2 = 1000 – 10x1 - ——— 4 u1 u2 – 1000 = - 10x1 - ——— 4 u1 u2 – 1000 + ——— = - 10x1 4 u2 u1 - ——— + 100 - ——— = x1
x1 in I, III und IV einsetzen
I u1 u2 u1 x2 = - ——— + 200 – 0,5 (- ——— + 100 - ——— ) 40 10 40 u1 x2 = - ——— + 200 + 0,05u2 – 50 + 0,0125 u1 40 u1 x2 = - ——— + 200 + 0,05u2 – 50 + 0,0125u1 40 x2 = - 0,0125u1 + 150 + 0,05u2
III u2 u1 u1 u3 = 3400 - 25(- ——— + 100 - ——— ) + ——— 10 40 4
u3 = 3400 + 2,5u2 – 2500 + 0,625u1 + 0,25u1
u3 = 900 + 2,5u2 + 0,875u1 IV u2 u1 Z = 30( - ——— + 100 - ———) – 3u1 + 24000
Z = - 3u2 + 3000 – 0,75u1 – 3u1 + 24000 Z = - 3u2 – 3,75u1 + 27000 Die Nichtbasisvariablen u1 und u2 sind Null, daraus folgt Z = 27000. Das ist die optimale Lösung, weil ein Austauschen der Basisvariablen x1, x2 und u3 gegen die Nichtbasisvariablen u1 und u2 keine Steigerung der Werte der Zielgröße nachsichzieht. Denn nimmt man u1 oder u2 als Basisvariablen, dann ginge der Deckungsbeitrag zurück. Der Deckungsbeitrag ist also mit 27000 GE maximal, wenn 100 ME von P1 und 150 ME von P2 hergestellt werden. Die dritte Maschine hat dann noch eine freie Kapazität von 900 bezogen auf ME, die Maschinen M1 und M2 sind ausgelastet. 5. Simplex – Tableau: Der oben beschriebene Lösungsweg lässt sich mit Hilfe des Simplex – Tableaus übersichtlicher darstellen. Für das bekannte Beispiel gilt das folgende Tableau:
*) Basisvariable x2 = 150 (150 ME von P2) x1 = 100 (100 ME von P1) u3 = 900 (die dritte Maschine hat noch eine freie Kapazität von 900 bezogen auf ME, die Maschinen M1 und M2 sind ausgelastet) Z = 27000 (max. Deckungsbeitrag) 5.1 Rechenregeln:
Dazu nimmt man alle positiven Koeffizienten der Pivot- Spalte und teilt die absoluten Glieder durch die Koeffizienten. Der kleinste Wert bestimmt den Engpass. Negative Koeffizienten und Nullen bleiben unberücksichtigt; kann kein Engpass bestimmt werden, so ist das Optimierungsproblem nicht lösbar. neu alt
durch das Pivot – Element. Das Pivot- Element ist das Element in der Pivot- Spalte und der Pivot- Zeile.
neu alt alt neu a i j = a i j - Si * Zj Zeile Spalte S = Pivot- Spalte neu Z = aus Pivot- Zeile hervorgegangene Zeile
Beispiele: neu a21 = 15 – 10 * 0,5 = 10 neu a22 = 10 – 10 * 1 = 0 neu a23 = 0 – 10 * 0,025 = - 0,25 neu a24 = 1 – 10 * 0 = 1 Quellenangaben – Literaturverzeichnis
H.- J. Bartsch Fachbuchverlag Leipzig, 1998
Cornelsen, 1998
|