Kurs:Algorithmen und Datenstrukturen/Vorlesung/Simplex Verfahren Gewinnmaximierung

Aus Wikiversity
Zur Navigation springen Zur Suche springen



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.


verweishttps://de.wikiversity.org/wiki/Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Simplex_Verfahren_Tableau Discussion