Farkas' Lemma < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es seien [mm] A\in\IR^{m\times n} [/mm] und [mm] b\in\IR^{m}.
[/mm]
Zeigen Sie folgende Version des Lemmas von Farkas:
Das System Ax [mm] \le [/mm] b ist unzulässig genau dann wenn gilt
[mm] \exists [/mm] y [mm] \ge [/mm] 0 s.d. [mm] A^{T}y [/mm] = 0 und [mm] b^{T}y [/mm] < 0.
Tipp: Betrachten Sie das LP max{0*x : Ax [mm] \le [/mm] b} und das zugehörige duale Problem. |
Hallo zusammen,
ich komme mit dieser Aufgabe einfach nicht voran.
Ich habs bis jetzt mit dem Tipp versucht:
LP in Standardform: -min{0*x : A'x' = b}
dann dualisieren: -max { [mm] b^{T}\pi^{T} [/mm] : [mm] A'^{T}pi^{T} \le [/mm] 0, [mm] \pi [/mm] >< 0 }
Aber das bringt mich irgendwie nicht wirklich weiter...
Ich hoffe mir kann jemand weiterhelfen.
Vielen Dank schonmal im Voraus.
Gruß Michael
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 24.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
