Frage zum Simplexverfahren

ich versuchs mal, hoffentlich ist verständlich was ich meine:


schlupfvariablen fügst du zu (all) den nebenbedingungen die mit "<="
angegeben sind , hier nb 1 und 2

für nebenbedingen mit werten >= fügst du eine negative schlupfvariable -s hinzu und
ein hilfsvariable w in der hilfszeile phase1 um diese wieder auszugleichen; (kommt hier nicht vor)

für nebedingung mit negativen werten multipliziertst du mit *-1, tauscht also die Vorzeichen (kommt hier nicht vor)

für nebenbingungen mit werten =, hier nb 3 fügst du nur eine hilfsvariable
hinzu w1 und gleichst diese in der hilfszeile (zeile Phase 1 über dem optiemierungsproblem)

die drei variablen s1, s2, w1 ergeben so den Einheitsvektor und helfen das problem zu lösen
wie du aus der ersten tabeleau1 gut siehst
s1: 1 0 0
s2: 0 1 0
w1: 0 0 1

standardform:
max....-2.x1.-5.x2..................-w1.....( durch -w1 in der hilfszeile Phase 1 gleichst du die hilfsvariabel aus)
unter....2.x1.+2.x2.-x3.+s1..........=5..(durch s1 wird aus <= 5, = 5)
......................x2.+x3.....+s2......=5..( (durch s1 wird aus <= 5, = 5)
...............x1.+.x2.+x3..........+w1=1 (w1 gibt dir hier den fehlenden vektor für die einheitsmatrix)

du hast in phase 1 also eine zusatzszeile über dem maximierungsproblem mit -w
und eine oder mehr zusatzspalten mit +w für die Hilfsvariablen,
wenn du in der zusatzszeile überall - werte hast ist phase 1 beendet, du streichst und
vergisst die hilfsweise und spalte und machst mit dem normalen simplexalgorithmus weiter.

klingt verwirrend, hoffe wiederholtes lesen macht klar war gemeint ist 😉

Sascha

Vielen Dank für die verständliche Erklärung!

Wie bestimme ich das Pivotelement? Insbesondere bei einem 2-Phasen Simplex?

Irgendwie habe ich das Gefühl, dass das in den Klausurlösungen nicht nach einer bestimmten Regel erfolgt. Gibt es denn so eine Regel?

Ich hatte z.B. hier auf meiner Zusammenfassung stehen "Um die Spalte zu bestimmen, sucht man das größte Element aus der Zielfunktion". Jedoch wurde das z.B. bei "1142LK08 Aufgabe 12" nicht so gemacht.

Wenn ich die Spalte habe, ist es einfach die Zeile zu bestimmen: Man teilt einfach die Zahl ganz rechts durch die jeweilige Zahl in der Zeile und schaut, welches Element am kleinsten ist (Negative Zahlen ausgeschlossen).

Das Problem liegt eher daran: Wie ist die Regel, um die richtige Spalte zu bestimmen?

Wenn wir schon dabei sind: Kann jemand vielleicht noch erklären, welches Vorgehen nun Blands Rule ist und welche Alternative es dazu gibt.

Ich bin über jede Hilfe dankbar!

Ich gehe gerade nochmals die KS07 Klausur durch, die ich vor ein paar Wochen mal bearbeitet hab:
Aufgabenstellung:
max 2x1 + x2
unter 2x1 + 3x2 <= 24
-x1 + x2 >= 3
x1,x2 >= 0

Daraus folgt:
0 0 0 0 | -1 | 0
2 1 0 0 | 0 | 0
2 3 1 0 | 0 | 24
-1 1 0 -1 | 1 | 3

Also die letzte Zeile ist die Zeile mit der künstlichen Schlupfvariable. Diese addieren wir jetzt zur ersten Zeile:

-1 1 0 -1 | 0 | 3
2 1 0 0 | 0 | 0
2 3 1 0 | 0 | 24
-1 1 0 -1 | 1 | 3

So jetzt zu deiner eigentlichen Frage: Die Schlupfvariable bekommen wir immer mittels Bland's Rule. Die macht das ganze meiner Meinung nach auch einfacher. Bland's Rule sagt aus, dass die Schlupfvariable immer in der ersten Spalte zu suchen ist! Also stellt sich normalerweise nur die Frage nach der Zeile. ABER: Das gilt nur, wenn in der obersten Zeile (diese nennt man künstliche Zielfunktionszeile), in der Spalte eine Ziffer >= 1 drinnen steht. In der ersten Spalte haben wir das nicht!!! Da die -1 ja nicht größer oder gleich 1 ist. Also suchen wir laut Bland's Rule in der zweiten Spalte ein Pivotelement. So ist es nun 3 oder 1 ??? Dass geht mittels "minimalem Koeffiziententest". Wir rechnen:
24 / 3 = 8
3 = 1 = 3

(Also die 24 bzw. 3 ist immer der Eintrag der letzten Spalte).
Da das Ergebnis 3 kleiner ist als das Ergebnis 8, ist das Pivotelement in dieser Zeile. Und das war die 1. Also ist die oben rotmarkierte Ziffer 1 das Pivotelement.
Übrigens: Ein Pivotelement darf keine NEGATIVE Ziffer sein.

So jetzt teilen wir die Zeile, in der sich das Pivotelement befindet, durch das Pivotelement. Dann wird dass Pivotelement eine 1. Das ist hier natürlich sinnlos, da das Pivotelement bereits eine 1 ist.

Ich hoffe deine Frage ist dadurch geklärt.

Für alle anderen erklär ich noch weiter:
Jetzt benötigen wir in der Spalte, in der sich auch das Pivotelement befindet, über alle eine 0.Die grünen Zahlen müssen also eine 0 werden (passt auf, es steht hier nicht alles sauber untereinander)
-1 1 0 -1 | 0 | 3
2 1 0 0 | 0 | 0
2 3 1 0 | 0 | 24
-1 1 0 -1 | 1 | 3

So wie kriegt man die erste Zeile, also die grüne 1 zu einer 0. Und dass geht immer gleich:

Zeile mit dem grünen betroffenen Element
-
Zeile mit dem roten Pivotelement

Immer geht das natürlich nicht. Stellt euch vor, die grüne 1 wäre eine grüne 3. Dann wiefolgt (mehr darf nie machen):

Zeile mit dem grünen betroffenen Element
-
(3*) Zeile mit dem roten Pivotelement.

Und anstatt der 3* benötigt man manchmal eine 5* oder manchmal halt auch ein -2*. Und so weiter.

In unserem Fall rechnen wir lediglich:

Zeile mit dem grünen betroffenen Element
-
(1*) Zeile mit dem roten Pivotelement.


Und dann macht man mit der zweiten und der dritten Zeile weiter. Die Spalte der vierten Zeile muss keine 0 werden, da in dieser bereits dass Pivotelement vorhanden ist.

Dann kommt folgendes raus:
0 0 0 0 | -1 | 0 Wir rechneten 1. Zeile - (1*) 4. Zeile, um aus der obrigen grünen 1 eine 0 zu bekommen
3 0 0 -1 | -1 | -3 Wir rechneten 2. Zeile - (1*) 4. Zeile, um aus der obrigen grünen 1 eine 0 zu bekommen
5 0 1 3 | -3 |15 Wir rechneten 3. Zeile - (3*) 4. Zeile, um aus der obrigen grünen 3 eine 0 zu bekommen
-1 1 0 -1 | 1 | 3 Abschreiben, da in dieser Zeile das Pivotelement sich befindet.

Nun sind wir aus 2 Gründen "glücklich".

Grund 1: In der ersten Zeile, also der künstlichen Zielfunktionszeile, stehen keine Werte mehr >=1, also alle sind 0 oder kleiner.
Grund 2: Die Stelle, wo sich die blaue Ziffer befindet, ist eine 0. Dass heisst, der Zielfunktionswert ist eine 0.

Da beide Gründe korrekt sind, streichen wir nun die künstliche Zielfunktionszeile und künstliche Zielfunktionsspalte:

Wir haben dann:
3 0 0 1 | -3
5 0 1 3 | 15
-1 1 0 -1 | 3

Bland's Rule sagt uns wie oben: Pivotelement befindet sich in 1. Spalte. Hier tatsächlich 1. Spalte, da 3 nicht gleich oder kleiner 0.

Pivotelement ist die 5. Kann nur die 5 sein, da der Gegenkandidat eine Minuszahl ist. Die -1 kann deshalb kein Pivotelement sein.

Wir teilen die Pivotzeile durch das Pivotelement, sodass die Pivotzeile wiefolgt lautet:

1 0 1/5 3/5 | 3.

Nun muss die -1, in der 3. Zeile eine 0 werden. (wie oben ja auch). Das machen wir in dem wir folgendes machen:

3. Zeile minus (-1) * Pivotzeile (also die fettgedruckte, bereits durch 5 geteilte Pivotzeile)

Und nun muss die 3 in der ersten Zeile eine 0 werden. 1. Zeile -3* Pivotzeile.

Nun haben wir als Ergebnis:

0 0 -3/5 -4/5 |-12
1 0 1/5 3/5 | 3
0 1 1/5 -2/5 | 6

Jetzt benötigen wir für x1 und x2 das jeweilige Ergebnis.

Die 1. SPALTE liefert uns das Ergebnis für x1 und die zweite SPALTE das Ergebnis für x2.
Wir suchen also, dass Ergebnis für x1 (vorausgesetzt in der obersten Zeile der jeweiligen Spalte steht eine 0. Das ist hier bei x und y der Fall. Falls eine Minuszahl dasteht, ist das Ergebnis für das jeweilige x oder y immer 0). In der 1. SPALTE suchen wir eine 1. (Wenn man keine 1 findet, ist das Ergebnis 0). Wir finden eine 1. Und diese 1 deutet auf die 3 hin. Also (x1= 3)

Wir suchen also, dass Ergebnis für x2. In der 2. SPALTE suchen wir eine 1. (Wenn man keine 1 findet, ist das Ergebnis 0). Wir finden eine 1. Und diese 1 deutet auf die 6 hin. Also (x2= 6)



Ich hoffe ihr versteht das. In einem Forum das zu erklären, ist recht schwierig. Ich habs durch das tolle Mentoriat in München verstanden.

Vielen Dank, Stefan! Das ist die beste Erklärung, die ich bis jetzt gelesen habe!

Eine Nachfrage (nur um jeden Fehler auszuschließen):

Ich beziehe mich auf folgende Stelle in deinem ersten Post:

-1 1 0 -1 | 0 | 3
2 1 0 0 | 0 | 0
2 3 1 0 | 0 | 24
-1 1 0 -1 | 1 | 3

So jetzt zu deiner eigentlichen Frage: Die Schlupfvariable bekommen wir immer mittels Bland's Rule. Die macht das ganze meiner Meinung nach auch einfacher. Bland's Rule sagt aus, dass die Schlupfvariable immer in der ersten Spalte zu suchen ist! Also stellt sich normalerweise nur die Frage nach der Zeile. ABER: Das gilt nur, wenn in der obersten Zeile (diese nennt man künstliche Zielfunktionszeile), in der Spalte eine Ziffer >= 1 drinnen steht. In der ersten Spalte haben wir das nicht!!! Da die -1 ja nicht größer oder gleich 1 ist. Also suchen wir laut Bland's Rule in der zweiten Spalte ein Pivotelement.

Zum Vergrößern anklicken....

Was wäre nun, wenn die Simplex Tabelle so aussieht:

1 1 0 -1 | 0 | 3
-1 1 0 0 | 0 | 0
2 3 1 0 | 0 | 24
-1 1 0 -1 | 1 | 3


(lila sind die geänderten Zahlen).
Nach deinem Prinzip, schaue ich mir nun die erste Spalte an und sehe, dass sie positiv ist. Also kann ich nun als Pivotelement die 2 in der ersten Spalte nehmen, richtig?

Oder gilt die Regel, das ich die Spalte nicht nehmen darf, auch, wenn die echte Zielfunktionszeile ein Minus hat? (hier lila -1)

Vielen Dank nochmal für Deine Hilfe!

Richtig, also:

1. Spalte nehmen. Es geht um die künstliche Zielfunktionszeile. Die ist eine 1. Also musst du nach Bland's Rule die 1. Spalte nehmen. Wir nehmen nur die 2. Spalte, der Wert der künstlichen Zielfunktionszeile der ersten Spalte bereits 0 oder kleiner 0 ist.

Also müssen wir nur unterscheiden, in welcher ZEILE sich das Pivotelement befindet. Das machen wir mittels "minimalem Koeffiziententest".
24 /2 = 12
3 / -1 = HALT, wegen dem negativen Vorzeichen kann das kein Pivotelement sein.
Also hat es sich geklärt. 2 ist Pivotelement.

Einen ganz speziellen Fall gibt es noch. Der tritt in der Aufgabe 12 in der KW10 auf.
Da gibt es an einer bestimmten Stelle einmal ein folgendes Tableau:
X Y Z S1 S2 S3

0 1 3 0 -1 0 | -3
0 2 5 1 -1 0 | 2
1 1 1 0 1 0 | 3
0 1 2 0 -1 1 | 1

So hier muss sich das Pivotelement in SPALTE 2 befinden, da in der 1 Zeile eine 0 bereits in der 1. Spalte steht.

Minimaler Koeffiziententest ergibt:
2/2 = 1
3/1 = 3
1/ 1 = 1


Nun, was machen wir jetzt? Dürfen wir nun selbst entscheiden??? Also nach Bland's Rule NICHT!
Entweder 2. Zeile oder 4. Zeile. Die dritte Zeile kann es wegen der 3 nicht sein, da 3 > 1.
Nun müssen wir uns die Schlupfvariablen ansehen. Die zweite Zeile hat eine 1 stehen bei S1
Die 4. Zeile hat bei S1 eine 0 stehen und erst bei S3 eine 1.
Da die 1 bei den Schlupfvariablen in der 2. Zeile eher kommt, wird die 2. Zeile Pivotelement.

Also Pivotelement ist die 2.

Klasse! Vielen Dank für deine Mühe!

bitte bitte.

ganz dickes virtuelles Kudos an Dich!
Ich habe seit Tagen weder bei YouTube, im Web, in den Kurseinheiten noch sonstwo eine Erklärung gefunden, die mich den zweiphasigen Simplex durchschauen lies...
Du bist der erste, der es so dargelegt hat, dass ich den Weg verstanden habe! Und das pünktlich vor der Klausur morgen...!
Sollten wir uns irgendwann mal im realen Leben treffen, gebe ich Dir ein Bierchen aus 🙂

Vielen Dank! Von solch engagierten Leuten lebt eine Community wie diese hier!!!
Dennis

freut mich. das mim Bierchen merk ich mir 😉 ich schreib übrigens in München

Ich in Bochum... Viel Glück wünsch ich Dir!

achso. Dann werds wohl nichts mit meim Bierchen gleich morgen 😉 Dir auch.

tolle Anleitung! Eine Frage habe ich jedoch; wie komme ich auf die Werte in der künstlichen Zielfunktionsspalte bzw. Zeile? (zu Anfang)