Konvexität der optimalen Lösungsmenge eines linearen Programms |
26.03.2009, 13:25 | calyton | Auf diesen Beitrag antworten » | ||||||
Konvexität der optimalen Lösungsmenge eines linearen Programms 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 |
||||||||
27.03.2009, 21:43 | Abakus | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
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 |
||||||||
27.03.2009, 23:14 | 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? |
||||||||
28.03.2009, 11:38 | Abakus | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
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 edit: Konvexitätsbedingung |
||||||||
28.03.2009, 13:15 | 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? |
||||||||
28.03.2009, 18:50 | Abakus | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
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.
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:
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 edit: Konvexitätsbedingung |
||||||||
Anzeige | ||||||||
|
||||||||
29.03.2009, 15:35 | 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" Schreibe heute abend was dazu |
||||||||
30.03.2009, 09:52 | calyton | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
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 ? |
||||||||
30.03.2009, 18:56 | 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 edit: Latex |
||||||||
31.03.2009, 11:27 | 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? |
||||||||
31.03.2009, 20:46 | Abakus | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms
Also ? (stimmt zwar, aber das ist nicht der Sinn hier) Überlege mal, was eigentlich gezeigt werden sollte.
Auch hier, überlege dir, was gezeigt werden soll. Grüße Abakus |
||||||||
01.04.2009, 18:07 | 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? |
||||||||
02.04.2009, 20:50 | Abakus | Auf diesen Beitrag antworten » | ||||||
RE: Konvexität der optimalen Lösungsmenge eines linearen Programms Ich zitiere mal von weiter oben:
Du machst aus [1] ein:
ist hier bereits Voraussetzung. Das, was du zeigen sollst, ist: Ähnlich dann bei [2]. Grüße Abakus |
||||||||
03.04.2009, 19:48 | 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 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! |
||||||||
03.04.2009, 20:04 | Elvis | Auf diesen Beitrag antworten » | ||||||
konvexe Lösungsmenge Hallo, calyton, deine Beweisführung gefällt mir richtig gut. 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. |
||||||||
04.04.2009, 20:09 | Abakus | Auf diesen Beitrag antworten » | ||||||
Jetzt sieht es gut aus ; 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 |
||||||||
04.04.2009, 20:39 | Jayk | Auf diesen Beitrag antworten » | ||||||
Was bedeutet ? |
||||||||
04.04.2009, 20:44 | Abakus | Auf diesen Beitrag antworten » | ||||||
Es kennzeichnet eine Behauptung. Grüße Abakus |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |