Lösung des dualen Problems < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Min [mm] -300x_1 [/mm] - [mm] 500x_2
[/mm]
s.t.
[mm] x_1+2x_2 \leq [/mm] 170
[mm] x_1+x_2 \leq [/mm] 150
[mm] 3x_2 \leq [/mm] 180 |
Ich habe das obere Problem mit dem Simplex-Tableu gelöst. Es handelt sich um das Beispiel aus Wikipedia (Simplexverfahren). Die Lösung lautet
[mm] x^{*} [/mm] = (130,20) mit Wert -49000.
Das zugehörige duale Problem habe ich wie folgt formuliert...
Max [mm] 170y_1+150y_2+180y_3
[/mm]
s.t.
[mm] y_1+y_2 \leq [/mm] -300
[mm] 2y_1+y_2+3y_3 \leq [/mm] -500
Nun weiß ich jedoch nicht, wie man das duale Problem lösen kann. Mit Gleichsetzen der Bedingungen (um eine Randlösung zu finden), und auflösen nach [mm] t:=y_1 [/mm] ergibt sich eine Lösung
[mm] y^*=(t,-300-t,-\bruch{200}{3}-\bruch{1}{3}t), [/mm] was nach Einsetzen in der Zielfunktion -40t-57000 ergibt.
Da [mm] y\in R^3 [/mm] gilt, gibt es keine weiteren Einschränkungen für [mm] y_1, [/mm] bzw. t. Aus diesem Grund ist die Lösung [mm] +\infty.
[/mm]
Schränke ich t [mm] \geq [/mm] 0 ein (warum auch immer), so erhalte ich den Maximalwert -57000, was der Lösung des primalen Problems widerspricht.
Gemäß der Dualitätssätze müsste allerdings der Zielfunktionswert im Optimum beider Probleme identisch sein, also -49000.
Ich bin schon mal für Tipps und Anregungen dankbar,
Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:27 Mo 07.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
