Degeneriertheit < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei ein lineares Programm im [mm] \IR^2 [/mm] mit A [mm] \in \IR^{mx2}:
[/mm]
min cx
s.t. Ax [mm] \le [/mm] b
[mm] x\ge0
[/mm]
Beweisen Sie: Wenn (LP) (in Standardform) degeneriert ist, dann existiert x' [mm] \in \IR^2, [/mm] das alle m+2 Ungleichungen und mindestens 3 von ihnen mit Gleichheit erfüllt. |
ich verstehe die Aufgabe nicht ganz. Degeneriertheit bedeutet, dass es eine zulässige Basislöung gibt, bei der mindestenes eine der Basisvariablen den Wert 0 hat.
Also wenn es dann eine zulässige Basislösung gibt, die das LP in Standardform erfüllt, dann erfüllt sie ja auch Ax' [mm] \le [/mm] b.
Und somit wären m+2 Ungelichungen erfüllt; das kann es doch nicht alles sein?
(Zur Gleichheit muss ich mir noch was überlegen)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 10.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
