Entfernen einer inaktiven Nebenbedingung bei LP

Neue Frage »

Schachspieler Auf diesen Beitrag antworten »
Entfernen einer inaktiven Nebenbedingung bei LP
Meine Frage:
Hallo,
ich muss folgendes zeigen:
Sei ein LP gegeben (Maximierungsproblem, nicht notwendigerweise ganzzahlig). Sei nun x* eine Optimallösung und ax<=b eine Nebenbedingung, die in x* nicht mit Gleichheit erfüllt ist, also nicht aktiv ist. Wenn ich diese NB nun entferne, bleibt x* die Optimallösung des (neuen) LP. Warum ist das so?

Meine Ideen:
Dass die Optimallösung nicht kleiner werden kann, ist trivial. Nun möchte ich zeigen, dass sie nicht größer ist. Dazu nehme ich an, die Optimallösung des neuen LP liegt in dem Bereich, der nach Streichen der NB hinzukommt. Dann möchte ich irgendwie dahinkommen, dass die Optimallösung des alten LP dann an einer Ecke liegen müsste, die an diesen Bereich "angrenzt", aber ich weiß nicht wie das geht.
Eine andere Idee war, das duale LP irgendwie ins Spiel zu bringen, aber ich weiß nicht wie.
Hat da jemand eine Idee, wie man das zeigen könnte?
IfindU Auf diesen Beitrag antworten »

Nimm an es gibt eine bessere Lösung welche also die Nebenbedingung verletzt. Zeige, dass für ein geeignetes sowohl eine bessere Lösung als ist als auch die Nebenbedinung erfüllt.
Schachspieler Auf diesen Beitrag antworten »

Ok, vielen Dank, ich denke ich habe nun die Lösung:
Sei x_2 nun optimal und aus dem Bereich, der durch die NB verletzt wird, also Val(x*)<Val(x_2). Wenn man sich nun die Menge der Konvexkombinationen ansieht, wird diese durch die NB geschnitten. Nun kann man lambda groß genug wählen, dass die NB erfüllt ist. Sei dazu lambda entsprechend gewählt. Es folgt:



Dies ist ja dann der Widerspruch. Ist das so richtig?
IfindU Auf diesen Beitrag antworten »

Die Ungleichung gilt nur für . Für ist dort Gleichheit, für ist die Ungleichung sogar anders herum.
Zitat:
Original von Schachspieler


Dies ist ja dann der Widerspruch. Ist das so richtig?


Im Prinzip aber richtig. Beweise, dass ein existiert und du hast das Problem erfolgreich umgangen. Du kannst hier den Zwischenwertsatz benutzen oder das sogar explizit angeben, und dann zeigen, dass es echt zwischen und liegt.
Schachspieler Auf diesen Beitrag antworten »

Ok, also mit dem Zwischenwertsatz zeigt man ja, dass wenn f(x)=ax-b und f(x*)<=0 und f(x_2)>0 dann dazwischen ein x existiert mit f(x)=0. (also ax=b)
Ich arbeite also nun mit diesem x, um mein lambda zu bestimmen, dass zwischen 0 und 1 liegen soll. Ich gehe nun folgendermaßen vor:



Nun muss ich zeigen, dass dieses lambda in (0,1) liegt. Es gilt nun b-ax_2<0, da x_2 die NB verletzt. Also ist der Zähler negativ. Es gilt ax*-ax_2<0, da x* die NB erfüllt und x_2 nicht. Also ist der Nenner auch negativ und lambda somit >0. Nun will ich eigen, dass der Zähler kleiner als der Nenner ist, dann wäre lambda<1. Da gilt aber nun b>=ax*, was zum genauen Gegenteil führt. Wo liegt hier mein Fehler?
IfindU Auf diesen Beitrag antworten »

Es ist .

Da gilt, gilt .
 
 
Schachspieler Auf diesen Beitrag antworten »

Ah ok, jetzt sehe ich es auch. Vielen Dank für die Hilfe.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »