Minimierungsproblem- Big-M/dualer Simplex

Es ist natürlich ebenfalls möglich ein gegebenes Minimierungsproblem durch bestimmte Umformumgsregeln in ein Maximierungsproblem zu transformieren und dann die Big-M-Methode bzw. den dualen Simplexalgorithmus anzuwenden ohne das Problem vorher zu dualisieren.

Umformung in Standardform (erweitert)

1. Aus einem Minimierungsproblem wird ein Maximierungsproblem, indem die Zielfunktion mit multipliziert wird.
   
   
2. Ersetzen von , welche keiner Nichtnegativitätsbedingung unterliegt, durch und , wobei gilt .
   
   
3. Eine Gleichung kann durch zwei Ungleichungen ersetzt werden
   und .
   
   
4. Aus einer -Ungleichung wird eine -Ungleichung durch Multiplikation der gesamten Ungleichung mit .

Beispiel: Minimierungsproblem und dualer Simplexalgorithmus

Gegeben sei das folgende Minimierungsproblem:

   min!

u.d.N

Das Problem wird nun zunächst auf die Standardform gebracht (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung):

1. Zielfunktion mit multiplizieren:

   max!

2. Nebenbedingungen mit Gleichheitszeichen in zwei Ungleichungen überführen:

3. Größer/Gleich-Nebenbedingungen in Kleiner/Gleich-Nebenbedingungen umformen durch Multiplikation mit :

Das Maximierungsproblem sieht wie folgt aus:

   max!

u.d.N

Es wird anhand der Standardform nochmals geprüft, welcher Simplex hier angewandt werden kann. Der primale Simplex ist hier nicht anwendbar, da die rechte Seite negative Werte aufweist. Es kann also der duale Simplexalgorithmus angewandt werden (alternativ: Big-M-Methode). Hierzu muss das Problem aber zunächst in Normalform vorliegen:

   max!

u.d.N

Eintragen in das Tableau:

Es kann nun der duale Simplex angewandt werden. Hierbei wird zunächst die Pivotzeile und dann die Pivotspalte ausgewählt. Es wird die Zeile als Pivotzeile gewählt, welche den kleinsten negativen Wert auf der rechten Seite aufweist. Hier existieren zwei kleinste negative Werte, es wird einer beliebig ausgewählt (1. Zeile). Es wird dann die Pivotzeile betrachtet und für alle Werte kleiner Null der Quotient aus zugehörigen Zilefunktionswert und negativen Koeffizient der Pivotzeile bestimmt:

.

Es wird der größte Wert ausgewählt.

Dort wo sich Pivotspalte und Pivotzeile treffen liegt das Pivotelement, hier: . Es wird nun der Simplexschritt durchgeführt (wie beim primalen Simplexalgorithmus). Es darf nicht vergessen werden die Basisvariable und die Nichtbasisvariable des Pivotelements zu vertauschen:

Es liegt nun das folgende neue Tableau nach Durchführung eines Simplexschrittes vor. Die Vorgehensweise sei kurz zusammengefasst:

Das Pivotelement geht mit seinem reziproken Wert ein: -\frac{1}{2}-1x_642y_1$) bleibt für die weitere Betrachtung wieder unberücksichtigt. Es muss also nur die Pivtozeile und die restlichen Elemente berechnet werden. Es resultiert das folgende Tableau:

Der Zielfunktionswert ergibt sich durch Einfügen der Basisvariablen in die Zilefunktion (Nichtbasisvariablen nehmen den Wert null an):

Da noch weitere negative Werte in der Zielfunktionszeile erhalten sind, wird der primale Simplexalgorithmus weiter angewandt. Die Pivotspalte kann beliebig zwischen und gewählt werden. Es wird die Spalte bei gewählt. Die Pivotzeile wird mit dem kleinsten Quotienten gewählt (wobei die Werte der Pivotspalte positiv sein müssen), dies entspricht hier . Das Pivotelemt ist demnach . Es ergibt sich das folgende Tableau:

Da keine negativen Werte mehr in der Zielfunktionszeile vorhanden sind, liegt die optimale Lösung vor. Diese beträgt mit und für das Maximierungsproblem . Für das Minimierungsproblem (Ausgangsprroblem) beträgt doe optimale Lösung dann:

Es resultiert dieselbe optimale Lösung wie bei dem dualen Simplexalgorithmus!