Benutzer:Schafholt/Beispielrechnung Simplex-Verfahren

Beispielrechnung

Veranschaulichung des Beispiels (Erklärung siehe Text)

Anhand eines einfachen Beispiels zur Produktionsplanung mit zwei Variablen soll der Lösungsweg Schritt für Schritt gezeigt werden. In diesem einfachen Fall ist eine Optimallösung leicht zu finden. Reale Probleme können dagegen leicht aus mehreren Hunderttausend Variablen und Nebenbedingungen bestehen, so dass man ihnen meistens die Existenz einer Lösung oder den Wert einer Optimallösung nicht unmittelbar ansehen kann.

Eine Firma stelle 2 verschiedene Produkte her. Es stehen 3 Maschinen A, B, C zur Verfügung. Maschine A hat eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden, Maschine B von 150 Stunden und Maschine C von 180 Stunden. Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man 1 ME von Produkt 1, benötigt man dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde die Maschine B. 1 ME von Produkt 2 belegt nacheinander 2 Stunden Maschine A, 1 Stunde Maschine B und 3 Stunden Maschine C.

Daraus erhält man folgende Bedingungen:

${\begin{matrix}1\cdot x_{1}&+&2\cdot x_{2}&\leq &170&{\mbox{(Maschine A)}}\\[2pt]1\cdot x_{1}&+&1\cdot x_{2}&\leq &150&{\mbox{(Maschine B)}}\\[2pt]0\cdot x_{1}&+&3\cdot x_{2}&\leq &180&{\mbox{(Maschine C)}}\\[2pt]\end{matrix}}$

$x_{1}\geq 0,\ x_{2}\geq 0$

Die Firma möchte den Deckungsbeitrag $z\,$ maximieren:

$\max \;z=300\cdot x_{1}+500\cdot x_{2}$

$z\,$ ist daher der sogenannte Zielfunktionswert.

Eventuelle Fixkosten sind unabhängig von der Produktionsmenge und können daher einfach am Ende der Berechnung vom Gesamtdeckungsbeitrag abgezogen werden, um den Gewinn zu erhalten.

Überführung in Gleichungen

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt. Dazu führt man so genannte Schlupfvariablen $y_{1}\,$, $y_{2}\,$ und $y_{3}\,$ ein, welche die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen die Schlupfvariablen nicht negativ sein. Damit lässt sich das Problem so formulieren, dass man die Schlupfvariablen bezüglich der ursprünglichen Variablen freilegt. Ein derart genormtes Gleichungssystem heißt im Englischen dictionary (Benennung von V. Chvátal):

Maximiere die Zielfunktion $z\,$ unter den Nebenbedingungen:

${\begin{matrix}z&=&~~~~~~0&+~300\,x_{1}&+~500\,x_{2}\\[3pt]y_{1}&=&~~~170&-~~~~1\,x_{1}&-~~~~2\,x_{2}\\[2pt]y_{2}&=&~~~150&-~~~~1\,x_{1}&-~~~~1\,x_{2}\\[2pt]y_{3}&=&~~~180&+~~~~0\,x_{1}&-~~~~3\,x_{2}\end{matrix}}$

$x_{1}\geq 0,\ x_{2}\geq 0$

$y_{1}\geq 0,\ y_{2}\geq 0,\ y_{3}\geq 0$

Die obigen Gleichungen kann man in das vorher beschriebene Simplex-Tableau übertragen:

      -----------------------------
      |  x1     x2   | rechte Seite
  ---------------------------------
  -z  |  300   500  |      0
  ---------------------------------
  y1  |   1      2   |      170  = b1
  y2  |   1      1   |      150  = b2
  y3  |   0      3   |      180  = b3

