Zielfunktion ändern < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:12 Mi 31.03.2010 | | Autor: | Jana85 |
Hallo,
ich bin gerade am Lernen für Ganzzahlige Optimierung und habe bei einem Beweis ein Verständnisproblem.
Das grobe Problem:
man hat ein c [mm] \in \IR^n [/mm] : max{cx:x [mm] \in [/mm] P} hat eine eindeutige Lösung (Extrempunkt) x* (mit Polyeder P = {x [mm] \in \IR^n [/mm] : Ax <= b} ).
Nun wird argumentiert:
Da x* die eindeutige Lösung des LPs ist, gilt für ein hinreichend großes q [mm] \in \IN,
[/mm]
sodass x* auch eindeutige Lösung von [mm] max((c+1/q*e_j)x:x \in [/mm] P) (mit [mm] e_j [/mm] j.ter Einheitsvektor...)
Wieso dies nun gilt ist mir nicht ganz klar. Der Professor sagte es sei wegen der Stetigkeit der Zielfunktion... Allerdings hilft mir das auch nicht weiter, da man ja nach dem Shift eine komplett andere Zielfunktion hat...
Anschaulich ist mir das schon klar. Die Zielfunktion kann man ein klein wenig "shiften", dann bleibt der Extrempunkt immer noch die einzige Optlsg...
Achja: Ich weiß jetzt nicht ob es irgendwas hierzu beiträgt, aber über das x* weiß man noch, dass die j. Komponente x*_j nicht in [mm] \IZ [/mm] ist!
Ich hoffe ihr könnt mir bei meinem kleinen Verständnisproblem helfen
Vielen Dank im Voraus und Viele Grüße
Jana
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 03.04.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
