Einführung in den Simplex-Algorithmus

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

Einführung

Die Lineare Planungsrechnung ist ein wichtiges, sehr häufig verwendetes Teilgebiet des Operations Research.

Sie geht hauptsächlich auf George B. Danzig zurück und wurde von ihm für die Planung der Aufgaben der amerikanischen Luftwaffe in den 40er Jahren entwickelt. Erst später wurde versucht, diese Methoden für die Unternehmungsplanung einzusetzen und man erkannte, dass hier viele Probleme mit dieser Lösungsmethode bearbeitet werden können. Für die Praxis wurden sie aber erst interessant und anwendbar, als effiziente Rechenanlagen entwickelt wurden. Wichtige Entwicklungen auf diesem Gebiet wurden auch von H. Müller-Merbach gemacht.

Modelle der Linearen Planrechnung bestehen nur aus linearen Gleichungen; einer linearen Zielfunktion, alle anderen Gleichungen sind Restriktionen. Die Simplex Methode ist das meist verwendete Verfahren zur Lösung linearer Optimierungsmodelle.

Beispiel
Die Simplex Methode zur Bestimmung des optimalen Produktionsprogramms

Eine Unternehmung stellt 2 Produkte her: A, B
Produkt A bringt einen Erlös von 2000 GE (Geldeinheiten) pro ME (Mengeneinheit) und verursacht direkte Kosten von 1400 GE pro ME.
Produkt B bringt einen Erlös von 6000 GE pro Mengeneinheit und verursacht direkte Kosten von 5000 GE pro Mengeneinheit.
Der Unternehmung entstehen durch die Produktion monatlich Fixkosten in Höhe von 72000 GE.

Zur Produktion stehen drei Maschinen zur Verfügung: X, Y, Z

Die maximalen Produktionsmengen sind durch die Maximalkapazitäten dieser Maschinen begrenzt. Maschine X hat eine monatliche Maximalkapazität von 340 Fertigungsstunden pro Monat, Maschine Y eine Kapazität von 300 Stunden pro Monat und Maschine Z eine Kapazität von 360 Stunden pro Monat.
Produkt A belegt die Maschinen X und Y jeweils für zwei Stunden je Mengeneinheit. Produkt B belegt Maschine X für vier, Maschine Y für zwei und Maschine Z für sechs Stunden je Mengeneinheit.


mathematische Formulierung

Um die Lösung dieses Problems mit der Simplex-Methode zu bestimmen, muss es durch lineare Ungleichungen bzw. Gleichungen beschrieben werden. Jedes Problem lässt sich durch eine Zielfunktion, beliebig viele Restriktionen und Nichtnegativitätsbedingungen beschreiben. Hierbei sind xj die Produktionsmengen, ej die Erlöse, kj die Kosten, kf die Fixkosten, cj die Deckungsbeiträge, aij die benötigten Kapazitäten, bi die Maximalkapazitäten und yi die Schlupfvariablen.

Zielfunktion:

Max DB = ∑j (( ej– kj ) xj ) - kf = ∑j (cj xj) - kf

Die Zielfunktion beschreibt das Optimierungsziel, in diesem Fall die Maximierung des Deckungsbeitrages (möglich z.B. auch Minimierung der Kosten), die sich aus den Deckungsbeiträgen der beiden Produkte multipliziert mit den Produktionsmengen und den Fixkosten berechnen lässt.

Restriktionen:

j aij xj ≤ bi
bzw yi + ∑j aij xj= bi

Durch die Restriktionen werden die Begrenzungen des Modells ausgedrückt, die bei der Lösung eingehalten werden müssen. Die genutzte Kapazität einer Maschine, ausgedrückt durch das Produkt von benötigter Kapazität pro Mengeneinheit und Produktionsmenge muss kleiner sein als die Maximalkapazität.
Da es sehr umständlich ist mit Ungleichungen zu rechnen, werden diese in Gleichungen überführt. Dies geschieht durch die Einführung der Schlupfvariablen, die die Leerkapazitäten der Maschinen beschreiben. Die Summe aus Leerkapazität und genutzter Kapazität einer Maschine sind dann gleich der Maximalkapazität.

Nichtnegativitätsbedingungen:

xj ≥ 0
yi ≥ 0

Da es keine Mengen kleiner Null gibt, muss die Produktionsmenge der Güter größer Null sein. Auch eine Restkapazität kleiner Null ist nicht möglich.


mathematische Formulierung des Beispiels