In der Kopfzeile stehen die Nichtbasisvariablen $x_{1},\,x_{2}$ mit dem Wert 0, während die Basisvariablen $y_{i}\,$ in der ersten Spalte stehen. In der obersten Zeile – der Gleichung für die Zielfunktion – stehen die Zielfunktionskoeffizienten $c_{i}\,$, also 300 und 500. Auf der rechten Seite steht die aktuelle Basislösung, was in diesem Fall genau $b\,$ ist. In der obersten Zeile der rechten Seite steht das Negative des Zielfunktionswertes für die aktuelle Basislösung, im Beispiel also das Negative des Gesamtdeckungsbeitrag. Dieser ist momentan 0, da nichts produziert wird.

Bestimmung einer zulässigen Ausgangslösung (Phase I)

Da die konstanten Größen des obigen Gleichungssystems nichtnegativ sind, kann man die unabhängigen Variablen des Gleichungssystems (Basisvariablen) auf Null setzen und so eine triviale zulässige Lösung angeben, mit der direkt die Phase II gestartet werden kann:

$x_{1}=0,\ x_{2}=0\qquad y_{1}=170,\ y_{2}=150,\ y_{3}=180$

Die Variablen $y_{i}\,$ bilden eine zulässige Basis $B\,$, deren Basismatrix $A_{B}\,$ die Einheitsmatrix ist. Die zugehörige Basislösung ist also $A_{B}^{-1}b=b$. Diese Lösung entspricht dem Fall, dass nichts produziert wird ($x_{i}=0\,$). Die Restkapazität der Maschinen, die durch die Werte der $y_{i}\,$ angegeben wird, ist hier deren Gesamtkapazität (170, 150 und 180), da die Maschinen nicht genutzt werden.

Verbesserung der Lösung mittels einer Simplex-Iteration (Phase II)

Da die soeben berechnete Ausgangslösung unbefriedigend ist, wird nun in Phase II versucht, bessere zulässige Lösungen zu finden.

Auswahl einer Pivotspalte und -zeile

In einer Simplex-Iteration wird eine Basisvariable gegen eine der unabhängigen Variablen ausgetauscht. In Frage kommen Nichtbasisvariablen mit positivem Zielfunktionskoeffizienten, da deren Aufnahme in die Basis den Zielfunktionswert verbessern kann. Diese Variable soll so weit erhöht werden, bis eine oder mehrere der Basisvariablen auf 0 stoßen. Eine beliebige dieser Basisvariablen verlässt dann die Basis und wird gegen die Nichtbasisvariable ausgetauscht.

Variable $x_{1}\,$ hat den positiven Zielfunktionskoeffizienten 300; indem sie erhöht wird, lässt sich die Zielfunktion $z\,$ vergrößern; sie kommt also als basis-eintretende Pivotvariable in Frage. Solange $x_{1}\,$ die einzige erhöhte Nichtbasisvariable ist, soll diese Erhöhung ${\bar {x}}_{1}\,$ durch folgende Bedingungen eingeschränkt werden:

${\begin{matrix}0\leq {\bar {y}}_{1}=170-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{1}{\text{)}}\\[2pt]0\leq {\bar {y}}_{2}=150-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{2}{\text{)}}\\[2pt]\end{matrix}}$

In anderen Worten,

${\bar {x}}_{1}\leq {\frac {170}{1}},\quad {\bar {x}}_{1}\leq {\frac {150}{1}}$  oder  ${\bar {x}}_{1}\leq \min {\Bigl \{}{\frac {170}{1}},\ {\frac {150}{1}}{\Bigr \}}=\min\{170,150\}=150$

Die erste der Basisvariablen, die in diesem Fall auf Null stößt, erhält man über den Quotienten $150/1\,$ und ist $y_{2}\,$. Diese ist die Variable, die gegebenenfalls gegen $x_{1}\,$ ausgetauscht werden müsste. Der neue Wert der Zielfunktion wäre dann ${\bar {z}}=300\cdot (150/1)=45000$.

Auch Variable $x_{2}\,$ hat mit 500 einen positiven Zielfunktionskoeffizienten, kommt also ebenfalls als eintretende Nichtbasisvariable in Frage. Nach der obigen Vorgehensweise erhalten wir

