von Studenten für Studenten
-
Guten Start ins Wintersemester 2024/2025
Verkürztes Simplex
- Ersteller jeinie
- Erstellt am
P
psedi
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.
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.
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
P
psedi
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.
Weiter lesen