Eine Unternehmung stellt 2 Produkte her: A, B
Produkt A bringt einen Erlös von 2000 GE (Geldeinheiten) pro ME (Mengeneinheit) und verursacht direkte Kosten von 1400 GE pro ME.
Produkt B bringt einen Erlös von 6000 GE pro Mengeneinheit und verursacht direkte Kosten von 5000 GE pro Mengeneinheit.
Der Unternehmung entstehen durch die Produktion monatlich Fixkosten in Höhe von 72000 GE.

(∑j ( ej – kj)xj) = (2000 GE – 1400 GE) xA + (6000 GE - 5000 GE) xB
= 600 xA + 1000 xB = 72000

Zur Produktion stehen drei Maschinen zur Verfügung: X, Y, Z

Die maximalen Produktionsmengen sind durch die Maximalkapazitäten dieser Maschinen begrenzt. Maschine X hat eine monatliche Maximalkapazität von 340 Fertigungsstunden pro Monat, Maschine Y eine Kapazität von 300 Stunden pro Monat und Maschine Z eine Kapazität von 360 Stunden pro Monat.
Produkt A belegt die Maschinen X und Y jeweils für zwei Stunde je Mengeneinheit. Produkt B belegt Maschine X für vier, Maschine Y für zwei und Maschine Z für sechs Stunden je Mengeneinheit.

2xA + 4xB ≤ 340
bzw. y1 + 2xA + 4xB = 340
2xA + 2xB ≤ 300
bzw. y2 + 2xA + 2xB = 300
6xB ≤ 360
bzw. y3 + 6xB = 360


graphische Lösung

Zweidimensionale Probleme (zwei Produkte) lassen sich graphisch in einem Koordinatensystem lösen, bei dem man auf der Abszisse xA und auf der Ordinate xB aufträgt.

Zum Einzeichnen der Geraden ist es hilfreich, jeweils eine der Variablen der Ungleichungen gleich Null zu setzen.
Beispiel: 2xA + 4xB ≤ 340

xA = 0

4 xB ≤ 340
xB ≤ 85


xB = 0

2 xA≤ 340
xA≤ 170

Die errechneten Werte für xA und xB trägt man nun auf der Abszisse bzw. der Ordinate ab. Mit den anderen Ungleichungen verfährt man auf die gleiche Weise und erhält somit folgendes Schaubild:


Bild1.jpg
Abb. 1: graphische Darstellung der Restriktionen


Die effizienten Lösungen liegen auf dem Rand des Lösungsraumes in einem der Schnittpunkte der Geraden oder in einem der Schnittpunkte der Geraden mit den Koordinatenachsen, da alle anderen Lösungen von diesen dominiert werden. Um die optimale Lösung, d.h. die Lösung mit maximalem Deckungsbeitrag, zu bestimmen trägt man die Zielfunktion in die Grafik ein und verschiebt sie so lange parallel, bis sie den Rand des Lösungsraumes in einem Punkt tangiert. Diese parallelen Geraden werden auch als Iso-Gewinnlinien, also Linien gleichen Gewinns, bezeichnet.
Die Zielfunktion lässt sich nur für vorgegebene Werte einzeichnen. Man wählt zu Beginn einen festen Wert für den Deckungsbeitrag, zeichnet die Gerade für diesen und verschiebt sie dann parallel, bis man den maximalen Wert erhält.

Im Beispiel lautete die Zielfunktion

Max DB = 600 xA + 1000 xB = 72000

Wählt man einen Deckungsbeitrag von 18000 GE erhält man die Gleichung

600 xA + 1000 xB = 90000

Diese kann nun in bekannter Weise in die Grafik eingetragen werden.


Bild2.jpg
Abb. 2: graphische Lösung des Problems


Die Isogewinnlinie bei einem Gewinn von 26000 GE tangiert den Lösungsraum im Punkt (130, 20) und markiert somit das Gewinnmaximum.

Interpretation:
Bei einer Produktion von 130 A und 20 B erzielt die Unternehmung ihren maximalen Gewinn von 26000 GE.

Alle Isogewinnlinien mit niedrigerem Niveau werden von der mit Niveau 26000 GE dominiert, alle mit höherem Niveau berühren den Lösungsraum nicht mehr und sind somit uninteressant.

Lösung mit dem Simplex-Algorithmus (Phase 2)

Um die Lösung mit dem Simplex-Algorithmus zu bestimmen, müssen die Gleichungen in ein Simplex-Tableau überführt werden.

Simplex-Tableaus sind folgendermaßen aufgebaut:


Bild3.jpg
Abb. 3: Aufbau Simplex-Tableau


Terminologie