${\begin{matrix}0\leq {\bar {y}}_{1}=170-2\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{1}{\text{)}}\\[2pt]0\leq {\bar {y}}_{2}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{2}{\text{)}}\\[2pt]0\leq {\bar {y}}_{3}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{3}{\text{)}}\\[2pt]\end{matrix}}$

und somit

${\bar {x}}_{2}\leq \min {\Bigl \{}{\frac {170}{2}},\ {\frac {150}{1}},\ {\frac {180}{3}}{\Bigr \}}=\min\{85,150,60\}=60$

Der minimale Quotient $(180/3)\,$ gehört zur Basisvariable $y_{3}\,$. Der neue Wert der Zielfunktion wäre ${\bar {z}}=500\cdot (180/3)=30000$.

Für den Zuwachs der Zielfunktion in diesem Schritt ist es also am günstigsten, den ersten Fall zu wählen und die unabhängige Variable $x_{1}\,$ anstelle der Basisvariablen $y_{2}\,$ freizulegen.

Durchführung eines Austauschschrittes

Mit dem Austauschschritt wird die Basisvariable $y_{2}\,$ gegen die Nichtbasisvariable $x_{1}\,$ ausgetauscht. Zuerst legen wir in der Gleichung für $y_{2}\,$ die unabhängige Unbekannte $x_{1}\,$ frei,

${\begin{matrix}y_{2}~=~150-1\,x_{1}-1\,x_{2}\qquad \qquad \qquad \qquad \qquad \\[3pt]\Longrightarrow \quad x_{1}~=~150-1\,y_{2}-1\,x_{2}\end{matrix}}$

und anschließend ersetzen wir $x_{1}\,$ in den restlichen Gleichungen für den so erhaltenen Ausdruck:

${\begin{matrix}z&~=~&~~~~0&+~300\,(150-1\,y_{2}-1\,x_{2})&+~500\,x_{2}\\[2pt]y_{1}&~=~&~170&-~~~~1\,(150-1\,y_{2}-1\,x_{2})&-~~~~2\,x_{2}\\[2pt]y_{3}&~=~&~180&+~~~~0\,(150-1\,y_{2}-1\,x_{2})&-~~~~3\,x_{2}\end{matrix}}$

Das führt zu den oben beschriebenen Verwandlungsregeln für das Simplex-Tableau nach dem Pivotelement $a_{21}=1$. Wenn $x_{1}\,$ die Zeile von $y_{2}\,$ besetzt und $y_{2}\,$ die Spalte von $x_{1}\,$, dann ist das neue Gleichungssystem

${\begin{matrix}z&=&45000&-~300\,y_{2}&+~200\,x_{2}\\[2pt]y_{1}&=&~~~~20&+~~~~1\,y_{2}&-~~~~1\,x_{2}\\[2pt]x_{1}&=&~~~150&-~~~~1\,y_{2}&-~~~~1\,x_{2}\\[2pt]y_{3}&=&~~~180&+~~~~0\,y_{2}&-~~~~3\,x_{2}\end{matrix}}$

Die Unbekannte $x_{1}\,$ ist in die Basis gerückt, die jetzt unabhängige Unbekannte $y_{2}\,$ ist eine Nichtbasisvariable und erscheint in der Kopfzeile.

Diese Lösung bedeutet: Es werden $150\,$ ME von Produkt 1 (Gleichung mit freigelegtem $x_{1}\,$) produziert. Von Produkt 2 wird nichts gefertigt ($x_{2}=0\,$ ist Nichtbasisvariable). Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 45.000 Euro. Maschine A steht $20\,$ Stunden pro Monat still (sie läuft nur 150 der 170 möglichen Stunden). Maschine B hat keine Leerlaufzeit. Maschine C steht $180\,$ Stunden still, das heißt, sie wird überhaupt nicht benötigt. Dies ergibt sich auch direkt aus der Aufgabenstellung: Maschine C wird nur bei der Herstellung von Produkt 2 benötigt. Da dieses nicht gefertigt wird, braucht man Maschine C noch nicht.

