Lineares Optimierungsproblem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:22 Mi 26.05.2010 | | Autor: | side |
| Aufgabe | Gegeben sei das Optimierungsproblem
max [mm] x_1+x_2
[/mm]
[mm] x_1+\bruch{1}{2}x_2\le1
[/mm]
[mm] x_1+2x_2\le2
[/mm]
a) Sei [mm] M=\{(0,0); (1,0); (2,0); (\bruch{1}{2},\bruch{1}{2}); (\bruch{2}{3}, \bruch{2}{3})\} [/mm]
Welche [mm] (X_1,x_2)\in\M [/mm] sind zulässig für das Problem?
b) Bestimmen sie das duale lineare Programm
c) Geben sie eine Lösung des dualen linearen Programms an
d) Welche der Elemente von M sind optimale Lösungen für das ursprüngliche Problem? |
zu a) einfach einsetzen [mm] \Rightarrow [/mm] (2,0) ist als einziges nicht zulässig, oder?
zu b) Ich komm mit der Difinition davon noch nciht so zurecht. Wenn mir jemand hier weiterhilft, hab ich mal ein Beispiel und blick dann vllt besser durch
zu c) hängt ja dann von b ab...
zu d) [mm] (\bruch{2}{3},\bruch{2}{3}) [/mm] ist optimal, da die Summe der beiden Einträge hier am größten ist, oder?
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:40 Fr 28.05.2010 | | Autor: | side |
Ich hab mich jetzt weiter damit beschäftigt.
Das Problem lässt sich umschreiben in
min [mm] \vektor{-1 \\ -1}^T*\vektor{x_1 \\ x_2}
[/mm]
mit
[mm] \vmat{ -1 & -\bruch{1}{2} \\ -1 & -2 }*\vektor{x_1 \\ x_2}\ge\vektor{-1 \\ -2}
[/mm]
Das hat dann das duale Programm:
min [mm] y_1+2y_2
[/mm]
mit [mm] y_1+y_2\ge1
[/mm]
[mm] \bruch{1}{2}y_2+2y_1\ge1
[/mm]
Dieses hat für mich die optimale Lösung [mm] (\bruch{2}{3}, \bruch{1}{3})
[/mm]
Ist das dann schon alles?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:56 Fr 28.05.2010 | | Autor: | abakus |
> Ich hab mich jetzt weiter damit beschäftigt.
> Das Problem lässt sich umschreiben in
> min [mm]\vektor{-1 \\ -1}^T*\vektor{x_1 \\ x_2}[/mm]
> mit
> [mm]\vmat{ -1 & -\bruch{1}{2} \\ -1 & -2 }*\vektor{x_1 \\ x_2}\ge\vektor{-1 \\ -2}[/mm]
>
> Das hat dann das duale Programm:
> min [mm]y_1+2y_2[/mm]
> mit [mm]y_1+y_2\ge1[/mm]
> [mm]\bruch{1}{2}y_2+2y_1\ge1[/mm]
> Dieses hat für mich die optimale Lösung [mm](\bruch{2}{3}, \bruch{1}{3})[/mm]
>
> Ist das dann schon alles?
Die richtige Lösung ist schon [mm] (\bruch{2}{3};\bruch{2}{3}).
[/mm]
Siehe Skizze:
Blaue Fläche: erlaubter Bereich (ich habe mich mal auf den 1. Quadranten beschränkt).
Grüne Linien: Geraden mit [mm] x_1+x_2=k
[/mm]
Blaue Linie: hat von allen Linien durch den erlaubten Bereich (oder durch einen Randpunkt) das größte k.
[Dateianhang nicht öffentlich]
Gruß Abakus
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:21 Fr 28.05.2010 | | Autor: | nikinho |
ich glaube beim aufstellen das linearen programms hast du dich vertan.
ich habe da min [mm] yT*\vektor{1 \\ 2} [/mm] s.d. yT * [mm] \pmat{ 1 & 1/2 \\ 1 & 2 } [/mm] = [mm] \vektor{1\\ 1}
[/mm]
so steht das mMn auch bei uns in der vorlesung!
da kommt dann auch 2/3 2/3 raus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:23 Fr 28.05.2010 | | Autor: | dormant |
Hi!
Dein primales Problem ist von der Form
max [mm] c^{T}x
[/mm]
unter
[mm] Ax\le [/mm] b, [mm] x\ge [/mm] 0.
Das duale davon lautet
min [mm] b^{T}y
[/mm]
unter
[mm] A^{T}y\ge [/mm] c, [mm] y\ge [/mm] 0.
Du brauchst dann dein primales Problem nicht umzuformen, sondern direkt in Vektor-Matrix schreibweise formulieren, transponieren nicht vergessen und das Duale aufstellen.
Wie du sicher weißt, müssen die Lösungen der beiden Programme übereinstimmen, also es muss (2/3, 2/3) rauskommen.
Grüße,
dormant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:23 Fr 28.05.2010 | | Autor: | nikinho |
Ich habe eine Frage wie die Menge M zu verstehen ist.
Ist M die Menge dieser 5 Punkte im [mm] R^2 [/mm] oder ist M sozusagen die Menge, wenn man die Punkte verbindet (also alle Punkte darin)?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:55 Sa 29.05.2010 | | Autor: | dormant |
Hi!
So wie sie geschrieben ist, ist sie als die fünf einzelnen Punkte zu verstehen.
Man wird später beweisen, dass in gewissem Sinn, die optimale Lösung sowieso "am Rand" ist, also reicht es, im 2-dimensionalen, die Eckpunkte der zulässigen Menge zu betrachten.
Wie man auch gesehen hat, ist die Lösung gerade so ein Eckpunkt (d.h. beide Ungleichungen werden zu Gleichungen in diesem Punkt).
Grüße,
dormant
|
|
|
|
