or:simplex_algorithmus [AE Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Simplex Algorithmus ======

===== Phase 0 =====
==== Gesperrte Variablen ====

Angewandt bei Gleichungsrestriktionen.

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

  - Pivotspalte: Jede Spalte, die **keine gesperrte Variable** als Nichtbasisvariable hat und in der Pivot-Zeile **ein Nichtnullelement** enthält. 
  - 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.

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

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


==== Auswahl des Pivotelements ====
  - Pivotspalte: Größter positiver Zielfunktionskoeffizient
  - 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:
  - Pivotzeile: $b_r = min \{b_i\}$
  - 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\}$