Strukturvariablen: xj
Schlupfvariablen: yi
Dualwerte:

Zielfunktionskoeffizienten, cj

Primalwerte:

Elemente der rechten Seite, bi


Kurzbeschreibung des Algorithmus:

  1. Auswahl der Pivot-Spalte:
    Wahl der zu transformierenden NBV nach
    • STEEPEST-UNIT-ASCENT: Spalte mit absolut größtem negativen Zielfunktionskoeffizient (ZFK)
    • GREATEST-CHANGE: Spalte mit absolut größtem Produkt von negativem ZFK und kleinstem positiven Quotienten aus rechter Seite und dem Element der entsprechenden Spalte
  2. Auswahl der Pivot-Zeile: Wahl der Zeile mit dem kleinsten positiven Quotienten aus rechter Seite und Element der Pivot-Spalte
  3. Pivot-Element: Schnittpunkt von Pivot-Spalte und Pivot-Zeile
  4. Tausch von Nicht-Basis-Variable und Basis-Variable
  5. Umrechnung des Simplex-Tableaus nach den Rechenregeln
  6. Weiter mit 1., falls Lösung nicht optimal.


Rechenregeln für Simplex-Tableaus:
Pivot-Element: ars* = 1/ars
Pivot-Zeile: arj* = arj/ars
Pivot-Spalte: ais* = - ais/ars
Restliche Elemente: aij* = aij - arj*ais/ars =aij - ais arj*

Variablen ohne Stern bezeichnen die alten Matrixelemente vor der Umrechung, Variablen mit Stern die Elemente nach der Umrechnung.

Für das Beispiel ergibt sich folgendes Simplex-Tableau:


Bild4.jpg
Abb. 4: Ausgangslösung


Das angegebene Simplex-Tableau gibt die mathematische Formulierung des Beispiels wieder. So steht die zweite Zeile zum Beispiel für y1 + 2x1 + 4x2 = 340.

Auswahl der Pivot-Spalte nach Steepest-Unit-Ascent

Nach Steepest-Unit-Ascent ist die Spalte mit dem absolut größten negativen Zielfunktionskoeffizienten die zu wählende Pivot-Spalte. Durch diese Art der Auswahl kommt diejenige Nichtbasisvariable in die Basis, die pro Einheit den größten Gewinnzuwachs zulässt; im Beispiel die Spalte x2 mit –1000. Die Pivot-Zeile ist die Zeile mit dem kleinsten nicht negativen Quotienten der Elemente der rechten Seite und den Elementen der Pivot-Spalte. Für das Beispiel betragen die Quotienten für die erste Zeile 340/4 = 85, für die zweite Zeile 300/2 = 150 und für die dritte Zeile 360/6 = 60. Die Pivot-Zeile ist also die dritte Zeile. Das Pivot-Element ist das Element im Schnittpunkt von Pivot-Zeile und Pivot-Spalte.


Bild5.jpg
Abb. 5: Bestimmung des Pivot-Elements


Als erstes vertauscht man die Nicht-Basis-Variable und die Basis-Variable des Pivot-Elements. Im Beispiel also xB gegen y3.

Das neue Pivot-Element ist der Kehrwert des alten Elements, also 1/6. Die neue Pivot-Spalte errechnet sich aus altem Spaltenelement geteilt durch das Pivot-Element mit getauschtem Vorzeichen. In der zweiten Zeile also –2/6=-1/3, in der ersten Zeile –4/6=-2/3, in der Zeile der Zielfunktion –1000/6=-500/3. Die neue Pivot-Zeile errechnet sich aus altem Zeilenelement geteilt durch das Pivot-Element. In der ersten Spalte also 0/6=0, in der letzten Spalte (Rechte Seite) 360/6=60.

Damit ergibt sich soweit für das neue Tableau:


Bild6.jpg
Abb. 6: Iteration 1.1


Im nächsten Schritt berechnet man die restlichen Elemente über altes Element minus altes Spaltenelement mal neues Zeilenelement. Dazu ist es hilfreich, diese noch mal an den Rand des Tableaus zu schreiben (Alternativ kann man natürlich die restlichen Elemente über die Formel aij - arj*ais/ars berechnen. Dies hat den Vorteil, dass alle Elemente, die zur Berechnung benötigt werden, in einem Tableau stehenDer nachteil ist, dass die Formel komplizierter wird):


Bild7.jpg
Abb. 7: Iteration 1.2


