4. Simplex-Algorithmus

Simplex-Algorithmus

  • I

    Hallo,

    wenn ich mehrere Simplex-Ungleichungen habe, etwas diese hier:

    Zielfunktion
    max 2x1 + 4x2
    Nebenbedingungen:
    2x1 + 3x2 <= 2000
    3x1 + 5x2 <= 3000

    dann erhalte ich für x2 = 600 als optimale Lösung.

    Nun will ich die Normalform erweitern, indem von x1 mindestens 20 Stück produziert werden müssen: x1 >= 20
    Die Umformung hin zu -x1 <= -20 stimmt ja noch, ich kann damit aber nicht mehr rechnen, denn

    Zielfunktion
    max 2x1 + 4x2
    Nebenbedingungen:
    2x1 + 3x2 <= 2000
    3x1 + 5x2 <= 3000
    -x1 + 0x2 <= -20

    führt weiterhin zu x2 = 600. Damit wurde aber die Bedingung von mindestens 20 Stück x1 nicht beachtet.
    Was mache ich falsch?

    Danke und Gruß!

    0
  • ?

    ich denke, dass der fehler nicht am simplex verfahren liegt. übergibst du dem simplex verfahren die restriktionen korrekt? die richtige lösung wäre vermutlich: x1 = 20, x2 = 588.

    0
  • I

    Leider habe ich keinen Lösungsvorschlag parat. Habe es noch einmal zu Fuß durchgerechnet und benötige nur eine Iteration. Ausgangspivotelement ist die Ziffer "5" in der zweiten Zeile und zweiten Spalte. Die Restriktion >= 20 wird dann aber im Verlauf überhaupt nicht beachtet, Lösung weiterhin laut Endtableau x2 = 600.
    Man muss wohl irgendwie anders vorgehen, leider weiß ich nur nicht, wie. Bin für jeden Rat dankbar. Ich weiß nur, dass man mit einem >=, das man in ein <= umwandelt, die Simplexnormalform verlassen wird.

    Gruß!

    0
  • ?

    Ingo schrieb:

    Leider habe ich keinen Lösungsvorschlag parat. Habe es noch einmal zu Fuß durchgerechnet und benötige nur eine Iteration. Ausgangspivotelement ist die Ziffer "5" in der zweiten Zeile und zweiten Spalte. Die Restriktion >= 20 wird dann aber im Verlauf überhaupt nicht beachtet, Lösung weiterhin laut Endtableau x2 = 600.
    Man muss wohl irgendwie anders vorgehen, leider weiß ich nur nicht, wie. Bin für jeden Rat dankbar. Ich weiß nur, dass man mit einem >=, das man in ein <= umwandelt, die Simplexnormalform verlassen wird.

    Gruß!

    du rechnest das per hand durch? dann schreib doch mal das tableu hier hin. führst du auch phase 1 korrekt durch? bzw. startest du mit einer zulässigen ecke?

    0
  • I

    Ich habe es noch einmal per Hand gerechnet. Unter der Bedingung, dass ich die -1 in der ersten Spalte und dritten Zeile zum Pivotelement machen darf, passt die Lösung: x1=20, x2=588, Gesamtoutput=2.392. Danke für Tritt in meinen ?="§*$§, dass ich es mal mit diesem Start versuche. Ging davon aus, dass man nicht mit -1 starten dürfe.

    Check das jetzt erst einmal für mehrere Tableaus.

    Danke und Grüße!

    Starttableau:

    2  3 | 1 0 0 | 2000
 3  5 | 0 1 0 | 3000
-1  0 | 0 0 1 |  -20
--------------------
-2 -4 | 0 0 0 |    0

    Endtableau:

    0 0 | 1 -3/5 -19/5 |  276
0 1 | 0  1/5   3/5 |  588
1 0 | 0    0   -1  |   20
-------------------------
0 0 | 0  4/5   2/5 | 2392
    0
  • A

    Im Internet und auch in Lehrbüchern findest Du oft Implementierungen des Simplex Algorithmus, die nur funktionieren, wenn alle Werte der Matrix positiv sind...

    Ich vermute, das ist das Problem...

    0
Anmelden zum Antworten