Lineare Optimierung Dualität < Sonstiges < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich hab da mal wieder ein Problem und freu mich über Tips!
Ich soll dies hier mittels Dualität graphisch lösen/minimieren [mm] x_1 + 5x_2 + 3x_3 + 6_4[/mm] unter den Nebenbedingungen [mm]-2x_1 + 2x_2 + x_3 + x_4 \ge 2[/mm] und [mm]x_1 - 4x_2 - x_3 +2x_4 \ge 3 [/mm] wobei gilt [mm] x_1, x_2, x_3, x_4 \ge 0 [/mm]
Dies habe ich jetzt in ein Maximierungsproblem umgewandelt:
[mm]2y_1 + 3y_2[/mm] unter Nebenbedingungen [mm]-2y_1+y_2\le1[/mm],[mm]2y_1-4y_2\le5[/mm],[mm]y_1-y_2\le3[/mm],[mm]y_1+2y_2\le6[/mm] wobei [mm]y_1,y_2 \ge0[/mm]
Ich habe das dann gezeichnet und bin auf die optimalen Werte [mm]y_1 = 4[/mm] und [mm]y_2 = 1[/mm] gekommen. [mm] 2y_1 + 3y_2 = 11[/mm]
Wie bekomme ich jetzt eine Aussage über die [mm] x_1, x_2, x_3, x_4[/mm]?
|
|
| |
|
Hallo!
> Ich soll dies hier mittels Dualität graphisch
> lösen/minimieren [mm]x_1 + 5x_2 + 3x_3 + 6_4[/mm] unter den
> Nebenbedingungen [mm]-2x_1 + 2x_2 + x_3 + x_4 \ge 2[/mm] und [mm]x_1 - 4x_2 - x_3 +2x_4 \ge 3[/mm]
> wobei gilt [mm]x_1, x_2, x_3, x_4 \ge 0[/mm]
>
> Dies habe ich jetzt in ein Maximierungsproblem
> umgewandelt:
> [mm]2y_1 + 3y_2[/mm] unter Nebenbedingungen
> [mm]-2y_1+y_2\le1[/mm],[mm]2y_1-4y_2\le5[/mm],[mm]y_1-y_2\le3[/mm],[mm]y_1+2y_2\le6[/mm] wobei
> [mm]y_1,y_2 \ge0[/mm]
>
> Ich habe das dann gezeichnet und bin auf die optimalen
> Werte [mm]y_1 = 4[/mm] und [mm]y_2 = 1[/mm] gekommen. [mm]2y_1 + 3y_2 = 11[/mm]
>
>
> Wie bekomme ich jetzt eine Aussage über die [mm]x_1, x_2, x_3, x_4[/mm]?
Optimierung ist bei mir schon ziemlich lange her. Aber ich versuche mich mal an Deiner Frage. Zunächst mal fällt mir zu dem Problem der Satz vom komplementären Schlupf ein. Zum primalen Problem gehören ja eigentlich noch [mm]x_5, x_6[/mm], die den Schlupf in den Nebenbedingungen angeben, also:
[mm]-2x_1 + 2x_2 + x_3 + x_4 +x_5 = 2[/mm] und
[mm]x_1 - 4x_2 - x_3 +2x_4 + x_6 = 3[/mm].
Genauso machst Du das auch im dualen Problem mit Schlupfvariablen
[mm]y_3, ...,y_6[/mm]. Dann sagt der Satz, dass bei einer optimalen Lösung das Produkt aus Strukturvariablen im primalen Problem und entsprechenden Schlupfvariablen im dualen Problem immer 0 ist (und umgekehrt). Also hier
[mm]x_1\cdot y_3=x_2\cdot y_4=x_3\cdot y_5=x_4\cdot y_6=0[/mm]
und
[mm]y_1\cdot x_5=y_2\cdot x_6=0.[/mm]
Bei Deinem Probkem bekommst Du also sowohl aus [mm] y_1 [/mm] und [mm] y_2 [/mm] als auch
aus den Schlupfvariablen [mm] y_3 [/mm] bis [mm] y_6 [/mm] Informationen über die optimale Lösung des primalen Problems. Letztere erhältst Du übrigens, indem Du Differenzen zwischen rechter und linker Seite der Nebenbedingungen
[mm]-2y_1+y_2\le1[/mm],
[mm]2y_1-4y_2\le5[/mm],
[mm]y_1-y_2\le3[/mm],
[mm]y_1+2y_2\le6[/mm]
bildest (wobei jeweils Deine Lösung zum dualen Problem eingesetzt wird).
Ich hoffe, das hilft zunächst mal weiter. Falls dann noch Probleme auftauchen, melde Dich noch mal.
Gruß
Brigitte
>
>
|
|
|
|
