Simplex Algorithmus - freie Strukturvariable und eine gesperrte Schlupfvariable

Question

Schönen

Woran erkenne ich wann freie Strukturvariable und eine gesperrte Schlupfvariable vorliegt, beim Optimierungsprobleme?

Ich habe hier diese zwei Optimierungsprobleme:

Woran erkenne ich das P₁ eine reie Strukturvariable hat und P₂ eine  freie Strukturvariable und eine gesperrte Schlupfvariable?

Ich wäre auch sehr verbunden, wenn ihr mir weiterhelfen könntet. Vielen Dank im Voraus.

Answer 1

Hm,

mir sind diese Begrifflichkeiten noch nicht untergekommen. Müsstest Du selber was dazu sagen, wo/wie definiert und wie umgesetzt.

Grundsätzlich fehlt in beidem Programmen eine Aussage zu x1 und in beiden Programmen sind NICHT Standard Nebenbedingungen zu erkennen, die behandelt werden müssen. Standard Programme gehen aber auch immer mit der Nichtnegativitätsbedingung zusammen.

Die gesperrte Schlupfvariable könnte auf die Gleichung bezogen sein, entweder man lässt sie weg oder setzt sie konstant =0 - da darf ja nix schlupfen.

Vielleicht sollte ich nach ergänzen, was mein CAS zu P2 sagt

minimize_lp(-2*x1-3*x2-4*x3,[
    x1 + 2*x2 + 2*x3 <= 45,
    0*x1 + 2*x2 + x3 >=20,
    -x1 + x2 + x3 =30,
    x2>0,x3>0]
), nonegative_lp=true;

Problem not feasible!

Comments

Erstmal Danke für deine Antwort.

freie Strukturvariable := Freie Variablen müssen zur Basisvariablen werden und dort verbleiben! Sie werden im Tableau mit einem grünen Rahmen gekennzeichnet.

gesperrte Schlupfvariable := Deshalb ist der erste Schritt, dass man die gesperrte Schlupfvariable zu einer NBV macht und dort belässt! Das zugehörige Pivotelement kann eine reelle Zahl ungleich Null sein. Eine Basisvariable darf diese gesperrte Schlupfvariable nicht mehr werden, d.h. die zugehörige Spalte darf keine Pivotspalte mehr werden. Die gesperrten Schlupfvariablen werden im Tableau mit einem blauen Rahmen gekennzeichnet.

Das Tableau sieht wie folgt aus:

P1

P2

Hoffe das hilft dir weiter. Falls noch unklar ist, lass es mich wissen, damit ich es besser beschreiben kann.

---

Deine Tableau-Schreibweise ist mir auch nicht geläufig. Ich komm für P1 auf

Es wird zwar erklärt wie mit einer freien Variablen verfahren wird, aber nicht wie man die freie Variable bestimmt.

Vermutung:
Freie Variablen wären demnach x1,x2 - die müssen zur Basis wandern  - das wären dann die, die originär im Ungleichungssystem des LP vorhanden sind.

Könnte es sein, dass man für jedes Tableau neu die freie Variable bestimmt - also die Variable welche man in diesem Schritt zur Basisvariablen macht?

Die gesperrte Schlupfvariable ist die der Gleichung - so wie ich mir das gedacht habe.

---

Nachtrag zu P2: Nach dem unter der Nichtnegativitätsbedingung nix geht, muss wohl x1 ins Negative gehen dürfen. Das kann ich mit einem handoptimierten Simplex hinbekommen - ich erstelle ein duales Programm Min:

und setze an den kritischen Stellen m2/m4 auf händisch vergebene Pivots. Damit komm ich auf ein Ergebnis. Wie sieht bei eurem Tableau ein Min-Programm aus?