Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Gewinnmaximierung



Beispiel GewinnmaximierungBearbeiten

Auf dieser Seite wird der Simplex Algorithmus anhand des Beispiels der Gewinnmaximierung Schritt für Schritt durchgegangen.

Zielfunktion:  .

Nebenbedingungen:

 

 

 

 

 

Das System lässt sich umschreiben zu:

 

 

 

 

 

 


 

InitialisierungBearbeiten

Gestartet wird mit der Basislösung, die durch die Schlupfvariable gegeben ist.

 

   

 

   

StarttableauBearbeiten

      b
z 1 6 13 0
  1 0 0 200
  0 1 0 300
  1 1 1 400
  0 1 3 600

  sind Nichtbasiselemente, Z ist die Zielfunktion und   sind Basiselemente.

OptimierungsphaseBearbeiten

      b
z 1 6 13 0
  1 0 0 200
  0 1 0 300
  1 1 1 400
  0 1 3 600

 

 

 

 

Erste IterationBearbeiten

Heuristik: Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt.

 

 

 

 

Hier wird die Zeile von   betrachtet und die Spalte von  . Der alte Wert ist 0. Der Koeffizient von x in der Zielfunktion ist 1 und der Zugewinn durch   ist 200.

 

 

 

 

 

Hier wird die Zeile von   betrachtet und die Spalte von  . Der alte Wert ist 0. Der Koeffizient von   in der Zielfunktion ist 6 und der Zugewinn durch   ist 1800.

 

 

 

 

Hier wird die Zeile von   betrachtet und die Spalte von  . Der alte Wert ist 0. Der Koeffizient von   in der Zielfunktion ist 13 und der Zugewinn durch   ist 2600. Nun wird   durch   ersetzt.

Update des TableausBearbeiten

Der neue Wert von   wird nun berechnet.

 .

Dieser Wert wird nun eingesetzt.

 

 

 

Das neue Tableau sieht nun so aus:

      b
z 1     -2600
  1 0 0 200
  0 1 0 300
  1     200
  0     200

Was haben wir nun gemacht? Von der Basis   haben wir zu der Bais   gewechselt und zu der neuen Basis haben wir das entsprechende Tableau bestimmt.

 


         


 


 


 

Zweite IterationBearbeiten

 

 

 

Heuristik: Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt.

 

 

 

 

Hier wird die Zeile von   betrachtet und die Spalte von  . Der alte Wert ist 2600. Der Koeffizient von   in der Zielfunktion ist 1 und der Zugewinn durch   ist 200.

 

 

 

 

 

Hier wird die Zeile von   betrachtet und die Spalte von  . Der alte Wert ist 2600. Der Koeffizient von   in der Zielfunktion ist 6 und der Zugewinn durch   ist 1800. Nun wird   durch   ersetzt.

Update des TableausBearbeiten

Der neue Wert von   wird nun berechnet.

 . Dieser Wert wird nun eingesetzt.

 

 

 

Das neue Tableau sieht nun so aus:

      b
z 1     -3100
  1 0 0 200
  0 1 0 300
  1     0
  0     100

Dritte IterationBearbeiten

 

 

Ersetze einen Basisvektor durch den Nichtbasisvektor, der den größten Zugewinn für die Zielfunktion bringt. Es müssen nur Terme aus z mit positivem Vorzeichen betrachtet werden, d.h. es bleibt nur noch   übrig.

 

 

 

 

Update des TableausBearbeiten

Nun wird   durch   ersetzt.

 . Dieser Wert wird nun eingesetzt.

 

 

Das neue Tableau sieht nun so aus:

      b
z -1 -1 -4 -3100
  -1     200
  0 1 0 300
  1     0
  0     100

Die Zielfunktion kann nun nicht weiter verbessert werden. Unser x ist nun (0,300,100) und unser z ist 3100.