Zusammenfassung: Minimierungsproblem

In diesem Abschnitt soll nochmals zusammegefasst werden, wie eine optimale Lösung mittels der unterschiedlichen Simplexverfahren gewonnen werden kann, wenn ein Minimierungsproblem gegeben ist. 

Vorgehen ohne Dualisierung

1. Wird das Minimierungsproblem nicht dualisiert, so muss dieses mittels der Umformungsregeln in die Standardform überführt (Maximierungsproblem, Kleiner/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung. Die Umformungsregeln lauten:

• Aus einem Minimierungsproblem wird ein Maximierungsproblem, indem die Zielfunktion mit $-1$ multipliziert wird.
  
  
• Ersetzen von $x_j$, welche keiner Nichtnegativitätsbedingung unterliegt, durch $x_j^+ \ge $ und $x_j^- \ge $, wobei gilt $x_j = x_j^+ - x_j^-$.
  
  
• Eine Gleichung $a_{i1}x_1 + ... + a_{in} x_n = b_i$ kann durch zwei Ungleichungen ersetzt werden
  $a_{i1}x_1 + ... + a_{in} x_n = b_i$ und $-a_{i1}x_1 - ... - a_{in} x_n = -b_i$.
  
  
• Aus einer $\ge$-Ungleichung wird eine $\le$-Ungleichung durch Multiplikation der gesamten Ungleichung mit $-1$.

2. Das Maximierungsproblem wird dann in die Normalform überführt -> Einfügen von Schlupfvariablen zur Erreichung von Gleichheitsbedingungen. Die Schlupfvariablen gehen mit dem Wert Null in die Zielfunktion ein und können demnach in dieser unberücksichtigt bleiben.

• Sind die Werte der rechten Seite alle positiv, wird der primale Simplexalgorithmus angewandt. Hier wird zunächst die Pivotspalte und dann die Pivotzeile ausgewählt. Danach erfolgt der Simplexschritt. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 
  
  
• Sind Werte der rechten Seite negativ, wird der duale Simplexalgoithmus oder die Big-M-Methode angewandt. 
  
  Beim dualen Simplexalgorithmus wird zunächst die Pivotzeile und dann die Pivotspalte gewählt. Es erfolgt der Simplexschritt. Erst wenn alle Werte der rechten Seite positiv sind liegt eine zulässige Basislösung vor. Liegen dann noch negative Werte in der Zielfunktionszeile vor, muss der primale Simplexalgorithmus angewandt werden um die Optimallösung zu erhalten. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 
  
  Bei der Big-M-Methode wird jede Gleichheitsbedingung, die negative Werte aufweist, mit $-1$ multipliziert. Dort wo sich dann negative Schlupfvariablen ergeben, wird jeweils eine künstliche Variable $y_i$ eingefügt. Diese wird in der Zielfunktion mit $-M$ bewertet, wobei $M$ als hinreichend groß angenommen wird. Die künstlichen Variablen müssen dann aus der Zielfunktion entfernt werden, indem die Nebenbedingungen nach diesen aufgelöst und in die Zielfunktion eingesetzt werden. Danach wird der primale Simplexalgorithmus angewandt. Für die Pivotspalte wird sich dabei in der Zielfunktionszeile an $M$ orientiert, da diese als hinreichend groß angenommen werden. Sind keine negativen Werte in der Zielfunkktion erhalten liegt die optimale Lösung vor.

Vorgehen bei Dualisierung

1. Wird das Minimierungsproblem dualisiert, so muss dieses zunächst in die folgende Form überführt werden: Minimierungsproblem, Größer/Gleich-Nebenbedingungen, Nichtnegativitätsbedingung. Danach wird die Dualsierung vorgenommen. Es liegt dann ein duales Maximierungsproblem vor. 

2. Das duale Maximierungsproblem wird dann in die Normalform überführt -> Einfügen von Schlupfvariablen zur Erreichung von Gleichheitsbedingungen. Die Schlupfvariablen gehen mit dem Wert Null in die Zielfunktion ein und können demnach in dieser unberücksichtigt bleiben.

• Sind die Werte der rechten Seite alle positiv, wird der primale Simplexalgorithmus angewandt. Hier wird zunächst die Pivotspalte und dann die Pivotzeile ausgewählt. Danach erfolgt der Simplexschritt. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 
  
  
• Sind Werte der rechten Seite negativ, wird der duale Simplexalgoithmus oder die Big-M-Methode angewandt. 
  
  Beim dualen Simplexalgorithmus wird zunächst die Pivotzeile und dann die Pivotspalte gewählt. Es erfolgt der Simplexschritt. Erst wenn alle Werte der rechten Seite positiv sind liegt eine zulässige Basislösung vor. Liegen dann noch negative Werte in der Zielfunktionszeile vor, muss der primale Simplexalgorithmus angewandt werden um die Optimallösung zu erhalten. Erst wenn alle Werte der Zielfunktionszeile positiv sind, ist die Lösung optimal. 
  
  Bei der Big-M-Methode wird jede Gleichheitsbedingung, die negative Werte aufweist, mit $-1$ multipliziert. Dort wo sich dann negative Schlupfvariablen ergeben, wird jeweils eine künstliche Variable $y_i$ eingefügt. Diese wird in der Zielfunktion mit $-M$ bewertet, wobei $M$ als hinreichend groß angenommen wird. Die künstlichen Variablen müssen dann aus der Zielfunktion entfernt werden, indem die Nebenbedingungen nach diesen aufgelöst und in die Zielfunktion eingesetzt werden. Danach wird der primale Simplexalgorithmus angewandt. Für die Pivotspalte wird sich dabei in der Zielfunktionszeile an $M$ orientiert, da diese als hinreichend groß angenommen werden. Sind keine negativen Werte in der Zielfunkktion erhalten liegt die optimale Lösung vor.

3. Die Lösung wird in diesem Fall im Optimaltableau nicht auf der rechten Seite abgelesen (wie ohne Dualsierung), sondern bei den Zielfunktionswerten.