Für die erste Spalte und die Zielfunktionszeile berechnet sich der neue Wert folgendermaßen: -600-(-1000*0)=-600. Für die letzte Spalte (Rechte Seite) und die Zielfunktionszeile gilt: -72000-(-1000*60)=-12000 Für die erste Zeile und die erste Spalte gilt: 2-(0*4)=2 ... Das Prinzip dürfte somit klar sein. Man verfährt mit allen anderen Elementen entsprechend.

Somit befindet man sich am Ende der ersten Iteration. Da das Tableau noch einen negativen Zielfunktionskoeffizienten enthält, hat man die Optimallösung noch nicht gefunden und beginnt wieder mit Schritt 1 der Simplex-Iteration, der Bestimmung der Pivot-Spalte, der Pivot-Zeile und somit des Pivot-Elements. Die Umrechnung wird analog wie zur oben Beschriebenen durchgeführt.

Es ergeben sich dann folgende Tableaus:


Bild8.jpg
Abb. 8: Iterationen 2 und 3


Dieses Tableau stellt die Optimallösung dar, was man an den positiven Vorzeichen der Zielfunktionskoeffizienten erkennt. Außerdem ist die Lösung zulässig, da die Werte der rechten Seite ebenfalls ein positives Vorzeichen haben. Die Optimallösung lässt sich folgendermaßen interpretieren: Die Basisvariablen nehmen die Werte z = 26000, xA= 130, xB = 20 und y3 = 240 an. Dies bedeutet, dass 130 ME von Produkt A und 20 ME von Produkt B hergestellt werden. Mit diesem Produktionsprogramm wird der maximale Deckungsbeitrag von 26000 GE erzielt. Maschine 3 hat eine Restkapazität von 240 Stunden, wird also nicht voll ausgelastet. Die Nichtbasisvariablen y1 und y2 nehmen den Wert Null an. Die Maschinen 1 und 2 werden also voll ausgelastet und stellen somit die Engpassrestriktionen dar.

Auswahl der Pivot-Spalte nach Greatest-Change

Nach Greatest-Change ist die Spalte mit absolut größtem Produkt von negativem ZFK und kleinstem positiven Quotienten aus rechter Seite und dem Element der entsprechenden Spalte die zu wählende Pivot-Spalte. Durch diese Art der Auswahl kommt diejenige Nichtbasisvariable in die Basis, die den größten Gewinnzuwachs verursacht.


Bild9.jpg
Abb. 9: Bestimmung des Pivot-Elements


Zur Bestimmung der Pivot-Spalte bestimmt man für jedes Element den Quotienten aus rechter Seite und zugehörigem Zeilenelement. Also für die erste Zeile und die erste Spalte 340/2 = 170; für die erste Zeile und die zweite Spalte 340/4 =85; für die zweite Zeile und die erste Spalte 300/2 = 150 usw. Die entsprechenden Werte sind als Hochzahlen im Tableau angegeben. Nun wird für jede Spalte das Produkt aus kleinster „Hochzahl“ und Zielfunktionskoeffizient gebildet und die Spalte mit absolut größtem Produkt als Pivot-Spalte gewählt. Für die erste Spalte: 150*l-600l = 90000; für die zweite Spalte: 60*l-1000l = 60000. Man wählt also die erste Spalte und vergrößert somit den Gewinn auf 18000 GE. Als Pivot-Zeile wird wie bekannt die Zeile mit dem kleinsten nicht negativen Quotienten der Elemente der rechten Seite und den Elementen der Pivot-Spalte gewählt, im Beispiel also die 2. Zeile. Das Pivot-Element befindet sich also im Schnittpunkt der ersten Spalte mit der zweiten Zeile. Die Umrechnung erfolgt nun wie oben für Steepest-Unit-Ascent beschrieben. Es ergeben sich folgende Tableaus:


Bild10.jpg
Abb. 10: Iteration 1


Bild11.jpg
Abb. 11: Iteration 2


Bei diesem Tableau handelt es sich um die Optimallösung. Mit Greatest-Change wird diese also viel schneller erreicht, was bei den meisten Problemstellungen der Fall ist. Die Interpretation des Tableaus ist die gleiche wie die für die Optimallösung nach Steepest-Unit-Ascent.

Applet

Wenn Sie sich eingehender mit dem Simplex-Algorithmus auseinandersetzen wollen, könnn Sie dies anhand eines Applets, das die Lösung weiterer Beispiele vorführt und erklärt oder anhand eines Tutorials der Universität Melbourne.

Literatur

Müller-Merbach (1973): Operations Research, Kapitel 4.1 - 4.2.7


Vorlesung/Lecture

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.


Simplex-Algorithmus (Deutsch)

Simplex-Algorithmus (English)