Lineares Optimierungsproblem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich hab ein Problem mit einer Operations Research Aufgabe und zwar genau gesagt, mit einem Linearen Optimierungsproblem.
Also es geht um folgende Aufgabe:
max [mm] F(x_{1}, x_{2}) [/mm] = - 30 [mm] x_{1} [/mm] - 20 [mm] x_{2}
[/mm]
unter den Nebenbedingungen:
[mm] 8x_{1}+3x_{2} \ge [/mm] 240
-4 [mm] x_{1}-4 x_{2} \le [/mm] -220
[mm] 2x_{1}+6 x_{2} \ge [/mm] 210
und [mm] x_{1}, x_{2} \ge [/mm] 0
Überführen Sie das angegebene LP-Modell in Normalform und lösen Sie dieses im Anschluss mit Hilfe des primalen Simplex Algorithmusl. Benutzen Sie gegebenenfalls den dualen Simplex-Algorithmus.
So okay, nun zu meinem Problem, was bereits im ersten Tableau anfängt 
Also zuerst hab ich die erste und die dritte Nebenbedingung geändert:
[mm] -8x_{1}-3x_{2} \le [/mm] -240
[mm] -2x_{1}-6 x_{2} \le [/mm] -210
So und nun kann ich das erste Tableau aufstellen. Also mir ist klar, dass ich den dualen SA anwenden muss, weil ich - 240, -220 und - 210 habe und das positiv sein muss.
Das Problem ist aber, dass ich in meiner oben gezeigten Zielfunktion nur negative Vorzeichen habe und durch den Vorzeichenwechsel, den ich beim Aufstellen des ersten Tableaus vornehmen muss, nur positive Einträge habe. Somit wäre ja das Stopp-Kriterium erreicht.
Gibt es bei diesem LOP vielleicht gar kein Optimum?
Ich wäre echt über jede Hilfe dankbar.
Liebe Grüße,
Vanessa
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Moin Vanessa,
> Überführen Sie das angegebene LP-Modell in Normalform und
> lösen Sie dieses im Anschluss mit Hilfe des primalen
> Simplex Algorithmusl. Benutzen Sie gegebenenfalls den
> dualen Simplex-Algorithmus.
> Gibt es bei diesem LOP vielleicht gar kein Optimum?
Also ich habe das mal eben durchgerechnet, und bin nach der 3.Iteration durch primalen Simplexalgorithmus auf ein Tableau gekommen, das sich folgendermaßen darstellt:
x1 x2 s1 s2 s3 RHS
x1 1 0 -0,2 0,15 0 15
s3 0 0 0,8 -2,1 1 60
x2 0 1 0,2 -0,4 0 40
Z 0 0 2,0 3,5 0 -1250
Wie du siehst, kann man durch drei Iterationsschritte zu einem Endtableau gelangen, welche die Schattenpreise signifikant verändert. Du hast grundsätzlich Recht, das bereits im Starttableau das formale Stopp-Kriterium erreicht ist, aber es ist trotzdem noch nicht optimal, weil wie gesagt die Schattenpreise (je nach Aufgabe z.B. Inputmengen o.ä.) noch nicht optimiert sind.
Liebe Grüße
Analytiker
![[lehrer]](/images/smileys/lehrer.gif "[lehrer]")
|
|
|
| |
|
Hallo,
also, danke schon mal, aber irgendwie hilft mir das noch nicht so ganz weiter. Das Problem ist, wie ich von meinem Startableau weiterrechne. Unser Prof meinte in der letzten Vorlesung halt, dass wir zuerst den dualen Simplex anwenden müssen, damit -240, -220 und -210 positiv werden. Aber selbst dann hab ich ja immer noch positive Einträge in der Zielfunktion und ich weiß nicht, wie ich damit rechnen soll. Da ich ja eigentlich die Pivotspalte so auswähle, dass ich die negativste Zahl aus der Zielfunktion nehme. Und ich find so jetzt einfach kein Pivotelement, wenn alle Einträge positiv sind.
Und ohne Pivotelement kann ich auch keinen Simplex
Danke schon mal im Voraus.
Liebe Grüße,
Vanessa
P.S. Und ich verstehe nicht so ganz, was du mit Schattenpreisen meinst...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:36 So 25.11.2007 | | Autor: | piet.t |
Hallo,
so richtig fit bin ich in diesen ganzen Tableau-Simplex-Verfahren nicht, aber ein paar allgemeine Hinweise zur Problematk dieser Aufgabe kann ich vielleicht geben. Du hast mit der Aufgabe ja zwei Probleme:
1.) Deine Startlösung erfüllt bereits die Optimalitätsbedingung des primalen Simplex, aber
2.) die Lösung ist primal nicht zulässig (sie verletzt die primalen Retstirktionen).
Das ist aber ein klassischer Fall für den dualen Simplexalgorithmus, denn Punkt 1.) von oben bedeutet, dass die zugehörige duale Lösung zulässig ist, 2.) sagt aber auch, dass sie keine optimale Lösung des dualen Problems ist.
Fazit: mit dem primalen Algorithmus wie Du es versucht hast wirst Du nicht allzu weit kommen, denn dieser verlangt ja eine zulässige Startlösung, die wir aber nicht haben (also müsste man erst eine Phase-1 durchlaufen, um eine zu finden), aber mit dem dualen Algorithmus kann man direkt loslegen, da hier ja eine zulässsige Lösung bekannt ist.
Gruß
piet
|
|
|
| |
|
Naja, das hab ich ja gemacht. Ich hab den dualen angewendet (wegen -240, -220, -210) und hatte dann nach 3 Tableaus positive Werte dort. ABER: Das änderte ja nichts an den Vorzeichen der Zielfunktion, die immernoch positiv waren. Damit wäre dann aber sofort das Stopp-Kriterium erreicht...
Und ich weiß nicht, wie es dann weiter geht, bzw. ob das überhaupt richtig ist.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:45 Mo 26.11.2007 | | Autor: | piet.t |
> Naja, das hab ich ja gemacht. Ich hab den dualen angewendet
> (wegen -240, -220, -210) und hatte dann nach 3 Tableaus
> positive Werte dort. ABER: Das änderte ja nichts an den
> Vorzeichen der Zielfunktion, die immernoch positiv waren.
> Damit wäre dann aber sofort das Stopp-Kriterium
> erreicht...
> Und ich weiß nicht, wie es dann weiter geht, bzw. ob das
> überhaupt richtig ist.
Das ist gerade der Knackpunkt am dualen Simplex-Algorithmus: während des gesamten Algorithmus bleibt Deine Zielfunktion so, dass das Stopp-Kriterium zieht - denn das primale Stopp-Kriterium ist ja gerade das duale Zulässigkeitskriterium. Also: ist deine Lösung dual zulässig (und das soll sie im dualen Simplexalgorithmus immer sein), dann ist für den primalen das Stopp-Kriterium erreicht. Wenn Du nun nach drei dualen Simplexschritten eine primal zulässige Lösung erreicht hast, dann hast Du damit auch schon die optimlae Lösung gefunden - primale Simplexschritte sind nicht mehr nötig.
Hilft das?
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:41 Di 27.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
