Verkürztes Simplex

Jeinie,

ich probier's mal anhand einer Klausuraufgabe (03/2004). Das Augangstableau nach der normalen Methode sieht so aus. Wir brauchen den Zwei-Phasen-Simplex, deshalb gibt es auch eine Spalte x-1.


x-1 x0 x1 x2 x3 s1 s2 z1 Typ RHS
1 0 -2 -1 2 0 1 0 = -40
0 1 4 5 -1 0 0 0 = 0
0 0 3 1 1 1 0 0 = 50
0 0 2 1 -2 0 -1 1 = 40
Der verkürzte Simplex ist jetzt nur eine einfachere Schreibweise desselben Tableaus. Es wird hier nicht wirklich anders gerechnet, sondern es wird nur das Tableau anders aufgeschrieben. Man lässt die Einheitsspalten einfach weg. In einer Spalte vor dem Tableau notiert man dann nur die Reihenfolge der Einheitsspalten (hier: x-1, x0, s1, z1). Die Reihenfolge der Einheitsspalten ergibt sich durch die Position der 1 innerhalb der Einheitsspalte.


x1 x2 x3 s2 Typ RHS
x-1 -2 -1 2 1 = -40
x0 4 5 -1 0 = 0
s1 3 1 1 0 = 50
z1 2 1 -2 -1 = 40
Der nächste Simplexschritt wäre hier Spalte 'x1', Element '3'. In dem ausführlichen Tableau wird dabei die Spalte 'x1' zur Einheitsspalte, während 's1' aus der Basis rausfliegt. Im vereinfachten Simplex-Tableau wird das dadurch verdeutlicht, daß der Spalten- und der Zeilenkopf vertauscht werden:


s1 x2 x3 s2 Typ RHS
x-1 2/3 ... ... ... = -20/3
x0 -4/3 ... ... ... = -200/3
x1 1/3 ... ... ... = 50/3
z1 -2/3 ... ... ... = 20/3
(Ich habe hier nicht alle Werte ausgerechnet) In langer Form sähe das wiederrum so aus:


x-1 x0 x1 x2 x3 s1 s2 z1 Typ RHS
1 0 0 ... ... 2/3 ... 0 = -20/3
0 1 0 ... ... -4/3 ... 0 = -200/3
0 0 1 ... ... 1/3 ... 0 = 50/3
0 0 0 ... ... -2/3 ... 1 = 20/3
So, ich hoffe, ich konnte das etwas klarer machen. Bedenke immer, daß es wirklich nur um eine andere Schreibweise geht -- der Algorithmus bleibt exakt derselbe.

Was strenggenommen noch fehlt, sind die "Spaltentypen", d.h. ob die Spalte frei ist oder nicht. ("<=" oder "-" unter der Spalte im ausführlichen Tableau). Wenn eine Spalte in die Basis kommt, schreibt man das dann dementsprechend vor die Spaltenbezeichnung.

Hier habe ich auch doch so ein paar Probleme, also muss man einfach nur in der langen Form rechnen aber in der kurzen aufschreiben?

SaschaHB schrieb:

Hier habe ich auch doch so ein paar Probleme, also muss man einfach nur in der langen Form rechnen aber in der kurzen aufschreiben?

Zum Vergrößern anklicken....

Genau, so ungefähr. Du musst nur bei der Pivotspalte zwei Sachen anders beachten.

Pivotelement = Kehrwert und die übrigen Werte in der Pivotspalte musst du so berechnen: neuer Wert = - alter Wert/Pivotelement

Den Rest dann in gewohnter Weise. Am anschaulichsten ist es, wenn Du einfach mal die lange Form vorher durchrechnest und anschließend die dann verkürzt rechnest. So ist habe ich es auch endlich kapiert. 🙂

VG
Claudia

Ich habe jetzt gedacht, so wie ich mir das Beispiel von psedi angucke, man kann einfach normal das lange Tableau ausrechnen und dann einfach übertragen, also gar nicht mehr mit dem verkürzten Tableau rechnen.

claudi228 schrieb:

Genau, so ungefähr. Du musst nur bei der Pivotspalte zwei Sachen anders beachten.

Pivotelement = Kehrwert und die übrigen Werte in der Pivotspalte musst du so berechnen: neuer Wert = - alter Wert/Pivotelement

Zum Vergrößern anklicken....

Genau das macht man auch in der Langen Form, und zwar mit der Spalte, die den passenden Einheitsvektor enthält (in meinem Beispiel 's1'). Das ist also keine Sonderbehandlung im verkürzten Tableau, wenn man bedenkt, daß diese Spalte und die Pivotspalte vertauscht werden.

Schau' Dir nochmal aus meinem ersten Posting das letzte Tableau an (langes Tableau nach dem Pivotschritt). Die Spalte 's1' war vorher eine Einheitsspalte. Wenn man die Kreisregel auf die zum Pivotelement passende Einheitsspalte anwendet, kommt dabei genau claudi228's Rechenanweisung raus.

Danke psedi für diesen Hinweis. So kann man es natürlich auch machen. Ich habe mir immer die Mühe gemacht und die Einheitsspalte schön mit der Kreisregel berechnet. So ist es natürlich weniger zeitaufwendig. :cool

Dankeschööööööööön! Enlich verstanden!