Simplex Algorithmus

Der Simplex-Algorithmus, oder auch Simplexverfahren genannt, ist eine Möglichkeit lineare Ungleichungen zu lösen und dessen Maximum anzugeben.

Meist habt ihr dann eine Zielfunktion und Bedingungen wie folgt gegeben:

• Zielfunktion: 
• z=c₁x₁+c₂x₂+c₃x₃+d
• Bedingungen:
• a₁₁x₁ + a₁₂x₂ + a₁₃x₃ ≤ b₁
• a₂₁x₁ + a₂₂x₂ + a₂₃x₃ ≤ b₂
• a₃₁x₁ + a₃₂x₂ + a₃₃x₃ ≤ b₃

Achtung: Wichtig ist, dass das es immer kleiner-gleich b ist und nie größer-gleich b!! Wenn nicht muss umgeformt werden. (Siehe Beispiel unten)

Mit diesen Werten erhält man dann diese Tabelle:

Habt ihr nun alle Angaben und ihr sollt das Maximum des Ungleichungssystems bestimmen, dann geht ihr so vor (Beschriftung wird aus der Tabelle darüber verwendet, ihr könntet andere Buchstaben haben):

1. Tragt alles in die Tabelle ein
2. Jetzt muss das Pivot-Element bestimmt werden. Das geht so: Schaut, ob bei RS (rechte Seite/Spalte) mindestens einer der Werte (b) negativ ist. 
• Wenn alle positiv sind, dann guckt ihr, welches das kleinste negative c in der unteren Zeile ist. Dort ist dann eure Pivot-Spalte. Um nun das Pivot-Element zu bestimmen, teilt ihr das jeweilige b durch die Zahl der Pivot-Spalte, welches in derselben Zeile ist (b:a). In der Zeile, wo der kleinste Wert rauskommt, ist das Pivot-Element. (Beispiel Schritt 4)
• Wenn eines oder mehrere Werte b negativ sind, wählt ihr das kleinste negative Element aus (falls nur eines da ist, dann halt dieses). In der Zeile, in der diese Zahl ist, ist die Pivot-Zeile. Das Pivot-Element ist dann die negative Zahl in der Pivot-Zeile. (Sollte es mehrere negative Zahlen in der Pivot-Zeile geben, könnt ihr euch selbst für eines entscheiden.) (Beispiel Schritt 2)
3. Habt ihr das Pivot-Element, müsst ihr alle Elemente in der Pivot-Spalte auf 0 bringen, außer das Pivot-Element selber. (Beispiel Schritt 3)
4. Jetzt beginnt ihr wieder von Anfang, bis kein b und kein c mehr negativ ist. Dann seid ihr fertig. Das d ist dann das Maximum. (Beispiel Schritt 7)

Man hat gegeben:

• Zielfunktion:
• z=2x₁+x₂
• Bedingungen:
• x₁+x₂ ≥ 3      ->  -x₁-x₂ ≤ 3
• 3x₁ ≤ 2x₂+9  ->  3x₁-2x₂ ≤ 9
• x₂ ≤ 6
• x₁ und x₂ ≥ 0

Wenn ihr alles richtig umgeformt habt, tragt alles in eure Tabelle ein. (Siehe Schritt 2)

• Geht wie oben beschrieben vor. Da hier eine negative Zahl in der rechten Spalte ist, ist dort die Pivot-Zeile (wären dort mehrere negative Zahlen, dann muss man die Kleinste negative nehmen).
• Das Pivot-Element [-1] ist dann die negative Zahl in der Pivot-Spalte. Hier gibt es 2 Stück, dann könnt ihr euch frei für ein Pivot-Element entscheiden. 

• Jetzt formt ihr so um, dass bis auf das Pivot-Element alle Zahlen in der Pivot-Spalte 0 sind. Dazu nehmt ihr eine Zeile mal eine Zahl und dann plus oder minus eine andere Zeile, sodass das jeweilige Element in der Pivot-Spalte 0 wird. 
• Hier wurde z.B. die Pivot-Zeile mal -3 genommen und dann plus die 2. Zeile. So wird aus der 3 in der Pivot-Spalte eine 0. 

• Wie ihr seht, ist in der untersten Spalte immer noch ein negatives Element, deshalb seid ihr noch nicht fertig. 
• Bestimmt das nächste Pivot-Element. Da in der rechten Spalte alle Elemente positiv sind, guckt ihr euch die in der untersten Zeile an. Das kleinste negative Element (hier -2) gibt die Pivot-Spalte vor. 
• Dann teilt ihr die Zahlen der letzten Spalte durch die jeweiligen Zahlen der Pivot-Spalte. Das kleinste positive Ergebnis gibt die Pivot-Zeile und so auch das Pivot-Element an. Die Ergebnisse sind hier:
• • 1. Zeile: 3/-1=-3. Das Ergebnis ist negativ, wird also nicht beachtet.
  • 2. Zeile: 0/3=0 Ist das kleinste Ergebnis, also dort ist die Pivot-Zeile.
  • 3. Zeile: 6/0 geht nicht! Man darf nicht durch 0 teilen, also wird das Ergebnis auch nicht berücksichtigt. 

• Jetzt formt ihr so um, dass bis auf das Pivot-Element alle Zahlen in der Pivot-Spalte 0 sind.

• Immer noch gibt es eine negative Zahl in der letzten Spalte, daher das Ganze noch einmal.
• Also Pivot-Spalte bestimmen, durch kleinste negative Zahl, dann Zahlen der rechten Spalte durch die jeweiligen Zahlen der Pivot-Spalte teilen, kleinstes positives Ergebnis gibt die Pivot-Zeile an.

• Das Ergebnis habt ihr dann, wenn alle Zahlen in der unteren Zeile und rechten Spalte positiv sind. 
• Das Ergebnis ist dann ganz unten rechts, hier 20.
• x₁ ist dann 7 (könnt ihr ablesen, indem ihr in der Zeile, in der bei der x₁-Spalte die 1 steht, guckt welche Zahl dort in der rechten Spalte steht.)
• x₂ ist dann 6 (könnt ihr genauso wie x₁ bestimmen.)
• Ihr könnt auch noch überprüfen, ob ihr richtig gerechnet habt, indem ihr x1 und x2 in die Zielfunktion einsetzt und guckt, ob das selbe rauskommt, wie unten rechts im Eck:
• z=2x₁+2x₂ = 2·7+6 = 20 ✓