Konvexität der optimalen Lösungsmenge eines linearen Programms

Neue Frage »

calyton Auf diesen Beitrag antworten »
Konvexität der optimalen Lösungsmenge eines linearen Programms
Hi,


ihr habt mir alle schon sehr viel weiter geholfen, auch das nutzen der SUCHEN-Funktion hat viele Fragen geklärt.

Vor kurzem hatte ich ein Prep abgegeben und dies jetzt zurückbekommen und war doch recht ernüchtert, vorallem weil es keine Anmerkungen dazu gab....


Deswegen bitte ich um Hilfe folgender Aufgabe (bei der ich 12 von 20 Punkten abzug erhalten habe....dabei dachte ich, dass ich die Konvexität komplett bewiesen hatte)

Hier die Aufgabe:



"Zeigen Sie, dass die optimale Lösungsmenge X* eines linearen Programms





konvex ist."


Hier meine (unvollständige Lösung):

---------------
1. Schritt: Konvexität zeigen:











Da

und



Folgt:




Damit ist Konvexität (des ersten Schritts) gezeigt.

--------------------
2. Schritt: Konvexität zeigen:








Da
, , , ,

ist Konvexität (des zweiten Schritts) gezeigt.

-------------------


So und jetzt hab ich 12 Punkte abgezogen bekommen, weil ich vergessen hätte im dritten Schritt
zu zeigen, dass gilt.


Entweder ist das zu trivial, dass ich den Baum vor lauter Wald ;P nicht sehe, oder ich versteh das wirklich nicht.



Freue wie immer über jede Hilfestellung
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Zitat:
Original von calyton
"Zeigen Sie, dass die optimale Lösungsmenge X* eines linearen Programms





konvex ist."


Hier meine (unvollständige Lösung):

---------------
1. Schritt: Konvexität zeigen:











Da

und



Folgt:




Damit ist Konvexität (des ersten Schritts) gezeigt.


Mir fällt ziemlich schwer zu verstehen, was du da machst. Deine Gleichung oben ist doch nicht konvex, sondern die Menge der opt. Punkte soll es sein!

Dann taucht plötzlich ein z auf, was nicht definiert ist, und am Schluß folgt aus der Behauptung die Behauptung? Möglicherweise meinst du ja das Richtige, aber ich stecke schon hier fest.

Grüße Abakus smile
calyton Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Also ich muss ja beweisen, dass die Zielmenge konvex ist.

Dafür muss ich erstmal nachweisen, dass die beiden Nebenbedingungen konvex sind oder nicht?

Und die nebenbedingung müssen ja im Zusammenhang mit Z gesehen werden....so dachte ich mir das, denn irgendwie muss da ja die "Grundform" der Konvexität rein.

Deswegen hatte ich



...

was mache ich falsch?


Sollte der komplette Ansatz anders sein?
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Zitat:
Original von calyton
Also ich muss ja beweisen, dass die Zielmenge konvex ist.

Dafür muss ich erstmal nachweisen, dass die beiden Nebenbedingungen konvex sind oder nicht?


Es gibt konvexe Mengen und konvexe Funktionen, was aber ist eine konvexe Nebenbedingung und wie sieht der Zusammenhang zur konvexen Menge aus?

Entweder formulierst du hier sehr lax oder du vewendest einen mir nicht bekannten Begriff.

Wenn du zeigen willst, dass die Menge der opt. Zielfunktionswerte konvex ist, musst du folgendes zeigen:



Dein Beweis fängt also wie folgt an:

Es seien . Dann ... (hier folgen deine Überlegungen).

Am Ende des Beweises sollte stehen:

Dann gilt .

Grüße Abakus smile

edit: Konvexitätsbedingung
calyton Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Ich dachte, dass das lineare Programm aus der Zielfunktion und den Nebenbedingungen besteht.

Und ich beweisen muss, dass diese konvex sind.


Wenn der beweis in Wirklichkeit so anfängt, dann fangen wir gleich bei meinem Problem, dem Ansatz an.

Ich bin ehrlich, ich hab keine Ahnung.

Bei den Nebendingungen handelt es sich ja um Funktionen, da war es ja ein leichtes die Konvexität nachzuweisen.

Aber wenn ich doch nur -> max da stehen hab, was weiß ich dann?

mit könnte ich schreiben als als irgendeine Zielfunktion, oder?

