Beispiel: Minimierungsproblem ohne optimal Lösung

In diesem Abschnitt wird ein Minimierungsproblem aufgezeigt, für welches zwar eine zulässige, jedoch keine optimale Lösung voliegt.

Gegeben sei das folgende Minimierungsproblem:

$f(x_1, x_2, x_3) = 5x_1 + 8x_2 - x_3$   $\rightarrow$  min!

u.d.N.

$4x_1 + 2x_2 + x_3 \ge 30$

$6x_1 + 4x_2 + x_3 \ge 40$

$           x_2           \ge 12$

$x_1, x_2, x_3$

Lösung ohne Dualsierung

Das Problem wird mittels der Umformungsregeln in ein duales Maximierungsproblem umgeformt. Dabei muss das Minimierungsproblem die folgende Form aufweisen (Größer/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung). Da dies bereits der Fall ist, können als nächstes die Umformungsregeln angewandt werden:

$f(x_1, x_2, x_3) = -5x_1 - 8x_2 + x_3$   $\rightarrow$  max!

u.d.N.

$-4x_1 - 2x_2 - x_3 \le -30$

$-6x_1 - 4x_2 - x_3 \le -40$

$           -x_2         \le -12$

$x_1, x_2, x_3$

Es liegen negative Werte auf der rechten Seite vor. Es wird der duale Simplexalgorithmus (alternativ: Big-M-Methode) angewandt. Das Problem wird in die Normalform überführt:

$f(x_1, x_2, x_3) = -5x_1 - 8x_2 + x_3$   $\rightarrow$  max!

u.d.N.

$-4x_1 - 2x_2 - x_3  + x_4                      = -30$

$-6x_1 - 4x_2 - x_3           + x_5             = -40$

$           -x_2                             + x_6   = -12$

$x_1, x_2, x_3$

Das Problem wird als nächstes in das Ausgangstableau eingetragen und der duale Simplexalgorithmus angewandt. Nach 3. Iterationsschritten, ist die zulässige Basislösung erreicht (alle Werte der rechten Seite sind positiv):

Um eine optimale Lösung zu erhalten, muss als nächstes der primale Simplexalgorithmus angewandt werden. Hier muss zunächst die Pivotspalte (kleinster negativer Wert) ausgewählt werden. Diese liegt bei $-1$. Die Pivtozeile wird dann ausgewählt, indem die Werte der rechten Seite durch die Werte der Pivotspalte geteilt werden, wobei die Werte der Pivotspalte größer als Null sein müssen. Dies ist hier nicht gegeben. Demnach existiert zwar eine zulässige Basislösung, jedoch keine optimale Lösung. Das Verfahren wird hier abgebrochen (siehe Abschnitt: Sonderfälle bei Optimierungsmodellen). 

Vorgehen mit Dualsisierung

Die Dualsierung muss hier nicht weiter betrachtet werden, denn für das duale Problem existiert keine zulässige Basislösung (siehe Abschnitt Sonderfälle bei Optimierungsmodellen).