Degenerierte Basislösung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Betrachten Sie das folgende lineare Programm (LP):
max [mm] 3x_{1} [/mm] + [mm] 4x_{2}
[/mm]
s.d. [mm] 2x_{1} [/mm] + [mm] x_{2} \le [/mm] 8
[mm] -x_{1} [/mm] + [mm] 2x_{2} \le [/mm] 6
[mm] x_{1} [/mm] + [mm] x_{2} \le [/mm] 6
[mm] x_{1} [/mm] , [mm] x_{2} \ge [/mm] 0.
Lösen Sie (LP) graphisch.Ist die optimale Basislösung degeneriert? |
Hallo zusammen,
ich hab das LP graphisch gelöst und bekomme nun als optimale Basislösung x=(2,4) heraus.
Nun weiß ich leider nicht genau, wann die BL degeneriert ist.
Eigentlich ist sie doch degeneriert, wenn ein x-Wert = 0 ist, oder?
Dies wäre hier doch nicht der Fall...
Allerdings schneiden sich in x=(2,4) 3 Geraden der Nebenbedingungen, und somit ist doch eine NB redundant...
Und ist nicht dann eine BL auch degeneriert?
Ich hoffe ihr versteht mein Problem und könnt mir weiterhelfen...
Vielen Dank schonmal im Voraus.
Gruß Michael
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:59 Do 12.11.2009 | | Autor: | piet.t |
Hallo,
> Hallo zusammen,
>
> ich hab das LP graphisch gelöst und bekomme nun als
> optimale Basislösung x=(2,4) heraus.
...das bekommt mein LP-solver auch raus, sieht also schon mal gut aus.
>
> Nun weiß ich leider nicht genau, wann die BL degeneriert
> ist.
> Eigentlich ist sie doch degeneriert, wenn ein x-Wert = 0
> ist, oder?
Ich würde eher sagen: wenn eine Basisvariable gleich 0 ist. Dazu gehören allerdings auch die Schlupfvariablen. Bei der vorliegenden Lösung sind alle drei Schlupfvariablen gleich 0 (da alle Nebenbedingungen mit Gleichheit erfüllt sind). Da es in diesem Problem nur zwei Nichtbasisvariablen gibt muss also eine Variable in der Basis gleich null sein.
> Dies wäre hier doch nicht der Fall...
> Allerdings schneiden sich in x=(2,4) 3 Geraden der
> Nebenbedingungen, und somit ist doch eine NB redundant...
> Und ist nicht dann eine BL auch degeneriert?
Ganz genau.
Gruß
piet
|
|
|
|
