Der Simplex-Algorithmus

Der Simplex-Algorithmus

Der Simplex-Algorithmus ist ein Verfahren, was in der linearen Planungsrechnung verwendet werden kann, um ein optimales Produktionsprogramm anhand einer Produktionsfunktion aufzustellen. Hier wird der Algorithmus anhand eines Beispiels verdeutlicht, da die Erfahrung gezeigt hat, dass ein theoretisches Verständnis aufgrund der anfänglich scheinbar großen Schwierigkeit des Systems eher nach einem praktischen Verständnis möglich ist.

Unser Ausgangsproblem

$\textsc<Max>_<Z_0>&=&2x_1+x_2\\x_1+x_2&\leq&5\\-x_1+x_2&=&0\\6x_1+2x_2&=&21$

Zielfunktion und Schlupfvariablen

Als Erstes wird die Zielfunktion umgeformt, sowie Schlupfvariablen¹⁾ eingefügt. Der Grund dafür ist, dass zur Anwendung des Simplexalgorithmus das System in kanonischer Form vorliegen muss – durch die Schlupfvariablen , und werden aus den Ungleichungen Gleichungen.

$Z_0-2x_1-x_2&=&0\\x_1+x_2+x_3&=&5\\-x_1+x_2+x_4&=&0\\6x_1+2x_2+x_5&=&21$

Aufstellen des Ausgangstabelaus

Das Ausgangstabelau wird nach dem Schema Zielfunktion , Basis , Nebenbedingungen , Schlupfvariablen , Basislösung und Zielwert folgendermaßen aufgestellt:

$\begin<tabular><c\svc|ccccc|cc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $Z_F$ & $Z_F$ & $Z_F$ & $0$ & $0$ & $0$ & $Z_W$\\\hline $B_N$ & $0$ & $Z_N$ & $Z_N$ & $S$ & $S$ & $S$ & $B_L$ \\ $B_N$ & $0$ & $Z_N$ & $Z_N$ & $S$ & $S$ & $S$ & $B_L$ \\$B_N$ & $0$ & $Z_N$ & $Z_N$ & $S$ & $S$ & $S$ & $B_L$ \end<tabular>$

Im konkreten Fall führt dies zu unserem Ausgangstabelau wie folgt:

$\begin<tabular><c\svc\svccccc\svcc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $1$ & $-2$ & $-1$ & $0$ & $0$ & $0$ & $0$\\\hline $x_3$ & $0$ & $1$ & $1$ & $1$ & $0$ & $0$ & $5$ \\ $x_4$ & $0$ & $-1$ & $1$ & $0$ & $1$ & $0$ & $0$ \\ $x_5$ & $0$ & $6$ & $2$ & $0$ & $0$ & $1$ & $21$\end<tabular>$

Die zugehörige Basislösung lautet $\begin<pmatrix>\begin<array><ccccc>0&0&5&0&21\end<array>\end<pmatrix>$ .

Der Algorithmus

Der Algorithmus wird solange durchgeführt, wie in der Zielfunktionszeile (Zeile x_0 ) noch negative Werte stehen.

Basistausch/neue Basisspalte

Die neue Basisspalte wird die jenige, deren Wert der Kleinste in der Zielfunktionszeile ist – hier also x_1 . Die Aktuelle Basis ist übrigens x_3 , im ersten Schritt nämlich immer Teil der Schlupfvariablen.

Die Spalte, die aus der Basis auszuschließen ist, wird folgendermaßen ermittelt: Ergebnisvektor x_B durch Zielvektor x_1 komponentenweise teilen, negative Werte und eins nicht berücksichtigen, der kleinste Wert hat gewonnen, besser gesagt verloren, also geht es hier um diese Vektoren/Werte:

$\vec<x_B>=\begin<pmatrix>\begin<array><c> 5\\0\\21 \end<array>\end<pmatrix>~;~\vec<x_2>=\begin<pmatrix>\begin<array><c> 1\\-1\\6 \end<array>\end<pmatrix>$

Wie beschrieben teilen:

$5\div1&=&5\\0\div-1&=&0\\21\div6&=&3<,>5$

Da null wie gesagt nicht berücksichtigt wird, ist 3,5 der entscheidende Wert²⁾. Die Rechnung, mit der wir den Wert erhalten haben, steht in der Zeile x_5 , daher teilen wir diese Zeile im Tabelau komplett durch 6, also durch die Zahl, durch die wir die 3,5 erhalten haben – hier die veränderte Zeile (ganz unten) im Tabelau: (“ $x_5\div6$ “)