Das zum obigen Gleichungssystem gehörende neue Simplex-Tableau ist

      -----------------------------
      |  yB     x2   | rechte Seite
  ---------------------------------
  -z  |  -300   200  |      -45000
  ---------------------------------
  yA  |  -1      1   |       20  = b1
  x1  |   1      1   |      150  = b2
  yC  |   0      3   |      180  = b3

Die Einträge des neuen Simplex-Tableaus können anhand der oben angeführten Formeln errechnet werden.

Nochmalige Verbesserung der Lösung

Da die Zielfunktion im entstandenen Simplex-Tableau noch einen positiven Koeffizienten enthält, kann man die Lösung noch verbessern. Dies geschieht mittels einer weiteren Simplex-Iteration. Bei der Auswahl des Pivotelementes kommt nur die Unbekannte $x_{2}\,$ in Frage, da nur hier der Zielfunktionskoeffizient positiv ist. Die Basisvariable des Pivots ergibt sich aus

${\begin{matrix}0\leq {\bar {y}}_{1}=~20-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{1}{\text{)}}\\[2pt]0\leq {\bar {x}}_{1}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{1}{\text{)}}\\[2pt]0\leq {\bar {y}}_{3}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{3}{\text{)}}\\[2pt]\end{matrix}}$

und somit

${\bar {x}}_{2}\leq \min\{{\frac {20}{1}},\ {\frac {150}{1}},\ {\frac {180}{3}}\}=\min\{20,150,60\}=20$

Damit ist Zeile $y_{1}\,$ die einzige Basisunbekannte, die für einen Pivot in Frage kommt. Die Basisvariable $y_{1}\,$ wird gegen die Nichtbasisvariable $x_{2}\,$ ausgetauscht; das Pivotelement ist $1\,$. Mit den gleichen Umrechnungen wie oben erhält man als neues Gleichungssystem

${\begin{matrix}z&=&49000&-~100\,y_{2}&-~200\,y_{1}\\[2pt]x_{2}&=&~~~~20&+~~~~1\,y_{2}&-~~~~1\,y_{1}\\[2pt]x_{1}&=&~~~130&-~~~~2\,y_{2}&+~~~~1\,y_{1}\\[2pt]y_{3}&=&~~~120&-~~~~3\,y_{2}&+~~~~3\,y_{1}\end{matrix}}$

beziehungsweise ein neues Simplex-Tableau

      -----------------------------
      |  yB     yA   | rechte Seite
  ---------------------------------
  -z  | -100   -200  |   -49000
  ---------------------------------
  x2  |  -1      1   |       20 
  x1  |   2     -1   |      130 
  yC  |   3     -3   |      120

Da die Zielfunktion nun keine positiven Koeffizienten mehr enthält, ist eine optimale Lösung erreicht. Es werden $130\,$ ME von Produkt 1 und $20\,$ ME von Produkt 2 hergestellt. Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 49.000 Euro. Maschine A und Maschine B sind voll ausgelastet. Maschine C läuft 60 Stunden und hat daher noch eine ungenutzte Kapazität von $y_{3}=120\,$ Stunden.

Einträge in Bruchzahlform

Das obige Beispiel wurde in algebraischer Notation gelöst, indem man im Gleichungssystem die Basisvariablen bezüglich der restlichen, unabhängigen Variablen freilegt. Um Rundungsfehler zu vermeiden, kann man mit Bruchzahlen arbeiten und einen gemeinsamen Nenner für das gesamte Gleichungssystem wählen (dass dieser Nenner oben immer $1\,$ war, ist Zufall). Um in jedem Schritt den gemeinsamen Nenner für das Gesamtsystem zu finden, müssen wir die Einträge nicht zusätzlich analysieren. Falls das Startsystem ganzzahlig ist (was sich normalerweise durch Erweiterung erreichen lässt), gilt die Regel:

• Der Zähler des gewählten Pivotelements ist ein gemeinsamer Nenner für das darauffolgende System