Ist das die grundlage für den Beweis?
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Zitat:
Original von calyton
Ich dachte, dass das lineare Programm aus der Zielfunktion und den Nebenbedingungen besteht.

Und ich beweisen muss, dass diese konvex sind.


Ersteres ist ok. Was du jedoch zeigen willst, sagt mir zumindest nichts. Am Besten klärst du via Skript mal ab, was ihr unter "konvex" eigentlich versteht.


Zitat:
Wenn der beweis in Wirklichkeit so anfängt, dann fangen wir gleich bei meinem Problem, dem Ansatz an.

Ich bin ehrlich, ich hab keine Ahnung.

Bei den Nebendingungen handelt es sich ja um Funktionen, da war es ja ein leichtes die Konvexität nachzuweisen.

Aber wenn ich doch nur -> max da stehen hab, was weiß ich dann?


Ich habe oben als Bezeichnung für eine Menge aufgefasst (nachdem du es so bezeichnet hast). Nach der Schreibweise hier könnte aber auch die Zielfunktion und den maximalen Zielfunktionswert bezeichnen. Vermutlich ist dies wirklich so gemeint. Die auf Konvexität zu untersuchende Menge ist nach der Aufgabe dann .

In dem Fall müsste das zu Beweisende bei mir oben entsprechend anders geschrieben werden, ich korrigiere das mal:

Zu zeigen:


Zitat:
mit könnte ich schreiben als als irgendeine Zielfunktion, oder?


Hier hast du die Konfusion zwischen Menge und Zielfunktion komplett (eines geht natürlich nur).

Wenn du obige Behauptung zeigen willst, musst du 2 Dinge zeigen:

[1] erfüllt die Nebenbedingungen

[2] , dh. der Zielfunktionswert ist optimal

Beides kannst du durch Einsetzen und Ausnutzen der Linearität dann zeigen (ähnlich zu dem, wie du angesetzt hast).

Grüße Abakus smile

edit: Konvexitätsbedingung
 
 
calyton Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Hm, das muss ich prüfen.

Hört sich aber natürlich besser an als meine "Aussagen" smile


Schreibe heute abend was dazu
calyton Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Zitat:
Original von Abakus

Ich habe oben als Bezeichnung für eine Menge aufgefasst (nachdem du es so bezeichnet hast). Nach der Schreibweise hier könnte aber auch die Zielfunktion und den maximalen Zielfunktionswert bezeichnen. Vermutlich ist dies wirklich so gemeint. Die auf Konvexität zu untersuchende Menge ist nach der Aufgabe dann .

In dem Fall müsste das zu Beweisende bei mir oben entsprechend anders geschrieben werden, ich korrigiere das mal:
A.) Zu zeigen:


B.) Wenn du obige Behauptung zeigen willst, musst du 2 Dinge zeigen:

[1] erfüllt die Nebenbedingungen

[2] , dh. der Zielfunktionswert ist optimal

Beides kannst du durch Einsetzen und Ausnutzen der Linearität dann zeigen (ähnlich zu dem, wie du angesetzt hast).



Zu A.) :

hört sich gut an, aber wie ist das der weitere Ansatz?


Zu B.) :


[2]







Ist jetzt positiv? Woher wüsste ich das? Es gibt doch auch negative Zielfunktionswerte, siehe Simplextableau bei nicht optimalten Ecken!
Ist jetzt positiv? Woher? Wenn ja, dann ist ja negativ, da .
Damit wäre doch negativ...aber konvex nicht.....


[1]






da ist doch das selbe wie bei [2]. oder?



p.S.: fehlten da nicht die LAMBDA's bei [1] vor und bei [2] vor ?
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Mit dem hast du Recht, das muss noch vor das x (oben bereits korrigiert).

Das Ganze nochmal ausführlicher im Zusammenhang: zuerst die Voraussetzungen des Beweises, diese stehen am Anfang.

Es seien .

Jetzt kommen weitere Überlegungen:

bedeutet, dass beide Werte optimalen Zielfunktionswert besitzen und die Nebenbedingung erfüllen, es gilt also:



(Hier ist die Nebenbedigung in der "="-Form geschrieben; ggf. musst du begründen, wieso das geht oder alternativ: verwende die -Form)


Jetzt, zu dem, was zu zeigen ist:

[1] erfüllt die Nebenbedingungen

Es gilt:



(und das natürlich noch weiter ausrechnen)


[2] , dh. der Zielfunktionswert ist optimal

Hier gilt wegen der Linearität von Z:



Insgesamt dann:

Es gilt .

Wesentlich ist also, dass es Voraussetzungen gibt, die an geeigeter Stelle in den Beweis eingehen müssen.

Grüße Abakus smile

edit: Latex
calyton Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Also "so" weiter:


[1]










So und jetzt zu dem meiner Meinung schwereren Zielmenge

[2]












So?
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Zitat:
Original von calyton
Also "so" weiter:


[1]








Also ? (stimmt zwar, aber das ist nicht der Sinn hier) Überlege mal, was eigentlich gezeigt werden sollte.


Zitat:
So und jetzt zu dem meiner Meinung schwereren Zielmenge

[2]












So?


Auch hier, überlege dir, was gezeigt werden soll.


Grüße Abakus smile
calyton Auf diesen Beitrag antworten »

Ich hab jetzt den ganzen Tag gegrübelt.

Klar ich muss die Konvexität nachweisen und wenn du mich so darauf hinweist, dann hab ich das wohl nicht.


Es kann ja nicht sein, dass ich jetzt ausklammere und das wars dann.

Dann hätte ich ja schon vorher einfach die Z(y) und Z(x) mit Z(x*) gleichsetzen können, ohne, dass ich das ausklammere.

Das kann es ja nicht sein.



Kannst du mir nicht etwas die Hand führen?
Abakus Auf diesen Beitrag antworten »
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Ich zitiere mal von weiter oben:

Zitat:
Original von Abakus
Jetzt, zu dem, was zu zeigen ist:

[1] erfüllt die Nebenbedingungen

Es gilt:



(und das natürlich noch weiter ausrechnen)


[2] , dh. der Zielfunktionswert ist optimal

...

Insgesamt dann:

Es gilt .



Du machst aus [1] ein:

Zitat:


ist hier bereits Voraussetzung. Das, was du zeigen sollst, ist:



Ähnlich dann bei [2].

Grüße Abakus smile
calyton Auf diesen Beitrag antworten »

Zum ersten Mal erscheint mir etwas "trivial", ob das heißt, dass ich jetzt richtig liege, dass wirst du mir sagen müssen smile


Lösungs(versuch):
----------------------------------








[1]

erfüllt die Nebenbedingung

Zu zeigen :



Es gilt:



Da laut den Vorraussetzungen gilt, folgt:





[2]

erfüllt die Nebenbedingung

Zu zeigen:



Es gilt:





Da laut den Vorraussetzungen und trivialer weise gilt, folgt:





[3] , dh. der Zielfunktionswert ist optimal

Zu zeigen:



Es gilt:



Da laut den Vorraussetzungen gilt, folgt:





[1]+[2]+[3] => die optimale Lösungsmenge ist konvex.



-----
edit: falsch gesetzte Klammern entfernt!
Elvis Auf diesen Beitrag antworten »
konvexe Lösungsmenge
Hallo, calyton,
deine Beweisführung gefällt mir richtig gut. smile
Für trivial halte ich das nicht, obwohl ich seit über 20 Jahren lineare und nichtlineare Optimierung mache. Bisher war ich immer damit zufrieden, dass mir die Algorithmen eine Lösung aus der Lösungsmenge berechnet haben.
Jetzt habe ich wieder was dazugelernt, nämlich, dass nicht nur die Menge der zulässigen Punkte sondern auch die (Teil-)Menge der optimalen Punkte eines linearen Problems konvex ist. Danke. Mit Zunge
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von calyton
[1]

erfüllt die Nebenbedingung

Zu zeigen :



Es gilt:



Da laut den Vorraussetzungen gilt, folgt:



Jetzt sieht es gut aus Augenzwinkern ; noch eine Bemerkung: wenn du einen Term umformst, benutze eine Gleichungskette, also schematisch zB A = B = C = D, damit A = D.

Die Bedeutung von A = B = C => C = D ist eine andere.

Grüße Abakus smile
Jayk Auf diesen Beitrag antworten »

Was bedeutet ?
Abakus Auf diesen Beitrag antworten »

Zitat:
Original von Jayk
Was bedeutet ?


Es kennzeichnet eine Behauptung.

Grüße Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

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