Beispiel: Revidierter Simplex-Algorithmus

Das Optimierungsproblem aus dem Abschnitt Beispiel: Vielzahl an beschränkten Variablen, welches mit dem Algorithmus für die oberen Schranken gelöst worden ist, kann auch einfach und schnell mit dem revidierten Simplexalgorithmus gelöst werden. 

Gegeben sei das folgende Optimierungsproblem:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 \le 80$

$2x_1 + x_2 + x_3           \le 60$

$x_1 \le 20$

$x_2 \le 30$

$x_3 \le 10$

$x_4 \le 5$

$x_1, x_2, x_3, x_4 \ge 0$

Die Anzahl der Nebenbedingungen ist größer als die Anzahl der Variablen. Der primale Simplexalgorithmus kann hier natürlich auch angewandt werden, allerdings würde die Bestimmung der optimalen Lösung sehr rechenaufwendig sein. Mittels des Algorithmus der oberen Schranken ist das Problem bereits im oben genannten Abschnitt bestimmt worden. Es soll nun der revidierte Simplex-Algorithmus angewandt werden, um das Problem zu lösen. 

Das Problem wird zunächst auf die Normalform gebracht, indem die Schlupfvariablen eingefügt werden:

$f(x_1, x_2, x_3, x_4) = 4x_1 + 6x_2 + 3x_3 + x_4$   $\rightarrow$  max!

u.d.N.

$x_1 + 2x_2 + 4x_3 + x_4 + x_5                 \le 80$

$2x_1 + x_2 + x_3                             + x_6        \le 60$

$x_1 + x_7                                              \le 20$

$x_2          + x_8                                     \le 30$

$x_3                   + x_9                            \le 10$

$x_4                             + x_{10}                 \le 5$

$x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9, x_{10} \ge 0$

Vorgehensweise revidierte Simplexmethode

Bevor mit der Berechnung begonnen wird, werden die Koeffizienten in Matrizen geschrieben und die Basis- und Nichtbasisvariablen wie folgt festgelegt:

$c^T = (4, 6, 3, 1, 0, 0, 0, 0, 0, 0)$

$A = \begin{bmatrix} 1 & 2 & 4 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$ 

$b =  \begin{pmatrix} 80 \\ 60 \\ 20 \\ 30 \\ 10 \\ 5 \end{pmatrix}$

Es werden ebenfalls die Schlupvariablen in den Matrizen mitberücksichtigt. In die Zielfunktion gehen diese mit dem Wert null ein, weshalb dort für alle 6 Schlupfvariablen am Ende eine Null steht.

Es wird nun die Matrix $B$ (nur Werte der Nebenbedingungen der Basisvariablen $x_5$ bis $x_{10}$ plus Einheitsvektor) aufgestellt:

$B = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$ 

Zu Beginn sind die Basisvariablen die Schlupfvariablen $x_5$ bis $x_{10}$. Es werden alle Werte der Nebenbedingungen für die Basisvariablen, ohne die rechte Seite berücksichtigt. Die Zielfunktionswerte für die Basisvariablen werden in die letzte Zeile der Matrix geschrieben. Für die Basisvariablen sind die Zielfunktionswerte alle Null. Außerdem wird noch ein Einheitsvektor (mit der $1$ in der letzten Zeile) berücksichtigt.

Die Matrix $N$ (nur Werte der Nichtbasisvariablen) wird ebenfalls benötigt:

$N = \begin{bmatrix} 1 & 2 & 4 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -4 & -6 & -3 & -1 \end{bmatrix}$ 

Zu Beginn sind die Nichtbasisvariablen die Variablen der Zielfunktion $x_1$, $x_2$, $x_3$ und $x_4. Es werden alle Werte der Nebenbedingungen für die Nichtbasisvariablen, ohne die rechte Seite berücksichtigt. Außerdem in der letzten Zeile die Zielfunktionswerte für die Nichtbasisvariablen, aber mit umgekehrten Vorzeichen.

1. Iteration:

1. Schritt: Auswahl der Pivotspalte.

Bestimmung der Pivotspalte $a_s$, indem die Zielfunktion der Inversen von $B$ mit der Matrix $N$ mulipliziert wird.

Es muss also zunächst die Inverse Matrix $B^{-1}$ bestimmt werden:

$B^{-1} = B = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}  = I$

Da die Matrix $B$ der Einheitsmatrix $I$ entspricht, ist diese zu Beginn gleich der Inversen.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = ( 0, 0, 0, 0, 0, 0, 1) \cdot \begin{bmatrix} 1 & 2 & 4 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -4 & -6 & -3 & -1 \end{bmatrix} = (-4, -6, -3, -1)$

Es wird der kleinste negative Wert ausgewählt, hier: $-6$. Dieser gehört zur Nichtbasisvariablen $x_2$. Die Nichtbasisvariable $x_2$ besitzt die Pivotspalte

