OR Simplex Algorithmus mit Schlupfvariablen

Neue Frage »

keuper Auf diesen Beitrag antworten »
OR Simplex Algorithmus mit Schlupfvariablen
Meine Frage:
Hallo!

folgendes LP Modell in Standartform gilt es mittels Simplex zu optimieren

Zielfunktion:
max=1200x1+800x2+1100x3
NB:
10x1+4x2+4x3<=3000
5x1+4x2+6x3<=1800

Mein Problem ist die Behandlung der NB mit Schlupfvariablen. Die Anzahl der Schlupfvariablen entspricht doch der Anzahl der NB (?). Von daher müsste ich doch 2 Schlupfvariablen in jeder NB einfügen. Allerdings kann ich dann doch für mindestens einen xi Wert keinen Wert über das Tableau ablesen. Ich suche jetzt nach dem richtigen Ansatz für das Ausgangstableau des Simplex.

Bei 2 xi Werten in der ZF und entsprechend 2NB komme ich auf die Lösungen, kein Problem aber wie verhält es sich bei der obigen mit 3 xi Variablen und 2 NB?


Meine Ideen:
Mein Ansatz:
Z:
1200x1+800x2+1100x3+0y1+0y2 ->max
NB: (yi = Schlupfvariable i)
10x1+4x2+3x3+1y1+0y2=3000
5x1+4x2+6x4+0y1+1y2=1800

Das Modell haben wir mit Lindo gelöst (gleicher Ansatz nur ohne die Schlupfvariablen in den Angaben), die Werte sind: x1=240, x2=150 und x3=0. Es braucht 3 Iterationen zur Lösung aber ich komme leider nicht darauf.
Kasen75 Auf diesen Beitrag antworten »

Hallo,

ich habe auch mit Lingo die Lösung berechnet.

Bei Ganzzahligkeit der Variablen hat Lingo folgendes heraus:



Zielfunktionswert:

Wenn ich die Bedingung der Ganzzahligkeit fallen lasse, dann hat Lingo folgendes heraus:












Zielfunktionswert:

Hier hat Lingo drei Iterationen gebraucht. Die Anzahl der Iterationen ist aber nicht so wichtig. Es kommt ja auch auf die Einstellungen an.

Jetzt habe ich mit dem Simplex-Verfahren gerechnet. Hier habe ich 2 Iterationen gebraucht um auf die nicht-ganzahlige Lösung von Lingo zu kommen.

Fang einfach mal an das Simplex-Tableau aufzustellen. Die Zielfunktionswerte gehen erstmal negativ ins Tableau ein. Der kleinste Zielfunktionskoeffizient ist dann -1200. Somit hast du schonmal die Pivotspalte.

Da ist die erste Zeile die Pivotzeile.

Somit ist die 10 das Pivotelement.

Grüße.
keuper Auf diesen Beitrag antworten »

Bin auf die Lösung gekommen, habe aber andere Werte als Du rausbekommen. Die Werte sind die, die ich vom Prof bekommen habe. Scheint also zu passen.

Hier meine Lösungswege mit Lindo und per Hand mit Simplex.

Anhang: Lindo1: Eingabe der ZF und NB

Anhang: Lindo2: Lösung

Anhang: Ausgangstableau: Ausgangstableau mit Simplex
Anhang: Lösungsweg: Lösungsweg mittels Simplex. ;-)

Danke für die Denkanstöße!

Sorry für die seltsame Anordnung der Anhänge, klappt irgendwie nicht anders. (oder ich bin zu doof) verwirrt
Kasen75 Auf diesen Beitrag antworten »

Ich hatte mich vertippt und das bei meiner eigenen Rechnung übernommen. Es sind in der Tat 408.000 bei der Zielfunktion. Insofern passt dein Ergebnis.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »