Simplex Algorithmus

Gesperrte Variablen

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.

Freie Variablen

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

Stoppregel

  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.

Auswahl des Pivotelements

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

Dualer Simplex

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\}$