Zusammenfassung: Maximierungsproblem

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

1. Das gegebene Maximierungsproblem muss in die Standardform umgeformt werden (Kleiner/Gleich-Nebenbedingungen, Nichtnegativtitätsbedingung). Die Umformungsregeln lauten:

• 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 \le b_i$ und $-a_{i1}x_1 - ... - a_{in} x_n \le -b_i$.
  
  
• Aus einer $\ge$-Ungleichung wird eine $\le$-Ungleichung durch Multiplikation der gesamten Ungleichung mit $-1$.

2. Das Problem 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. 

3. 

• 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 Simplexalgothmus 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.