Farkas Lemma < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweise die folgende Aussage:
Auf das Ungl.system Ax [mm] \le [/mm] b trifft genau eine der Aussagen zu:
1) [mm] A*x\leb [/mm] hat eine zulässige Lösung x*
2) es existiert ein Vektor y mit
[mm] y\ge0, y^T*A=0^T, y^T*b<0 [/mm] |
Hallo,
der Beweis, dass 1 gilt und 2 nicht, den verstehe ich.
Aber, dass 2 gilt und 1 nicht, den bekomme ich nicht hin und habe da im Skript nur folgendes zu stehen:
Ist 1 falsch und somit A*x [mm] \le [/mm] b nicht lösbar, so folgt die Existenz eines [mm] y\ge0, [/mm] das 2 erfüllt, aus dem Fourier-Motzkin Verfahren.
Kann mir da jemand was zu sagen, wie ich das angehe oder warum das folgt?
Danke.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:29 Fr 30.07.2010 | | Autor: | martin2 |
Hallo,
erstmal vorweg:
es genügt nicht zu zeigen, dass aus 1 nicht 2 und aus 2 nicht 1 folgt. Wenn nämlich 1 nicht gilt, dann ist 2 beliebig, d.h. wenn 2 auch nicht gilt, gilt keins von beiden.
Du kannst zuerst zeigen, dass beide nicht gleichzeitig gelten können:
Annahme 1 und 2 würden gelten:
0 = [mm] y^{T}Ax \le y^{T}b [/mm] < 0
Was ein Widerspruch ist.
Nun reicht es zu zeigen dass aus der Nichgültigkeit des einen die Gültigkeit des anderen folgt (1 Beweis). Hier habe ich aber auch keine schöne Lösung parat
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 05.08.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
