1         Der Simplexalgorithmus

1.1      Maximierungsproblem

Beispiel: Geldanlage

x₁=Festgeldanlage; x₂=Aktienanlage

Restriktionen:

Ziel ist die Maximierung folgender Zielfunktion: G(x)= 0,04x₁ + 0,08x₂ unter o.g. Restriktionen ->0=G-0,04x₁-0,08x₂

Die Restriktionen geben eine Lösungsmenge vor ->die Lösung des Maximierungsproblems liegt auf dem Rand der Lösungsmenge

Darstellung der Lösungsmenge:

Die graphische Lösung erfolgt, indem man Niveaulinien von G einzeichnet, bis sie die Lösungsmenge nur noch tangieren

Rechnerische Lösung:

Aufstellung des Grundtableaus: ->Eintragen der Restriktionen und von G

Basisvariablen: kommen jeweils nur in einer Gleichung vor ->u₁ bis u₄

Nichtbasisvariablen: Rest ->x₁ und x₂

Setzt man die Nichtbasisvariablen 0, kann man die Werte der Basisvariablen ablesen ->u₁=50; u₂=40; u₃=20; u₄=0; G=0 mit x₁ und x₂=0 (1. Ecke der Lösungsmenge)

Als nächstes wird eine neue Basisvariable bestimmt ->es wird der betragsmäßig größte negative Koeffizient der Gewinnfunktion genommen. ->x₂ wird neue Basisvariable.

Nun wird die neue Nichtbasisvariable bestimmt, in dem man alle Konstanten durch den Koeffizienten der neuen Basisvariable dividiert, sofern dieser nicht negativ ist und dann den kleinsten Wert wählt ->hier u₄, da 0/0,12=0.

Im nächsten Tableau können die verbliebenen alten Basisvariablen übernommen werden. Für die neue Basisvariable (x₂) wird die Spalte der neuen Nichtbasisvariable (u₄) eingetragen:

->jetzt wird durch geeignetes Umformen das obere Tableau in das untere Transformiert

Zeile 4 = Zeile 4_alt : 0,12

Zeile 1 = Zeile 1_alt - Zeile 4

Zeile 2  bleibt in diesem Fall erhalten

Zeile 3 = Zeile 3_alt - Zeile 4

Zeile 5 = Zeile 5_alt + 0,08* Zeile 4

Es ergibt sich folgendes Tableau:

->Das Ganze wird wiederholt, bis in der letzten Zeile keine negativen Koeffizienten mehr stehen

Folglich wird als nächstes x₁ Basisvariable und u₁ Nichtbasisvariable.

Das Ergebnistableau hat dann folgende Gestalt:

->jetzt gibt es in der letzten Zeile keine negativen Koeffizienten mehr. Setzt man jetzt die Nichtbasisvariablen 0, kann man die Lösung ablesen
->x₁ = 37,5; x₂=12,5; G=2,5 ->hier liegt das Maximum

Kontrolle durch Einsetzen in die Restriktionsgleichungen.

Mehrdeutige Lösungen:

Wenn eine der Nichtbasisvariablen in der Lösung 0 ist, gibt es unendlich viele Lösungen. Die Lösungen können als Lösungen eines Gleichungssystems gesehen, dass entsteht, wenn man nur die anderen Nichtbasisvariablen 0 setzt und dann das Gleichungssystem aufschreibt.

1.2      Minimierungsproblem

• Die Variablen werden mit y statt mit x bezeichnet
• Zielfunktion = K(Y)
• Zeichnet man die Restriktionsbedingungen in ein Koordinatensystem ein, so gehören alle Punkte oberhalb der Restriktionsbedingungen zur Lösungsmenge
• Graphisches Minimum:
• Festlegung eines Niveaulinie für die Zielfunktion
• Einzeichnen dieser Niveaulinie
• Verschieben der Niveaulinie, bis sie den südlichsten Punkt der Lösungsmenge erreicht hat
• Rechnerische Lösung:
• Die Koeffizientenmatrix der Restriktionen wird transponiert und als neue Restriktionen aufgeschrieben
• Die Konstanten der neuen Restriktionen sind die Koeffizienten von K(y)
• Die neue Zielfunktion ist G(x), wobei die Koeffizienten die Konstanten der alten Restriktionen sind

->die neue Form wird dann nach der Simplex-Methode aufgelöst. Die x-Variablen in der Lösung sind dann die Schlupfvariablen des Minimierungsproblems (v). Die Schlupfvariablen der Lösung sind dann die y-Variablen des Minimierungsproblems.