ZU DEN KURSEN!

Operations Research - Duales Simplexverfahren

Kursangebot | Operations Research | Duales Simplexverfahren

Operations Research

Duales Simplexverfahren

In diesem Abschnitt soll gezeigt werden, wie das duale Simplexverfahren angewandt werden kann. Das duale Simplexverfahren wird dann angewandt, wenn das Optimierungsproblem nicht in kanonischer Form gegeben ist bzw. sich schwer in diese Form umformen lässt.

Merke

Das lineare Optimierungsmodell liegt in kanonischer Form vor, wenn die Werte der rechten Seite alle positiv sind $b_i \ge 0$ und die Standardform (Maximierungsproblem, kleiner-gleich-Nebenbedingungen, Nichtnegativitätsbedinung) vorliegt. 

Liegt das lineare Optimierungsmodell in kanonischer Form vor, so existiert bereits zu Beginn des Simplexverfahrens eine zulässige Basislösung und es kann das primale Simplexverfahren angewandt werden. In diesem Abschnitt soll nun aber das lineare Optimierungsmodell nicht in kanonischer Form vorliegen. Das bedeutet also, dass keine zulässige Basislösung vorliegt. Ist dies der Fall, so muss das duale Simplexverfahren oder die Big-M-Methode (siehe spätere Abschnitte) angewandt werden.

Methode

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

Es wird im folgenden anhand eines Beispiels gezeigt, wie bei dem dualen Simplexverfahren vorgegangen wird.

Gegeben sei das folgende Optimierungsproblem

$f(x_1, x_2) = 2x_1 + x_2$  $ \rightarrow$   max!

u.d.N.

$x_1 + x_2 \ge 8$

$3x_1 + x_2 \ge 12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt noch nicht in Standardform vor (größer-gleich-Nebenbedingungen vorhanden). Es muss also zunächst in diese transformiert werden. Eine größer-gleich-Nebenbedinung wird ein eine kleiner-gleich-Nebenbedingung transformiert, indem diese mit $-1$ multipliziert wird:

$f(x_1, x_2) = 2x_1 + x_2$  $ \rightarrow$   max!

u.d.N.

$-x_1 - x_2 \le -8$

$-3x_1 - x_2 \le -12$

$x_1 + x_2 \le 10$

$x_1, x_2 \ge 0$

Das Optimierungsmodell liegt nun in Standardform vor (Maximierungsproblem, kleiner-gleich-Bedingungen, Nichtnegativitätsbedingung). Allerdings sind hier die Werte der rechten Seite nicht alle positiv, weshalb keine zulässige 1. Basislösung existiert. Es muss demnach das duale Simplexverfahren angewandt werden. Das Opmtimierungsproblem wird zunächst in die Normalform überführt (Einfügen von Schlupfvarbiablen um Gleichheitsbedingungen zu erhalten):

$f(x_1, x_2) = 2x_1 + x_2$  $ \rightarrow$   max!

u.d.N.

$-x_1 - x_2 + x_3                    = -8$

$-3x_1 - x_2        + x_4           = -12$

$x_1 + x_2                           + x_5    = 10$

$x_1, x_2, x_3, x_4, x_5 \ge 0$

Danach werden die Werte in das Simplextableau eingetragen:

Duales Simplexverfahren Anfangstableau

Das obige Anfangstableau erhält die unzulässige Basislösung $x_1 = 0$, $x_2 = 0$, $x_3 = -8$, $x_4 = -12$ und $x_5 = 10$ mit dem Zielfunktionswert $f(x_1, x_2) = z = 0$. Diese Lösung ist deshalb unzulässig, da die Nichtnegativitätsbedingung für die Variablen $x_3$ und $x_4$ nicht gegeben ist. 

Merke

Nicht vergessen! Die Zielfunktionswerte gehen mit dem negativen Wert in das Tableau ein!