Ganzzahlige Optimierung Gegenbeispiel convexe Hülle ist Polyeder

Neue Frage »

MiniVie Auf diesen Beitrag antworten »
Ganzzahlige Optimierung Gegenbeispiel convexe Hülle ist Polyeder
Meine Frage:
Mir stellt sich eine Frage zu dem folgenden Gegenbeispiel.
Wir schauen uns:

an.

Mir ist klar, dass das Supremum in diesem Fall nicht angenommen werden kann, sonst würde folgen .

Jetzt will man aber an diesem Beispiel zeigen, dass die konvexe Hülle der zulässige Menge, bezeichne ich mit S, kein Polyeder ist.

Im Skript steht .
Dann wird argumentiert, dass conv(S) kein Polyeder sein kann, da sonst die Optimallösung angenommen werden muss und somit sqrt(2) rational wäre.

Hierzu habe ich jetzte ein paar Fragen. Die erste Gleichung besagt, eigentlich nur dass die ganzzahlige Lösung z*=0 das Supremum der Ganzzahligen Lösungen ist. Bis dorthin kein Problem. Dann besteht wohl die Überlegung darin, dass man sich nun die konvexe Hülle von S anschaut, weil man argumentieren will, dass wenn man eine konvexe Hülle bildet keine Optimallösungen dazukommen können, weil normalerweise im R keine weiteren Ecken dazukommen, oder? Aber wenn ich die konvexe Hülle von etwas bilde, kann diese Hülle doch "wieder" reell werden. Bsp: Punkte und , konvexe Hülle ist [1,2], hier ist zB wieder sqrt(2) enthalen (oder muss das Skalar aus dem gleichen Grundkörper kommen?

Warum kann zum einen jetzt bei Umstellung von S auf conv(S) das Maximum betrachtet werden? Und selbst wenn das geht, was sagt mir, dass die Mengen für die Optimallösung gleich sind. Es kann doch genauso sein, dass durch das reell werden von S nach conv(S) eine Optimallösung nun gefunden werden kann, die aber nicht in S liegt.

Mir ist klar, dass man damit argumentieren will, dass wenn die Gleichung gilt, man sagt, dass wenn conv(S) ein Polyeder wäre, die Optimallösung in einer Ecke angenommen werden würde (Vorteil von Optimierung über Polyedern).

Die große ungeklärte Frage für mich ist, warum die Lösungen von conv(S) und S gleich seien sollten, obwohl in conv(S) viel mehr Punkte sind, bzw. warum der optimale Punkt von conv(S) in S liegen sollte.

Vielen Dank im Voraus







Meine Ideen:
Neue Frage »
Antworten »



Verwandte Themen

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