2-Phasen-Simplex-Algorithmus

Silvia77 wrote:

Hallo ihr,
ich habe noch ein paar Probleme mit dem 2-Phasen-Simplex-Algorithmus. Ich weiß, wann ich eine Hilfsvariable und/oder Schlupfvariablen einfügen muss. Aber wie kriege ich dann die Hilfsvariable wieder weg?
Bsp.: Max. 3x1 - 2x2 + x3
u.d.N. x1 + x2 >= 70
2x1 - 4x3 <= 280
x1 + 4x2 + x3 <= 150

Das Tableau müsste meiner Meinung nach wie folgt aussehen:
x0 x1 x2 x3 s1 s2 s3 h1 Typ RHS
1 0 0 0 0 0 0 1 = 0
0 -3 2 -1 0 0 0 0 = 0
0 1 1 0 -1 0 0 1 = 70
0 2 0 -4 0 1 0 0 = 280
0 1 4 1 0 0 1 0 = 150

Stimmt das so und was muss ich jetzt machen?

Viele Grüße
Silvia

Hallo Silvia,

m.E. muss das Ausgangstableau so aussehen, weil du eine Hilfszielfkt. brauchst:

[COLOR=Red]h0[/COLOR] x0 x1 x2 x3 s1 s2 s3 h1 Typ RHS
[COLOR=Red]h0 1[/COLOR] 0 0 0 0 0 0 0 1 = 0
[COLOR=Red]x0 0 1[/COLOR] -3 2 -1 0 0 0 0 = 0
[COLOR=Red] h1 0[/COLOR] 0 1 1 0 -1 0 0 1 = 70
[COLOR=Red]s2 0[/COLOR] 0 2 0 -4 0 1 0 0 = 280
[COLOR=Red]s3 0 [/COLOR]0 1 4 1 0 0 1 0 = 150

als erstes wird die Hilfszielfunktion h0 neu geschaffen - eben um die Hilfsvariable zu eliminieren :).

dazu wird h1 eingesetzt:

[COLOR=Black]h0 x0 x1 x2 x3 s1 s2 s3 h1 Typ RHS
[/COLOR] [COLOR=Black][COLOR=Red]h0 1 0 -1 -1 0 1 0 0 0 = 0[/COLOR]
[/COLOR] [COLOR=Black]x0 0 1 -3 2 -1 0 0 0 0 = 0
[/COLOR] [COLOR=Black] h1 0 0 1 1 0 -1 0 0 1 = 70
[/COLOR] [COLOR=Black]s2 0 0 2 0 -4 0 1 0 0 = 280
[/COLOR] [COLOR=Black]s3 0 0 1 4 1 0 0 1 0 = 150

Dann erst mal Hilfszielfunktion mit Simplex optimieren; wenn Opt. erreicht, dann Hilfszielfkt. und Hilfsvariable streichen = Ende 1. Phase

Dann die Zielfunktion x0 wie gewohnt optimieren.

Hoffe es stimmt so und hilft dir ein bisschen weiter - ist bei mir doch auch schon ein paar Tage her :o...

Das Animationsbeispiel auf der CD zum Kurs ist m.E. auch ein zwei-Phasen-Simplex, schau Dir das am besten mal an :).

[/COLOR]

Kerstin,
ganz vielen Dank für deine ausführlichen Erläuterungen. :) Ich werde es mir genau anschauen und hoffe, dass ich danach keine weiteren Fragen mehr habe.
Viele Grüße
Silvia