Dualer Simplexalgorithmus

Das duale Simplexverfahren wird angewandt, wenn das Optimierungsproblem in Standardform vorliegt, aber negative Werte auf der rechten Seite der Nebenbedingungen gegeben sind. Dann nämlich existiert keine zulässige Ausgangslösung. Der duale Simplex wird also angewandt um eine zulässige Ausgangslösung zu bestimmen. Nachdem die zulässige Ausgangslösung mittels dualen Simplex bestimmt wurde, kann der primale Simplexalgorithmus angewandt werden um eine optimale Lösung zu ermitteln.

Das Tableau wird analog zum primalen Simplexalgorithmus aufgestellt. Beachtet werden muss in jedem Fall, dass die Werte der Zielfunktion mit den umgekehrten Vorzeichen berücksichtigt werden müssen. Es wird im folgenden aufgezeigt wie die Wahl der Pivotspalte und der Pivotzeile erfolgt. Diese Vorgehensweise unterscheidet sich von der des primalen Simplexalgorithmus.

Wahl der Pivotspalte, Pivotzeile und des Pivotelements

Nachdem das Tableau für das lineare Optimierungsproblem wie im vorherigen Abschnitt aufgestellt worden ist, soll nun die erste Iteration für das duale Simplexverfahren durchgeführt werden. Für jede Iteration müssen die folgenden Schritte durchgeführt werden. Im Gegensatz zum primalen Simplexverfahren beginnt das duale Simplexverfahren mit Wahl der Pivotzeile:

1. Wahl der Pivotzeile s: Existiert kein $b_i < 0$, so liegt bereits eine zulässige Basislösung vor. Es wird dann das duale Simplexverfahren abbgebrochen und mit dem primale Simplexverfahren fortgesetzt.
   
   Ansonsten wird diejenige Zeile $s$ mit dem kleinsten negativen Wert der rechten Seite als Pivotzeile gewählt. Sind mehrere Zeilen mit kleinstem negativen Wert gegeben, so kann unter diesen eine beliebige Zeile ausgewählt werden. 
   
   
2. Wahl der Pivotspalte t: Sind in der Pivotszeile aus 1. alle $a_{sj} \ge 0$, so existiert für das Problem keine zulässige Basislösung. Das gesamte Verfahren wird dann abgebrochen. 
   
   Ansonsten wird die untere Zeile (Zielfunktionszeile) für alle Elemente $a_{sj} < 0$ der Pivotzeile betrachtet und diejenige Pivotspalte ausgewählt, für die gilt $max\frac{c_j}{a_{sj}}$. Dort wo sich die Pivotspalte und die Pivotzeile schneiden, liegt das Pivotelement $a_{st}$.
   
   
3. Nachdem die Pivotzeile $s$ und die Pivotspalte $t$ 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.

Die Simplexschritte sind hier analog zu denen des primalen Simplexalgorithmus.

Das Verfahren endet, wenn die Werte der rechten Seite alle positiv sind. Dann liegt eine zulässige Ausgangslösung vor. 

Beispiel: Dualer Simplexalgorithmus

Gegeben sei das folgende lineare Optimierungsproblem:

Der erste Schritt ist, das gegebene Problem in ein Maximierungsproblem mit Kleiner-Gleich-Nebenbedingungen umzuwandeln.

Die Zielfunktion soll minimiert werden, um hier ein Maximierungsproblem zu erhalten, muss diese mit (-1) multipliziert werden:

max $ Z = -x_1 - x_2$

Die Nebenbedingungen sind Größer-Gleich-Nebenbedingungen. Um hier Kleiner-Gleich-Nebenbedingungen zu erhalten, werden diese mit (-1) multipliziert:

$~~~-x_1 + 2x_2 \le -1$

$~~~-x_1 - 2x_2 \le -4$

$~~~-x_1 - x_2 \le 2$

Die Nichtnegativitätsbedingung ist bereits gegeben:

$~~~x_1, x_2 \ge 0$

Es ergibt sich ein Maximierungsproblem mit Kleiner-Gleich-Nebenbedingungen und Nichtnegativitätsbedingung:

max $ Z = -x_1 - x_2$

udN

$~~~-x_1 + 2x_2 \ge -1$

$~~~-x_1 - 2x_2 \ge -4$

$~~~-x_1 - x_2 \ge 2$

$~~~x_1, x_2 \ge 0$

Der primale Simplexalgorithmus kann hier nicht angewendet werden, weil auf der rechten Seite negative Werte gegeben sind. Es liegt demnach keine zulässige Basislösung vor. Denmach müssen wir hier den dualen Simplexalgorithmus anwenden, um eine zulässige Basislösung zu erhalten.

Zunächst wird das Problem in die Normalform überführt, indem Schlupfvariablen $y_i$ eingefügt werden:

max $ Z = -x_1 - x_2$

udN

$~~~-x_1 + 2x_2 + y_1 = -1$

$~~~-x_1 - 2x_2 + y_2 = -4$

$~~~-x_1 - x_2 + y_3 = 2$

$~~~~~x_1, x_2 \ge 0$

Danach wird das Problem in ein Tableau übertragen:

Dualer Simplex - Starttableau

Wir beginnen mit der Auswahl der Pivotzeile:

Ist ein negativer Wert auf der rechten Seite gegeben, so wird der duale Simplexalgorithmus angewendet. Wir haben hier auf der rechten Seite die (-1) und und die (-4) gegeben. Wir wählen den kleinsten negativen Wert aus, hier: (-4).

Danach wählen wir die Pivotspalte aus:

Es wird nun der Quotient aus der Zielfunktionszeile und den Werten der Pivotzeile gebildet. Dabei dürfen nur die Werte innerhalb der Pivotzeile berücksichtigt werden, die kleiner als Null sind. Die Werte der Pivotzeile sind (-1) und (-2) und demnach beide kleiner als Null. Wir bilden also die Quotienten:

$\frac{1}{-1} = -1$

$\frac{1}{-2} = -\frac{1}{2}$

Der maximale Quotient wird gewählt. Der maximale Quotient ist $-\frac{1}{2}$.

Das Pivotelement ist dort gegeben, wo sich Pivotzeile und Pivotspalte schneiden.

Die Auswahl der Pivotzeile und -spalte als Überischt:

Dualer Simplex - Auswahl Pivotzeile und -spalte

Danach folgt der Austauschschritt gemäß Simplexalgorithmus. Hier ist kein Unterschied zum primalen Simplexalgorithmus gegeben:

Dualer Simplex - Erster Austauschschritt

Es ist noch eine negative Zahl auf der rechten Seite gegeben. Wir führen also einen weiteren dualen Simplexschritt durch. Zunächst wählen wir wieder Pivotzeile und -spalte aus:

Dualer Simplex - Auswahl Pivotzeile und -spalte

Danach wenden wir den Simplexalgorithmus an und gelangen zum Endtableau:

Dualer Simplex - Endtableau

Es sind keine negativen Werte mehr auf der rechten Seite gegeben. Das optimale Endtableau ist gegeben mit:

$x_1 = \frac{5}{2}$, $x_2 = \frac{3}{4}$ und $y_3 = \frac{21}{4}$.

Die dritte Nebenbedingung weist also noch eine Restkapazität von $\frac{21}{4}$ auf.