ZU DEN KURSEN!

Operations Research 2 - Dualer Simplexalgorithmus

Kursangebot | Operations Research 2 | Dualer Simplexalgorithmus

Operations Research 2

Dualer Simplexalgorithmus

Methode

Hier klicken zum Ausklappen

Voraussetzung für die Anwendung des dualen 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 negative Koeffizienten auf der Rechten-Seite der Nebenbedingungen vor ($b_i \le 0$).

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.

Merke

Hier klicken zum Ausklappen

Der duale Simplexalgorithmus wird angewendet, wenn die Werte der rechten Seite der Nebenbedingungen negativ sind. Der primale Simplexalgorithmus wird angewendet, wenn alle Werte der rechten Seite positiv sind. Der duale Simplexalgorithmus führt zu einer zulässigen Ausgangslösung, der primale Simplexalgorithmus zu einer optimalen Lösung. Nach Anwendung des dualen Simplexalgorithmus' kann der primale Simplexalgorithmus angewendet werden, um eine optimale Lösung zu erhalten. 

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. 

Merke

Hier klicken zum Ausklappen

Der duale und der primale Simplexalgorithmus unterscheiden sich dahingehend, dass diese eine andere Vorgehensweise bei der Wahl der Pivotspalte und Pivotzeile aufweisen.

Beispiel: Dualer Simplexalgorithmus

Gegeben sei das folgende lineare Optimierungsproblem:

Methode

Hier klicken zum Ausklappen

min $ 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 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 \ge -1$

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

$~~~-x_1 - x_2 \ge 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
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).

Methode

Hier klicken zum Ausklappen

Die zweite Zeile ist die Pivotzeile.

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

Methode

Hier klicken zum Ausklappen

Die zweite Spalte ist die Pivotspalte.


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

Methode

Hier klicken zum Ausklappen

Das Pivotelement ist (-2).


Die Auswahl der Pivotzeile und -spalte als Überischt:

Dualer Simplex - Auswahl Pivotzeile und -spalte
Dualer Simplex - Auswahl Pivotzeile und -spalte

 


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

Dualer Simplex - Erster Austauschschritt
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
Dualer Simplex - Auswahl Pivotzeile und -spalte

 

Danach wenden wir den Simplexalgorithmus an und gelangen zum Endtableau:

Dualer Simplex - 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.