$a_2 = \begin{pmatrix} 2 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \\ -6  \end{pmatrix}$

2. Schritt: Auswahl der Pivotzeile.

Die Pivotzeile wird bestimmt, indem die Inverse $B^{-1}$ mit der aktuell ausgewählte Pivotspalte $a_2$ und der rechten Seite $b$ mulipliziert wird. Dabei werden $a_2$ und $b$ in eine Matrix geschrieben:

$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{pmatrix} 2 & 80 \\ 1 & 60 \\ 0 & 20 \\ 1 & 30 \\ 0 & 10 \\ 0 & 5 \\ -6 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 80 \\ 1 & 60 \\ 0 & 20 \\ 1 & 30 \\ 0 & 10 \\ 0 & 5 \\ -6 & 0 \end{pmatrix}$

Die Ergebnismatrix wird dann verwendet, um die Pivtozeile zu bestimmen. Es werden die Werte der 2. Spalte durch die zugehörigen Werte der 1. Spalte geteilt. Hierbei dürfen in der 1. Spalte nur Werte größer als Null verwendet werden. Existieren keine Werte größer als Null, so existiert keine optimale Lösung. Es wird der kleinste Quotient ausgewählt:

$min \{ \frac{80}{2}, \frac{60}{1}, \frac{30}{1} \} = 30$.

Der Quotient steht in der 4. Zeile, demnach handelt es sich hierbei um die Basisvariable $x_8$.

Schritt 3: Neuberechnung der Inversen

Es wird nun in der Ausgangsmatrix $B$ die Spalte von $x_8$ ersetzt durch die Spalte von $x_2$ aus der Matrix $N$. Denn $x_2$ verlässt nun die Nichtbasis und wechselt in die Basis. Hingegen wechselt $x_8$ nun in die Nichtbasis. Das bedeutet auch $N$ muss angepasst werden:

$B = \begin{bmatrix} 1 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -6 & 0 & 0 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 1 & 0 & 4 & 1 \\ 2 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -4 & 0 & -3 & -1 \end{bmatrix}$ 

Die Inverse muss nun neu berechnet werden, da sich $B$ geändert hat. Diesemal entspricht die Inverse $B^{-1}$ nicht der Matrix $B$. Diese muss also nun mittels Gauß-Jordan-Algorithmus bestimmt werden:

$B^{-1} = \begin{bmatrix} 1 & 0 & 0 & -2 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 6 & 0 & 0 & 1 \end{bmatrix}$

2. Iteration

Es kann als nächstes mit der 2. Iteration begonnen werden. 

1. Schritt: Auswahl der Pivotspalte.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = (0, 0, 0, 6, 0, 0, 1) \cdot \begin{bmatrix} 1 & 0 & 4 & 1 \\ 2 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ -4 & 0 & -3 & -1 \end{bmatrix} = (-4, 0, -3, -1)$

Der kleinste negative Wert ist $-4$ für die Nichtbasisvariable $x_1$.

Die dazugehörige Pivotspalte ist:

$a_1 =  \begin{pmatrix} 1 \\ 2 \\ 1 \\ 0 \\ 0 \\ 0 \\ -4 \end{pmatrix}$

2. Schritt: Auswahl der Pivotzeile.

$B^{-1} \cdot (a_1, b)^T = \begin{bmatrix} 1 & 0 & 0 & -2 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 6 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{pmatrix} 1 & 80 \\ 2 & 60 \\ 1 & 20 \\ 0 & 30 \\ 0 & 10 \\ 0 & 5 \\ -4 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 20 \\ 2 & 30 \\ 1 & 20 \\ 0 & 30 \\ 0 & 10 \\ 0 & 5 \\ -4 & 180 \end{pmatrix}$

Kleinsten Quotienten:

$min \{ \frac{20}{1}, \frac{30}{2}, \frac{20}{1} \} = 15$.

Der Quotient $15$ befindet sich in der 2. Zeile. Demnach ist die Basisvariable $x_6$ zu wählen.

Schritt 3: Neuberechnung der Inversen

Es wird nun $x_1$ und $x_6$ getauscht und demnach die Matrizen $B$ und $N$ angepasst (Spaltentausch):

$B = \begin{bmatrix} 1 & 1 & 0 & 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & -4 & 0 & -6 & 0 & 0 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 0 & 0 & 4 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & -3 & -1 \end{bmatrix}$ 

Da sich $B$ verändert hat, muss die Inverse $B^{-1}$ neu berechnet werden:

$B^{-1} = \begin{bmatrix} 1 & -\frac{1}{2} & 0 & -\frac{3}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & 0 & 0\\ 0 & -\frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 2 & 0 & 4 & 0 & 0 & 1 \end{bmatrix}$

3. Iteration

