ZU DEN KURSEN!

Operations Research 2 - Primaler Simplexalgorithmus

Kursangebot | Operations Research 2 | Primaler Simplexalgorithmus

Operations Research 2

Primaler Simplexalgorithmus

Methode

Hier klicken zum Ausklappen

Voraussetzung für die Anwendung des primalen Simplex-Verfahrens:

  1. Es muss die Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung).

  2. Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.

  3. Es liegen keine negativen Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \ge 0$). Das Problem ist also in kanonischer Form gegeben.

Der primale Simplexalgorithmus geht wie folgt vor:

  • Ausgehend von einer Startecke mit einer Ausgangsbasis schreitet dieser durch Basisaustausch zu einer Ecke mit besserem Zielfunktionswert fort.
  • Da es nur endlich viele Ecken gibt, wird nach endlich vielen Schritten die optimale Lösung erreicht.
  • Der Basistausch geschieht dabei so sparsam wie möglich: Es wird stets genau eine Basisvariable gegen eine Nichtbasisvariable ausgetauscht

Das Simplexverfahren findet in einem sogenannten Simplex-Tableau statt. Dieses ist wie folgt aufgebaut:

Erläuterung des Tableaus zu Beginn des Verfahrens:

Auf der linken Seite stehen die Basisvariablen. Dies sind die Schlupfvariablen, welche mit dem Wert Null in die Zielfunktion eingehen und demnach in dieser nicht berücksichtigt werden. Auf der rechten Seite stehen die Werte rechts von den Nebenbedingungen. Beim primalen Simplex müssen diese Werte alle positiv sein. Ganz oben stehen die Nichtbasisvariablen, dies sind die Entscheidungsvariablen, welche nicht mit dem Wert Null in die Zielfunktion eingehen. Ganz unten stehen die Werte, welche die Nichtbasisvariablen in der Zielfunktion besitzen. Diese müssen mit entgegengesetzten Vorzeichen versehen werden (positive Werte werden negativ und umgekehrt). Unten rechts steht der momentane Zielfunktionswert (zu Beginn ist dieser Null). In die Mitte des Tableaus kommen alle Werte der Nichtbasisvariablen der Nebenbedingungen.

Merke

Hier klicken zum Ausklappen

Die sich in der Zielfunktion befindlichen Variablen (Variablen die nicht mit den Wert Null in die Zielfunktion eingehen) gehen in das Anfangstableau als Nichtbasisvariablen ein. Die sich nicht in der Zielfunktion befindlichen Variablen (=Schlupfvariablen) gehen als Basisvariablen in das Anfangstableau ein.

Pivotzeile, -spalte und -element

Nachdem das Tableau für das lineare Optimierungsproblem aufgestellt worden ist, soll nun die erste Iteration für das primale Simplexverfahren durchgeführt werden. Für jede Iteration müssen die folgenden Schritte durchgeführt werden:

  1. Wahl der Pivotspalte t: Enthält die untere Zeile, in welche die Werte aus der Zielfunktion eingetragen werden, nur nicht-negative Werte, so ist die optimale Lösung gefunden. Ansonsten wird diejenige Spalte mit dem kleinsten negativen Wert ausgewählt. Sind mehrere Spalten mit kleinstem negativen Wert gegeben, so kann unter diesen eine beliebige Spalte ausgewählt werden. 

  2. Wahl der Pivotzeile s: Sind in der Pivotspalte aus 1. alle $a_{it} \le 0$, so exsitiert für das Problem keine optimale Lösung. Das Verfahren muss abgebrochen werden. Ansonsten wird die rechte Seite für alle Elemente $a_{it} \ge 0$ der Pivotspalte betrachtet und diejenige Pivotzeile ausgewählt, für die gilt $min\frac{bi}{a_{it}} = min$. Dort wo sich die Pivotspalte und die Pivotzeile schneiden, liegt das Pivotelement $a_{st}$.

  3. Nachdem die Pivotspalte $t$ und die Pivotzeile $s$ sowie das Pivotelement $a_{st}$ bestimmt worden sind, wird nun in einem nächsten Schritt die Basisvariable der Pivotzeile mit der Nichtbasisvarbiablen der Pivotspalte getauscht und ein neues Tableau aufgestellt. Hierzu müssen bestimmte Simplexschritte durchgeführt werden.

Simplexschritt

Bei einem Austauschschritt berechnet sich das neue Simplextableau folgendermaßen:

Methode

Hier klicken zum Ausklappen

Pivotelement: $a_{st} = \frac{1}{a_{st}}$

Dort wo das Pivotelement stand wird der neue Wert bestimmt, indem der Kehrwert gebildet wird: $\frac{1}{\text{Pivotelemt}}$.

Methode

Hier klicken zum Ausklappen

Pivotzeile $s$:

$a_{sj} = \frac{a_{sj}}{a_{st}}$

$b_{s} = \frac{b_r}{a_{st}}$

Die neuen Werte in der Pivotzeile werden bestimmt, indem die alten Werte durch das Pivotelement dividiert werden. Dies gilt auch für den Wert der rechten Seite der Pivotzeile.

Methode

Hier klicken zum Ausklappen

Pivotspalte $t$: 

$a_{it} = - \frac{a_{it}}{a_{st}}$

$c_t = - \frac{c_t}{a_{st}}$

Die neuen Werte der Pivotspalte werden bestimmt, indem die alten Werte durch das Pivotelement dividiert und mit einem Minuszeichen versehen werden. Dies gilt auch für den neuen Wert der Zielfunktionszeile der Pivotspalte.

Methode

Hier klicken zum Ausklappen

Restliche Elemente: 

$a_{ij} = a_{ij} - \frac{a_{it} \cdot a_{sj}}{a_{st}}$

$c_j = c_j - \frac{c_t \cdot a_{sj}}{a_{st}}$

$b_i = b_i - \frac{b_s \cdot a_{it}}{a_{st}}$

Die restlichen Werte werden bestimmt, indem von dem alten Wert das Produkt aus zugehörigem Element der Pivospalte und Pivotzeile dividiert mit dem Pivotelemet abgezogen wird.

Diese Rechenschritte müssen durchgeführt werden, damit das neue Tableau mit verbesserten Zielfunktionswert ermittelt werden kann.

Merke

Hier klicken zum Ausklappen

Das Optimaltableau mit der optimalen Lösung für die Entscheidungsvariablen liegt dann vor, wenn die Werte in der Zielfunktionszeile (unterste Zeile) alle positiv sind.