Wenn wir die neuen Tableau-Einträge mit diesem gemeinsamen Nenner multiplizieren, erhalten wir stets ganzzahlige Zähler. Bei der Berechnung dieser Zähler für die neuen Tableau-Einträge wird dann ungeprüft durch den alten Nenner geteilt, wobei das Ergebnis ganzzahlig sein muss.

Als Beispiel für diese Vorgehensweise lösen wir dieselbe Aufgabe wie oben noch einmal mit Dantzigs Pivotauswahl; hierbei wird als eingehende Pivotvariable diejenige mit größtem Zielfunktionskoeffizienten gewählt:

${\begin{matrix}z&=&(&~~~~~~~0&+~300\,x_{1}&+~500\,x_{2}&)~/~1\\[2pt]y_{1}&=&(&~~~~170&-~~~~~\,x_{1}&-~~~~2\,x_{2}&)~/~1\\[2pt]y_{2}&=&(&~~~~150&-~~~~~\,x_{1}&-~~~~~\,x_{2}&)~/~1\\[2pt]y_{3}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~\mathbf {3\,x_{2}} &)~/~1\end{matrix}}$

Durch Erhöhung der unabhängigen Variable $x_{2}\,$ lässt sich die Zielfunktion $z\,$ vergrößern; die erste der Basisvariablen, die in diesem Fall auf Null stößt, ist $y_{3}\,$. Folglich kann man $x_{2}\,$ anstelle von $y_{3}\,$ freilegen und erhält folgendes System mit ${\bar {z}}=30000$:

${\begin{matrix}z&=&(&~90000&+~900\,x_{1}&-~500\,y_{3}&)~/~3\\[2pt]y_{1}&=&(&~~~~150&-~~~~\mathbf {3\,x_{1}} &+~~~~2\,y_{3}&)~/~3\\[2pt]y_{2}&=&(&~~~~270&-~~~~3\,x_{1}&+~~~~~\,y_{3}&)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~~\,y_{3}&)~/~3\end{matrix}}$

Wenn man die unabhängige Variable $x_{1}\,$ erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist $y_{1}\,$. Folglich legt man $x_{1}\,$ anstelle von $y_{1}\,$ frei und erhält folgendes System mit ${\bar {z}}=45000$:

${\begin{matrix}z&=&(&135000&-~900\,y_{1}&+~100\,y_{3}&)~/~3\\[2pt]x_{1}&=&(&~~~~150&-~~~~3\,y_{1}&+~~~~2\,y_{3}&)~/~3\\[2pt]y_{2}&=&(&~~~~120&+~~~~3\,y_{1}&-~~~~~\mathbf {\,y_{3}} &)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,y_{1}&-~~~~~\,y_{3}&)~/~3\end{matrix}}$

Wenn man die unabhängige Variable $y_{3}\,$ erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist $y_{2}\,$. Folglich legt man ${y_{3}\,}$ anstelle von $y_{2}\,$ frei und erhält folgendes System mit ${\bar {z}}=49000$:

${\begin{matrix}z&=&(&~49000&-~200\,y_{1}&-~100\,y_{2}&)~/~1\\[2pt]x_{1}&=&(&~~~~130&+~~~~~\,y_{1}&-~~~~2\,y_{2}&)~/~1\\[2pt]y_{3}&=&(&~~~~120&+~~~~3\,y_{1}&-~~~~3\,y_{2}&)~/~1\\[2pt]x_{2}&=&(&~~~~~20&-~~~~~\,y_{1}&+~~~~~\,y_{2}&)~/~1\end{matrix}}$

Die Zielfunktion hat Wert ${\bar {z}}=49000\,$ und lässt sich nicht mehr erhöhen; die Lösung ist wie oben ${\bar {x}}_{1}=130,\,{\bar {x}}_{2}=20$.  Wir beobachten nebenher, dass Dantzigs Pivotauswahl im Vergleich zur anfangs gewählten Alternative einen Schritt mehr gebraucht hat, um zur Lösung zu gelangen.