1. Schritt: Auswahl der Pivotspalte.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = (0, 2, 0, 4, 0, 0, 1) \cdot \begin{bmatrix} 0 & 0 & 4 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & -3 & -1 \end{bmatrix} = (2, 4, -1, -1)$

Der kleinste negative Wert ist $-1$ für die Nichtbasisvariablen $x_3$ und $x_4$. Es wird beliebig $x_3$ gewählt.

Die dazugehörige Pivotspalte ist:

$a_3 =  \begin{pmatrix} 4 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ -3 \end{pmatrix}$

2. Schritt: Auswahl der Pivotzeile.

$B^{-1} \cdot (a_3, b)^T$

$\begin{bmatrix} 1 & -\frac{1}{2} & 0 & -\frac{3}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 0 & -\frac{1}{2} & 0 & 0 & 0\\ 0 & -\frac{1}{2} & 1 & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 2 & 0 & 4 & 0 & 0 & 1 \end{bmatrix} \cdot \begin{pmatrix} 4 & 80 \\ 1 & 60 \\ 0 & 20 \\ 0 & 30 \\ 1 & 10 \\ 0 & 5 \\ -3 & 0 \end{pmatrix} = \begin{pmatrix} \frac{7}{2} & 5 \\ \frac{1}{2} & 15 \\ -\frac{1}{2} & 5 \\ 0 & 30 \\ 1 & 10 \\ 0 & 5 \\ -1 & 240 \end{pmatrix}$

Kleinsten Quotienten:

$min \{ \frac{5}{\frac{7}{2}}, \frac{15}{\frac{1}{2}}, \frac{10}{1} \} = 0,7$.

Der Quotient $0,7$ befindet sich in der 1. Zeile. Demnach ist die Basisvariable $x_5$ zu wählen.

Schritt 3: Neuberechnung der Inversen

Es wird nun $x_3$ und $x_5$ getauscht und demnach die Matrizen $B$ und $N$ angepasst (Spaltentausch):

$B = \begin{bmatrix} 4 & 1 & 0 & 2 & 0 & 0 & 0 \\ 1 & 2 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ -3 & -4 & 0 & -6 & 0 & 0 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 \end{bmatrix}$ 

Da sich $B$ verändert hat, muss die Inverse $B^{-1}$ neu berechnet werden:

$B^{-1} = \begin{bmatrix} \frac{2}{7} & -\frac{1}{7} & 0 & -\frac{3}{7} & 0 & 0 & 0 \\ -\frac{1}{7} & \frac{4}{7} & 0 & -\frac{2}{7} & 0 & 0 & 0\\ \frac{1}{7} & -\frac{4}{7} & 1 & \frac{2}{7} & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ -\frac{2}{7} & \frac{1}{7} & 0 & \frac{3}{7} & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \frac{2}{7} & \frac{13}{7} & 0 & \frac{25}{7} & 0 & 0 & 1 \end{bmatrix}$

4. Iteration

1. Schritt: Auswahl der Pivotspalte.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = (\frac{2}{7}, \frac{13}{7}, 0, \frac{25}{7}, 0, 0, 1) \cdot \begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 \end{bmatrix} = (\frac{13}{7}, \frac{25}{7}, \frac{2}{7}, -\frac{5}{7})$

Der kleinste negative Wert ist $-\frac{5}{7}$ für die Nichtbasisvariablen $x_4$.

Die dazugehörige Pivotspalte ist:

$a_4 =  \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ -1 \end{pmatrix}$

2. Schritt: Auswahl der Pivotzeile.

$B^{-1} \cdot (a_3, b)^T $

 $\begin{bmatrix} \frac{2}{7} & -\frac{1}{7} & 0 & -\frac{3}{7} & 0 & 0 & 0 \\ -\frac{1}{7} & \frac{4}{7} & 0 & -\frac{2}{7} & 0 & 0 & 0\\ \frac{1}{7} & -\frac{4}{7} & 1 & \frac{2}{7} & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ -\frac{2}{7} & \frac{1}{7} & 0 & \frac{3}{7} & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \frac{2}{7} & \frac{13}{7} & 0 & \frac{25}{7} & 0 & 0 & 1 \end{bmatrix} \cdot \begin{pmatrix} 1 & 80 \\ 0 & 60 \\ 0 & 20 \\ 0 & 30 \\ 0 & 10 \\ 1 & 5 \\ -1 & 0 \end{pmatrix} = \begin{pmatrix} \frac{2}{7} & \frac{10}{7} \\ -\frac{1}{7} & \frac{100}{7} \\ \frac{1}{7} & \frac{40}{7} \\ 0 & \frac{60}{7} \\ -\frac{2}{7} & 10 \\ 1 & 5 \\ -\frac{5}{7} & \frac{1690}{7} \end{pmatrix}$

