simplex-Algorithmus

Wo genau liegt denn Dein Problem mit dem Simplex-Algorithmus?

Beim Aufstellen der (Un-) Gleichungen?
Beim Aufstellen des Ausgangstableaus?
Beim Ausrechnen des Optimaltableaus?
Oder bei dessen Interpretation?

Es gab zum Dimplex mal eine Übungsklausuraufgabe mit Lösung. Damit habe ich es (spätestens) ganz gut verstanden.

Sven

@ svenuni
Hab ich gesehen wollte die aber erst ansehen und rechnen wenn ich das aus dem Skript verstanden haben


@michel 81
das Aufstellen der Gleichungen ist kein Problem (Skript Seite 19)
ebenso das Aufstellen des Ausgangstableau (Abb.16 Seite 19)

Ich habe es so verstanden die Basisvariablen sind Yp,Ym,Ya,Yb,Yc

Nach "Skript Seite 20 1.Absatz Satz :.. dies sind die Schlupfvariablen y. " verließen sie mich.

Ich kann mir einige Dinge logisch erklären aber ich verstehe nicht was die machen um die Pivotspalte und -zeile zu ermitteln und damit auch nicht die weitern Rechenwege.

Die Interpretaion verste ich zum Teil, hoffe der Rest erklärt sich für mich, wenn ich den Rechenweg verstanden habe.

Grüße
Susanne

Entschuldige, dass ich erst jetzt antworte!

Um das Pivotelement zu ermitteln, gehst du folgender Maßen vor:

- Zunächst ermittelst du die Pivotspalte, indem du den größten Wert in der Zielfunktion ermittelst (in dem Bsp. aus dem Skript ist das die 3, siehe Seite 20 Abb. 17).

- Dann ermittelst du die Pivotzeile, indem du alle Werte, welche in der Spalte RS (rechte Seite) stehen durch die entsprechenden Werte in der Pivotspalte teilst (im Bsp.: 1.900,00 / 4 = 475 etc.) und schreibst die Ergebnisse in die Q-Spalte. Die Pivotzeile ist nun diejenige, welche den kleinsten Q-Wert "besitzt".

- Das Pivotelement findest du jetzt im Schnittpunkt von Pivotspalte und -zeile.

So, dann gehts zum Umformen:

- Jetzt musst du das Pivotelement zu einer 1 umformen (im Bsp. ist es ja bereits eine 1, also einen Schritt gespart).

- Nun formst du alle anderen Elemente in der Pivotspalte zu einer 0 um, indem du in allen Zeilen in welchen noch keine 0 steht ein Vielfaches von der Pivotzeile addierst bzw. subtrahierst. Hoffe das war verständlich. In dem Bsp. aus dem Skript musst du also in der 1. Zeile rechnen: 4 - 4 * 1 = 0. Natürlich musst du das nicht nur für diese Zelle machen, sondern für alle. Die subtrahierst quasi 4 mal die Pivotzeile von der ersten Zeile.
Entsprechend machst du es für alle anderen Zeile auch, so dass in der Pivotspalte nur noch das Pivotelement (= 1) und ansonsten nur noch Nullen stehen.

- Nun suchst du das nächste Pivotelement und fängst wieder von vorne an.

- Das ganze geht dann so lange, bis in der Zielfunktion keine positiven Zahlen mehr stehen. Dann nämlich ist das Tableau optimal.

Hoffe, ich konnte dir helfen. Falls nich, frag nochmal, werd versuchen es etwas verständlicher zu erklären 🙂


Edit: Noch was Wichtiges vergessen:

Wenn Du mit dem Umformen fertig bist, musst du die Basisvariable in der ersten Spalte ändern. Im Bsp. ausm Skript wird dann aus dem yB das xB!

Ich bedanke mich auch für diese Erläuterung.

Michel,

danke, jetzt habe auch ich es verstanden.🙂🙂🙂

@ all

Bei mir haben sich hierzu zwei Fragen ergeben
was mache ich, wenn z.B.: der Db bei zweien gleich ist und ich keine eindeutige Pivospalten erhalte
oder
was mache ich, wenn der Q-Wert bei zweien gleich groß ist, und ich keine eindeutige Pivotzeile erhalte?

Dank und Gruß
Susanne

Bei zwei gleich hohen Zielfunktionswerten ist es völlig egal, welche Spalte Du zuerst nimmst.

Theoretisch müsste man auch nicht den höchsten Wert zuerst nehmen, nur kommt man damit schneller zum Ziel und spart sich die eine oder andere Iteration. Am Ende landet man - sofern korrekt gerechnet - immer im Optimaltableau.