Simplexverfahren |
| 15.08.2004, 11:08 | lamox79 | Auf diesen Beitrag antworten » | ||
| Simplexverfahren Ich habe zur Zeit ein kleines Problem beim Simplexverfahren. Und zwar lautet die Aufgabe Minimiere P= 9x+5y --> Minimal unter den Nebenbedingungen: 1.) x+3y>= 18 2.) 5x+3y >= 30. Wir haben es so gelernt, dass wir das Dualitätsproblem anwenden sollen, was ich auch gemacht habe. Ich habe dann also: P`= 9x+5y --> maximal Nebenbedingungen: 1`) u+5v<= 9 2`) 3u+3y<= 5 Wenn ich das nun berechne, komme ich zu folgendem Ergebnis. Für v=5/3 wird P=50. Das Ergebnis müsste eigentlich soweit stimmen, aber meine Frage, die ich mir jetzt stelle ist: Was bedeutet das Ergebnis jetzt für die Ausgangsfunktion?! |
||||
| 15.08.2004, 13:16 | therisen | Auf diesen Beitrag antworten » | ||
Hallo lamox79, Ich erhalte als Lösung x=0; y=10. Der minimale Wert von P unter den von dir genannten Bedingungen wäre dann also 50. Ich weiß nicht, was dein v zu bedeuten hat, allerdings weißt du nun, welchen Wert deine Ausgangsfunktion annehmen muss, also 50=9x+5y. Was steht denn in deinen Unterlagen? Gruß, therisen |
||||
| 16.08.2004, 15:47 | lamox79 | Auf diesen Beitrag antworten » | ||
Dein Ergebnis ist schon richtig. Wenn man das Verahren geometrisch löst, sind x=0 und y=10 und P=50 eine Lösung. Es handelt sich aber um eine parallele Niveaulinie, die eine Seite des Polygons schneidet. Es gibt demnach mehrere Lösungen. Wie bist denn du auf die Lösung gekommen? Wenn man nämlich das Dualitätsproblem anwendet, dass erhält man, die zwei Nebenbedingungen mit u und v und erhält dann: v=5/3 und P=50. Das war auch soweit richtig. Steht so zumindestens da. Aber dann stellt sich für mich die Frage, was das mit dem Ausgangsproblem zu tun hat. Das konnte mir bislang keiner so genau beantworten. |
||||
| 16.08.2004, 15:59 | lamox79 | Auf diesen Beitrag antworten » | ||
Nachdem ich das Dualitätsproblem angewendet hab, muss es bei 2´) anstatt "y" natürlich "v" heißen. Also habe ich: 1´) u+5v<= 9 2`) 3u+3v<= 5, da die Spalten und Zeilen vertauscht wurden und ich so von dem Minimalproblem : P= 9x+5y --> Minimal zu dem Maximalproblem: P`) 18u+30v --> Maximal. Die erste Aufgabenstellung war von mir also nicht korrekt notiert. |
||||
| 16.08.2004, 21:31 | therisen | Auf diesen Beitrag antworten » | ||
Hi Lamox79, es stellt sich zunächst die Frage, ob du nur ganzzahlige Lösungen willst oder nicht.
Soll das eine Äquivalenzumformung deiner Ausgangsfunktion sein? Wenn ich 18u+30v unter den Nebenbedingungen u+5v<=9 und 3u+3v<= 5 maximiere, erhalte ich v=1,66..52 und u=0. Ich würde an die Aufgabe zunächst folgendermaßen rangehen: P= 9x+5y --> Minimal P'=-P=-9x-5y --> Maximal Du kannst die Aufgabe mit einem Simplex-Tableau lösen. Schau mal hier, da ist eine sehr ausführliche Erklärung des Simplex-Verfahrens: http://www.matheboard.de/lexikon/index.php/Simplex-Verfahren Gruß, therisen |
||||
| 17.08.2004, 00:46 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Hallo therisen, du scheinst die Dualität, mit der lamox die Aufgabe lösen will/muss nicht zu kennen. @lamox: Wenn du das Dualproblem gelöst hast, hast du schon einmal den optimalen Zielfunktionswert, denn dieser ist dann für das primale und das duale Problem gleich. Wenn du noch den Optimalpunkt benötigst, so kannst du seine Koordinaten auch direkt im Simplextableau des dualen Problems ablesen. Sie stehen an der Stelle der reduzierten Kosten (du musst sie noch mit (-1) multiplizieren, wenn ich mich recht erinnere). Die rechte Seite und die reduzierten Kosten haben quasi den Prozess des Transponierens (Zeilen und Spalten tauschen) mitgemacht. Deswegen entsprechen auch die optimalen Koordinaten, die du fü das Dualproblem gefunden hast den reduzierten Kosten des Primalproblems. Alles klar? Gruß vom Ben Hab´s mal nach Sonstiges verschoben. |
||||
| Anzeige | ||||
|
|
||||
| 17.08.2004, 18:13 | lamox79 | Auf diesen Beitrag antworten » | ||
Danke an beide! Es funktioniert auf beiden Wegen. Lamox |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