Kleinsten Quotienten:

$min \{\frac{\frac{10}{7}}{\frac{2}{7}}, \frac{\frac{40}{7}}{\frac{1}{7}}, \frac{5}{1} \} = 5$

Der Quotient $5$ befindet sich in der 1. und 6.Zeile. Es wird beliebig zwischen $x_3$ (ist bereits im vorherigen Schritt mit $x_5$ getauscht worden) und $x_{10}$ gewählt. Es wird $x_{10}$ gewählt (im Grunde ist es egal welche Variable man hier wählt. Man kann also auch $x_3$ wieder in die Nichtbasis bringen. Man sollte sich bei einer solchen Situation dann aber für die Schlupfvariable entscheiden).

Schritt 3: Neuberechnung der Inversen

Es wird nun $x_4$ und $x_{10}$ getauscht und demnach die Matrizen $B$ und $N$ angepasst (Spaltentausch). Nicht vergessen, $x_{10}$ befindet sich in Spalte 6 (die letzte Spalte ist der Einheitsvektort). Der Spalte 6 der Matrix $B$ wird also nun $x_4$ zugefügt und der Spalte 4 der Matrix $N$ demnach $x_{10}$:

$B = \begin{bmatrix} 4 & 1 & 0 & 2 & 0 & 1 & 0 \\ 1 & 2 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ -3 & -4 & 0 & -6 & 0 & -1 & 1 \end{bmatrix}$

$N = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$ 

Da sich $B$ verändert hat, muss die Inverse $B^{-1}$ neu berechnet werden:

$B^{-1} = \begin{bmatrix} \frac{2}{7} & -\frac{1}{7} & 0 & -\frac{3}{7} & 0 & -\frac{2}{7} & 0 \\ -\frac{1}{7} & \frac{4}{7} & 0 & -\frac{2}{7} & 0 & \frac{1}{7} & 0 \\ \frac{1}{7} & -\frac{4}{7} & 1 & \frac{2}{7} & 0 & -\frac{1}{7} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ -\frac{2}{7} & \frac{1}{7} & 0 & \frac{3}{7} & 1 & \frac{2}{7} & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \frac{2}{7} & \frac{13}{7} & 0 & \frac{25}{7} & 0 & \frac{5}{7} & 1 \end{bmatrix}$

5. Iteration

1. Schritt: Auswahl der Pivotspalte.

Es wird nun die Zielfunktionszeile der Inversen $B^{-1}$ mit $N$ multipliziert:

$c_{B^{-1}} \cdot N = (\frac{2}{7}, \frac{13}{7}, 0, \frac{25}{7}, 0, \frac{5}{7}, 1) \cdot  \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = (\frac{13}{7}, \frac{25}{7},\frac{2}{7}, 1)$

Da keine negativen Werte mehr vorhanden sind, ist die Lösung optimal.

Optimale Lösung

Man betrachtet die letzte Matrix $B$ und dort die Spalten. Diese gleicht man mit der zu Beginn aufgestellten Matrix $A$ ab. Man sieht deutlich, dass die Variablen (der Reihenfolge in der sie in der Matrix $B$ auftreten nach) $x_3, x_1, x_7, x_2, x_9, x_4$ (plus Einheitsvektor) in der Basis befinden. Für diese Variablen müssen die dazugehörigen Werte berechnet werden. Diese werden bestimmt, indem die Inverse $B^{-1}$ mit der rechten Seite $b$ multipliziert wird:

Die Werte für die Basisvariablen ergeben sich durch Multiplikation der Inversen $B^{-1}$ mit der rechten Seite $b$:

$ \begin{bmatrix} \frac{2}{7} & -\frac{1}{7} & 0 & -\frac{3}{7} & 0 & -\frac{2}{7} & 0 \\ -\frac{1}{7} & \frac{4}{7} & 0 & -\frac{2}{7} & 0 & \frac{1}{7} & 0 \\ \frac{1}{7} & -\frac{4}{7} & 1 & \frac{2}{7} & 0 & -\frac{1}{7} & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ -\frac{2}{7} & \frac{1}{7} & 0 & \frac{3}{7} & 1 & \frac{2}{7} & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \frac{2}{7} & \frac{13}{7} & 0 & \frac{25}{7} & 0 & \frac{5}{7} & 1 \end{bmatrix} \cdot \begin{pmatrix} 80 \\ 60 \\ 20 \\ 30 \\ 10 \\ 5 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 15 \\ 5 \\ 30 \\ 10 \\ 5 \\ 245 \end{pmatrix}$

Dabei gilt $x_3 = 0$, $x_1 = 15$, $x_7 = 5$, $x_2 = 30$, $x_9 = 10$ und $x_4 = 5$. Der Zielfunktionswert kann in der Ergebnismatrix in der unteresten Zeile abgelesen werden $f = 245$.