$\begin<tabular><c\svc\svccccc\svcc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $1$ & $-2$ & $-1$ & $0$ & $0$ & $0$ & $0$\\\hline $x_3$ & $0$ & $1$ & $1$ & $1$ & $0$ & $0$ & $5$ \\ $x_4$ & $0$ & $-1$ & $1$ & $0$ & $1$ & $0$ & $0$ \\ $x_5$ & $0$ & $6$ & $2$ & $0$ & $0$ & $1$ & $21$\end<tabular>\Rightarrow\begin<tabular><c\svc\svccccc\svcc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $1$ & $-2$ & $-1$ & $0$ & $0$ & $0$ & $0$\\\hline $x_3$ & $0$ & $1$ & $1$ & $1$ & $0$ & $0$ & $5$ \\ $x_4$ & $0$ & $-1$ & $1$ & $0$ & $1$ & $0$ & $0$ \\ $x_5$ & $0$ & $1$ & $\frac<1><3>$ & $0$ & $0$ & $\frac<1><6>$ & $\frac<7><2>$\end<tabular>$

Aufnahme der neuen Basisspalte in die Basis

Das Element der neuen Basisspalte ( x_3 ), was an der Stelle steht, wo bei der alten Basisspalte die 1 stand, wird neues Pivotelement. In unserem Tabelau hier in eckige Klammern eingefasst:

$\begin<tabular><c\svc\svccccc\svcc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $1$ & $-2$ & $-1$ & $0$ & $0$ & $0$ & $0$\\\hline $x_3$ & $0$ & $[1]$ & $1$ & $1$ & $0$ & $0$ & $5$ \\ $x_4$ & $0$ & $-1$ & $1$ & $0$ & $1$ & $0$ & $0$ \\ $x_5$ & $0$ & $1$ & $\frac<1><3>$ & $0$ & $0$ & $\frac<1><6>$ & $\frac<7><2>$\end<tabular>$

Jedes Element in der Zeile des Pivotelements, also jedes Element in der sogenannten „Pivotzeile“, wird durch das Pivotelement geteilt, hier also alles durch eins, was nichts verändert:

$x_1=1\div1=[1]\\x_2=1\div1&=&1\\x_3=1\div1&=&1\\x_4=0\div1&=&0\\x_5=0\div1&=&1\\x_B=5\div1&=&5$

Wichtig ist hier in der Tat, das Pivotelement auch durch sich selbst zu teilen, damit es zu 1 wird! Das ist ja die Vorraussetzung für eine Basisspalte.

Dementsprechend müssen jetzt die passenden Nullen mittels Gaußumformungen bzw. Pivot-Schritten erzeugt werden.

Pivot-Element bestimmen (siehe oben) & Basis tauschen (benennung)
Kehrwert des Pivot-Elements bilden
Alle Elemente der Pivotzeile durch das Pivotelement teilen
Alle Elemente der Pivotspalte durch das Pivotelement, jetzt mit negativem Vorzeichen, teilen
Dreiecksregel anwenden

$\begin<tabular><c\svc\svccccc\svcc>~ & $x_0$ & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_B$ \\\hline $x_0$ & $1$ & $0$ & $-^1$/$_3$ & $0$ & $0$ & $^1$/$_3$ & $7$\\\hline $x_3$ & $0$ & $0$ & $^2$/$_3$ & $1$ & $0$ & $-^1$/$_6$ & $^3$/$_2$ \\ $x_4$ & $0$ & $0$ & $^4$/$_3$ & $0$ & $1$ & $^1$/$_6$ & $^7$/$_2$ \\ $x_1$ & $0$ & $1$ & $^1$/$_3$ & $0$ & $0$ & $^1$/$_6$ & $^7$/$_2$\end<tabular>$

FIXME

Neuer Zielfunktionswert

¹⁾ Schlupfvariablen stellen die nicht ausgeschöpften Resourcen beziehungsweise den über den Mindestverbrauch hinausgehenden Verzehr dar. Sie leisten keinen Beitrag zur Zielfunktion.

²⁾ Falls alle Zahlen negativ sind, handelt es sich um eine nach oben unbeschränke Funktion.