====== 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 =====

{{http://apps.rkcsd.com/latex2png.php/%5Ctextsc%7BMax%7D_%7BZ_0%7D&=&2x_1+x_2%5C%5Cx_1+x_2&%5Cleq&5%5C%5C-x_1+x_2&=&0%5C%5C6x_1+2x_2&=&21.png?nolink|\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//((Schlupfvariablen stellen die nicht ausgeschöpften Resourcen beziehungsweise den über den Mindestverbrauch hinausgehenden Verzehr dar. Sie leisten keinen Beitrag zur Zielfunktion.)) eingefügt. Der Grund dafür ist, dass zur Anwendung des Simplexalgorithmus das System in //kanonischer Form// vorliegen muss -- **durch die Schlupfvariablen {{http://apps.rkcsd.com/latex2png.php/x_3.png?nolink|x_3}}, {{http://apps.rkcsd.com/latex2png.php/x_4.png?nolink|x_4}} und {{http://apps.rkcsd.com/latex2png.php/x_5.png?nolink|x_5}} werden aus den Ungleichungen Gleichungen**.

{{http://apps.rkcsd.com/latex2png.php/Z_0-2x_1-x_2&=&0%5C%5Cx_1+x_2+x_3&=&5%5C%5C-x_1+x_2+x_4&=&0%5C%5C6x_1+2x_2+x_5&=&21.png?nolink|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 {{http://apps.rkcsd.com/latex2png.php/Z_F.png?nolink|Z_F}}**, **Basis {{http://apps.rkcsd.com/latex2png.php/B_N.png?nolink|B_N}}**, **Nebenbedingungen {{http://apps.rkcsd.com/latex2png.php/Z_N.png?nolink|Z_N}}**, **Schlupfvariablen {{http://apps.rkcsd.com/latex2png.php/S.png?nolink|S}}**, **Basislösung {{http://apps.rkcsd.com/latex2png.php/B_L.png?nolink|B_L}}** und **Zielwert {{http://apps.rkcsd.com/latex2png.php/Z_W.png?nolink|Z_W}}** folgendermaßen aufgestellt:

{{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Btabular%7D%7Bc%5Csvc\svccccc\svcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$Z_F$%20&%20$Z_F$%20&%20$Z_F$%20&%20$0$%20&%20$0$%20&%20$0$%20&%20$Z_W$%5C%5C%5Chline%20$B_N$%20&%20$0$%20&%20$Z_N$%20&%20$Z_N$%20&%20$S$%20&%20$S$%20&%20$S$%20&%20$B_L$%20%5C%5C%20$B_N$%20&%20$0$%20&%20$Z_N$%20&%20$Z_N$%20&%20$S$%20&%20$S$%20&%20$S$%20&%20$B_L$%20%5C%5C$B_N$%20&%20$0$%20&%20$Z_N$%20&%20$Z_N$%20&%20$S$%20&%20$S$%20&%20$S$%20&%20$B_L$%20%5Cend%7Btabular%7D.png?nolink|\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:

{{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Btabular%7D%7Bc\svc\svccccc\svcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$1$%20&%20$-2$%20&%20$-1$%20&%20$0$%20&%20$0$%20&%20$0$%20&%20$0$%5C%5C%5Chline%20$x_3$%20&%20$0$%20&%20$1$%20&%20$1$%20&%20$1$%20&%20$0$%20&%20$0$%20&%20$5$%20%5C%5C%20$x_4$%20&%20$0$%20&%20$-1$%20&%20$1$%20&%20$0$%20&%20$1$%20&%20$0$%20&%20$0$%20%5C%5C%20$x_5$%20&%20$0$%20&%20$6$%20&%20$2$%20&%20$0$%20&%20$0$%20&%20$1$%20&%20$21$%5Cend%7Btabular%7D.png?nolink|\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 {{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Bpmatrix%7D%5Cbegin%7Barray%7D%7Bccccc%7D0&0&5&0&21%5Cend%7Barray%7D%5Cend%7Bpmatrix%7D.png?nolink|\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 {{http://apps.rkcsd.com/latex2png.php/x_0.png?nolink|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 {{http://apps.rkcsd.com/latex2png.php/x_1.png?nolink|x_1}}. Die Aktuelle Basis ist übrigens {{http://apps.rkcsd.com/latex2png.php/x_3.png?nolink|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 {{http://apps.rkcsd.com/latex2png.php/x_B.png?nolink|x_B}} durch Zielvektor {{http://apps.rkcsd.com/latex2png.php/x_1.png?nolink|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: 

{{http://apps.rkcsd.com/latex2png.php/%5Cvec%7Bx_B%7D=%5Cbegin%7Bpmatrix%7D%5Cbegin%7Barray%7D%7Bc%7D%205%5C%5C0%5C%5C21%20%5Cend%7Barray%7D%5Cend%7Bpmatrix%7D~;~%5Cvec%7Bx_2%7D=%5Cbegin%7Bpmatrix%7D%5Cbegin%7Barray%7D%7Bc%7D%201%5C%5C-1%5C%5C6%20%5Cend%7Barray%7D%5Cend%7Bpmatrix%7D.png?nolink|\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:

{{http://apps.rkcsd.com/latex2png.php/5%5Cdiv1&=&5%5C%5C0%5Cdiv-1&=&0%5C%5C21%5Cdiv6&=&3%7B,%7D5.png?nolink|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((Falls alle Zahlen negativ sind, handelt es sich um eine nach oben unbeschränke Funktion.)). Die Rechnung, mit der wir den Wert erhalten haben, steht in der Zeile {{http://apps.rkcsd.com/latex2png.php/x_5.png?nolink|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: ("{{http://apps.rkcsd.com/latex2png.php/x_5%5Cdiv6.png?nolink|x_5\div6}}")

{{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Btabular%7D%7Bc%5Csvc%5Csvccccc%5Csvcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$1$%20&%20$-2$%20&%20$-1$%20&%20$0$%20&%20$0$%20&%20$0$%20&%20$0$%5C%5C%5Chline%20$x_3$%20&%20$0$%20&%20$1$%20&%20$1$%20&%20$1$%20&%20$0$%20&%20$0$%20&%20$5$%20%5C%5C%20$x_4$%20&%20$0$%20&%20$-1$%20&%20$1$%20&%20$0$%20&%20$1$%20&%20$0$%20&%20$0$%20%5C%5C%20$x_5$%20&%20$0$%20&%20$6$%20&%20$2$%20&%20$0$%20&%20$0$%20&%20$1$%20&%20$21$%5Cend%7Btabular%7D%5CRightarrow%5Cbegin%7Btabular%7D%7Bc%5Csvc%5Csvccccc%5Csvcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$1$%20&%20$-2$%20&%20$-1$%20&%20$0$%20&%20$0$%20&%20$0$%20&%20$0$%5C%5C%5Chline%20$x_3$%20&%20$0$%20&%20$1$%20&%20$1$%20&%20$1$%20&%20$0$%20&%20$0$%20&%20$5$%20%5C%5C%20$x_4$%20&%20$0$%20&%20$-1$%20&%20$1$%20&%20$0$%20&%20$1$%20&%20$0$%20&%20$0$%20%5C%5C%20$x_5$%20&%20$0$%20&%20$1$%20&%20$%5Cfrac%7B1%7D%7B3%7D$%20&%20$0$%20&%20$0$%20&%20$%5Cfrac%7B1%7D%7B6%7D$%20&%20$%5Cfrac%7B7%7D%7B2%7D$%5Cend%7Btabular%7D.png?nolink|\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 Basis__spalte__ ({{http://apps.rkcsd.com/latex2png.php/x_3.png?nolink|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:

{{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Btabular%7D%7Bc%5Csvc%5Csvccccc%5Csvcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$1$%20&%20$-2$%20&%20$-1$%20&%20$0$%20&%20$0$%20&%20$0$%20&%20$0$%5C%5C%5Chline%20$x_3$%20&%20$0$%20&%20$%5B1%5D$%20&%20$1$%20&%20$1$%20&%20$0$%20&%20$0$%20&%20$5$%20%5C%5C%20$x_4$%20&%20$0$%20&%20$-1$%20&%20$1$%20&%20$0$%20&%20$1$%20&%20$0$%20&%20$0$%20%5C%5C%20$x_5$%20&%20$0$%20&%20$1$%20&%20$%5Cfrac%7B1%7D%7B3%7D$%20&%20$0$%20&%20$0$%20&%20$%5Cfrac%7B1%7D%7B6%7D$%20&%20$%5Cfrac%7B7%7D%7B2%7D$%5Cend%7Btabular%7D.png?nolink|\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:

{{http://apps.rkcsd.com/latex2png.php/x_1=1%5Cdiv1&=&%5B1%5D%5C%5Cx_2=1%5Cdiv1&=&1%5C%5Cx_3=1%5Cdiv1&=&1%5C%5Cx_4=0%5Cdiv1&=&0%5C%5Cx_5=0%5Cdiv1&=&1%5C%5Cx_B=5%5Cdiv1&=&5.png?nolink|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

{{http://apps.rkcsd.com/latex2png.php/%5Cbegin%7Btabular%7D%7Bc%5Csvc%5Csvccccc%5Csvcc%7D~%20&%20$x_0$%20&%20$x_1$%20&%20$x_2$%20&%20$x_3$%20&%20$x_4$%20&%20$x_5$%20&%20$x_B$%20%5C%5C%5Chline%20$x_0$%20&%20$1$%20&%20$0$%20&%20$-%5E1$/$_3$%20&%20$0$%20&%20$0$%20&%20$%5E1$/$_3$%20&%20$7$%5C%5C%5Chline%20$x_3$%20&%20$0$%20&%20$0$%20&%20$%5E2$/$_3$%20&%20$1$%20&%20$0$%20&%20$-%5E1$/$_6$%20&%20$%5E3$/$_2$%20%5C%5C%20$x_4$%20&%20$0$%20&%20$0$%20&%20$%5E4$/$_3$%20&%20$0$%20&%20$1$%20&%20$%5E1$/$_6$%20&%20$%5E7$/$_2$%20%5C%5C%20$x_1$%20&%20$0$%20&%20$1$%20&%20$%5E1$/$_3$%20&%20$0$%20&%20$0$%20&%20$%5E1$/$_6$%20&%20$%5E7$/$_2$%5Cend%7Btabular%7D.png|\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 ====