Lineare Optimierung < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Huhu,
ich habe die folgende Aufgabe vor mir:
Gegeben ist das folgende primale LOP:
Zielfunktion: [mm] \pi(x)=4x_1+2x_2+2x_3+x_4 \to [/mm] max!
Nebenbedingungen: [mm] x_1+3x_2+x_3 \le [/mm] 20
[mm] x_1-x_2+x_4 \le [/mm] 60+t
mit [mm] x_1,x_2 \ge [/mm] 0 und [mm] t\in \IR.
[/mm]
a) Löse das LOP für t=0 und t=-50 mit dem Simplexalgorithmus.
b) Stelle das zugehörige duale Problem auf und berechne die duale Lösung graphisch.
Zu a):
Also für t=0 habe ich den Simplex gemacht und bekomme dann im letzten Tableaufeld in der oberen Zeile [mm] (\pi [/mm] - Zeile) folgendes:
[mm] \pi|0 [/mm] 6 1 0 3 1|120, wobei die ersten 4 Einträge die Variablen [mm] x_1,...,x_4 [/mm] sind und die übrigen beiden die Schlupfvariablen [mm] s_1 [/mm] und [mm] s_2. [/mm] Als Lösung [mm] \pi_{max} [/mm] bekomme ich hier ja den Wert auf der rechten Seite von 120 raus.
Für t=-50 bekomme ich analog: [mm] \pi|0 [/mm] 2 0 1 2 2 |70
Also ist hier [mm] \pi_{max}=70.
[/mm]
Soweit ist bei mir noch alles klar.
Jetzt zu b):
Ich habe das duale Problem formuliert und graphisch gelöst. Als neue duale Zielfunktion erhalte ich ja: [mm] \pi(y)=20y_1+(60+t)y_2 \to [/mm] min!
In der graphischen Lösung bekomme ich für t=0 den Punkt P=(3;1) als optimalen Punkt und es ergibt sich [mm] \pi_{min}=120. [/mm] Im obigen Tableau (rot markiert) konnte ich den optimalen Punkt für das duale Problem ja auch schon ablesen und es gilt ja auch hier [mm] \pi_{max}=\pi_{min}. [/mm]
Für t=-50 erhalte ich graphisch den optimalen Punkt Q=(2;2). Das stimmt im Tableau ja ebenfalls wieder überein! ABER: setze ich den Punkt in meine duale Zielfunktion ein, erhalte ich ja [mm] \pi_{min}=20*2+(60-50)*2=60?! [/mm] Laut obigen Tableau müsste doch aber 70 rauskommen???
Warum ist das hier nicht [mm] \pi_{max}=\pi_{min} [/mm] ?
Hoffe ich habe mein Problem verständlich genug dargestellt.
|
|
| |
|
Niemand eine Idee? Hat das etwas mit der schwachen Dualität zu tun?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:47 Sa 03.12.2011 | | Autor: | Stoecki |
du hast hier zwei LP's vorliegen. im Optimum müssen die Zielfunktionen immer gleich sein. Die schwache Dualität sagt nur aus, dass der Zielfunktionswert eines maximierungsproblems für alle zulässigen punkte kleiner oder gleich dem zielfunktionswert des dualen ist und es gilt bei lp's die starke dualität. also dass im optimum beide zielfunktionswerte übereinstimmen müssen. in deinem falle heißt das, das du dich irgendwo verrechnet haben musst oder du falsch gezeichnet hast
gruß bernhard
|
|
|
| |
|
Aber wenn ich graphisch den Punkt (3;1) herausbekomme und über das Simplexverfahren ebenfalls, dann ist es doch unlogisch, dass ich mich verrechnet habe :/ Bin die Aufgabe schon x-mal jetzt durchgegangen, finde aber den Fehler nicht...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:23 Mo 05.12.2011 | | Autor: | Stoecki |
poste mal alle deine simplexschritte. dann schaue ich mal drüber. ich vermute du hast dich in der zielfunktion verrechnet. es muss einen rechenfehler geben. sonst wären die werte gleich
gruß bernhard
|
|
|
| |
|
Als ich die Aufgabe gerade nochmal sauber schreiben wollte, habe ich den Rechenfehler endlich gefunden :D
Danke für die Hilfe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Di 06.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Sa 03.12.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
