Lemma von Farkas < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 21:42 Mo 02.11.2009 | | Autor: | daN-R-G |
| Aufgabe | Überprüfen Sie, für welche a [mm] \in \IR [/mm] das LGS Ax=b mit
A = [mm] \pmat{ 1.5 & e^{\pi} & a & ln(3) & 38 & 7 \\ 0.1 & \sqrt{2} & 1 & e^{-\pi} & 19 & 0 }, [/mm] b = [mm] \vektor{4 \\ 8}
[/mm]
eine Lösung x [mm] \geq [/mm] 0
Hinweis: Verwenden Sie das Lemma von Farkas |
Hallo!
Ich sitze gerade vor dieser Aufgabe, aber weiß noch nicht genau, wie ich ansetzten soll, da ich in der letzten Vorlesung leider gefehlt habe, und somit den Stoff zum Lemma verpasst habe.
Ich habs mal nachgeschlagen, und es lautet ja:
Sei A [mm] \in \IR^{(m, n)}, [/mm] b [mm] \in \IR^m. [/mm] Dann hat entweder das Ungleichungssystem
(I) Ax = b, [mm] x\geq [/mm] 0 (x [mm] \in \IR^n) [/mm] oder
(II) [mm] A^T [/mm] z [mm] \leq [/mm] 0, [mm] b^T [/mm] z > 0 (z [mm] \in \IR^m)
[/mm]
eine Lösung.
Nach dem Hinweis sollen wir ja nun dieses Lemma verwenden.
Gehe ich somit recht der Annahme, dass ich zeigen muss, dass
[mm] A^T [/mm] z [mm] \leq [/mm] 0 , [mm] b^T [/mm] z > 0 keine Lösung besitzt?
Wie würde ich das ganze denn geschickt angehen?
Es gilt ja:
[mm] A^T [/mm] z [mm] \leq [/mm] 0 [mm] \gdw \pmat{ 1.5 & 0.1 \\ e^{\pi} & \sqrt{2} \\ a & 1 \\ ln(3) & e^{-\pi} \\ 38 & 19 \\ 7 & 0 }z \leq [/mm] 0 , (4, 8)z > 0
Aber irgendwie verstehe ich den Ansatz noch nicht so ganz.
Kann mir jemand behilflich sein und mich ein wenig aufklären?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:33 Di 03.11.2009 | | Autor: | barsch |
Hi,
> Überprüfen Sie, für welche a [mm]\in \IR[/mm] das LGS Ax=b mit
> A = [mm]\pmat{ 1.5 & e^{\pi} & a & ln(3) & 38 & 7 \\ 0.1 & \sqrt{2} & 1 & e^{-\pi} & 19 & 0 },[/mm]
> b = [mm]\vektor{4 \\ 8}[/mm]
> eine Lösung x [mm]\geq[/mm] 0
>
> Hinweis: Verwenden Sie das Lemma von Farkas
> Hallo!
>
> Ich sitze gerade vor dieser Aufgabe, aber weiß noch nicht
> genau, wie ich ansetzten soll, da ich in der letzten
> Vorlesung leider gefehlt habe, und somit den Stoff zum
> Lemma verpasst habe.
>
> Ich habs mal nachgeschlagen, und es lautet ja:
>
> Sei A [mm]\in \IR^{(m, n)},[/mm] b [mm]\in \IR^m.[/mm] Dann hat entweder das
> Ungleichungssystem
> (I) Ax = b, [mm]x\geq[/mm] 0 (x [mm]\in \IR^n)[/mm] oder
> (II) [mm]A^T[/mm] z [mm]\leq[/mm] 0, [mm]b^T[/mm] z > 0 (z [mm]\in \IR^m)[/mm]
> eine Lösung.
>
> Nach dem Hinweis sollen wir ja nun dieses Lemma verwenden.
> Gehe ich somit recht der Annahme, dass ich zeigen muss,
> dass
> [mm]A^T[/mm] z [mm]\leq[/mm] 0 , [mm]b^T[/mm] z > 0 keine Lösung besitzt?
Ja, denn dann folgt aus dem Lemma von Farkas, dass System (1) eine Lösung hat.
> Wie würde ich das ganze denn geschickt angehen?
>
> Es gilt ja:
> [mm]A^T[/mm] z [mm]\leq[/mm] 0 [mm]\gdw \pmat{ 1.5 & 0.1 \\ e^{\pi} & \sqrt{2} \\ a & 1 \\ ln(3) & e^{-\pi} \\ 38 & 19 \\ 7 & 0 }z \leq[/mm]
> 0 , (4, 8)z > 0
>
> Aber irgendwie verstehe ich den Ansatz noch nicht so ganz.
>
> Kann mir jemand behilflich sein und mich ein wenig
> aufklären?
Naja, das ist komponentenweise zu verstehen. Sprich:
[mm] \pmat{ 1.5 & 0.1 \\ e^{\pi} & \sqrt{2} \\ a & 1 \\ ln(3) & e^{-\pi} \\ 38 & 19 \\ 7 & 0 }\vektor{z_1 \\ z_2} \leq{0}, [/mm] wenn
[mm] 1.5z_1+0.1z_2\leq{0}
[/mm]
[mm] e^{\pi}z_1+\sqrt{2}z_2\leq{0}
[/mm]
.
.
.
[mm] 7z_1+0z_2\leq{0}
[/mm]
und zudem: (4, 8)z > 0, d.h. [mm] 4*z_1+8*z_2>0.
[/mm]
Jetzt musst du ein a finden, sodass es keine Lösung für dieses System gibt. Ich würde versuchen, ein a zu finden, sodass stets [mm] a*z_1+1z_2>0.
[/mm]
Gruß barsch
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 19:27 Do 05.11.2009 | | Autor: | daN-R-G |
Danke schonmal für deine Antwort!
Irgendwie stelle ich mich gerade noch ungeschickt an, ein solches a zu finden.
Es gilt ja [mm] 4z_1 [/mm] + [mm] 8z_2 [/mm] > 0 [mm] \gdw z_1 [/mm] > [mm] -2z_2 \gdw z_1 [/mm] < [mm] 2z_2 [/mm]
Das muss ja stets gelten.
Wie kann ich denn das ganze mit [mm] az_1 [/mm] + [mm] 1z_2 [/mm] > 0 kombinieren?
Irgendwie wills mir noch nicht ganz einleuchten.
Nehme ich mal an, es gilt a = 0
Dann hätte ich [mm] 0z_1 [/mm] + [mm] 1z_2 [/mm] > 0 , was für beliebiges [mm] z_2 [/mm] nicht gilt
Bei a = 1 ergäbe sich [mm] 1z_1 [/mm] + [mm] 1z_2 [/mm] > 0 , was aber für [mm] z_1 [/mm] <= [mm] -|z_2| [/mm] nie gelten würde.
Hat jemand noch einen Tipp?
Edit:
Ich glaube das stimmt nicht so ganz.
Betrachtet man [mm] 4z_1 [/mm] + [mm] 8z_2 [/mm] > 0 [mm] \gdw z_1 [/mm] + [mm] 2z_2 [/mm] > 0 [mm] \gdw \bruch{1}{2}z_1 [/mm] + [mm] z_2 [/mm] > 0
dann hat man ja eigentlich schon eine Lösung für a = [mm] \bruch{1}{2}
[/mm]
Könnte das stimmen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 07.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
