Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Gewinnmaximierung



Beispiel Gewinnmaximierung

Bearbeiten

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:

 

 

 

 

 

 


 

Initialisierung

Bearbeiten

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

 

   

 

   

Starttableau

Bearbeiten
      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.

Optimierungsphase

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

 

 

 

 

Erste Iteration

Bearbeiten

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 Tableaus

Bearbeiten

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 Iteration

Bearbeiten

 

 

 

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 Tableaus

Bearbeiten

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 Iteration

Bearbeiten

 

 

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 Tableaus

Bearbeiten

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.