Simplex Algorithmus

Angewandt bei Gleichungsrestriktionen.

Strukturvariable nehmen den Wert Null an, um die Gleichung zu erfüllen.

1. Pivotspalte: Jede Spalte, die keine gesperrte Variable als Nichtbasisvariable hat und in der Pivot-Zeile ein Nichtnullelement enthält.
2. Pivotzeile: Jede Zeile, in denen sich gesperrte Variablen in der Basis befinden.

Pivotspalte kann anschließend gestrichen werden.

Variablen für die die Nichtnegativitätsbedingung nicht gelten, werden als freie Variablen bezeichnet. Diese müssen in die Basis.

1. Pivotspalte: Jede Spalte, die freie Variablen als Nichtbasisvariable hat.
2. Pivotzeile: Jede Zeile, die keine freie Variable als Nichtbasisvariable hat und in der Pivot-Zeile ein Nichtnullelement enthält.

Angewandt bei negativen rechten Seiten

1. Wenn $c_j \leq 0$ für alle $j$, dann ist $x$ optimal und $z_0$ das zugehörige Maximum.
2. Wenn ein $c_s > 0$ und alle $a_{is} \leq 0, i = 1, \dots ,m$, dann existiert kein Maximum.

1. Pivotspalte: Größter positiver Zielfunktionskoeffizient
2. Pivotzeile: $\frac{b_r}{a_{rs}} = min \{ \frac{b_i}{a_{is}} | a_{is} > 0\}$

Problem: Zielfunktion optimal nach Stoppregel 1 der Phase 2, aber negative rechte Seiten.

Lösung:

1. Pivotzeile: $b_r = min \{b_i\}$
2. Pivotspalte:

• a) Wenn $a_{rj} \geq 0$ für alle j, dann existiert keine zulässige Lösung.
• b) $\frac{c_s}{a_{rs}} = min \{ \frac{c_j}{a_{rj}} | a_{rj} < 0\}$