Beträge in Optimierungsproblemen auflösen

Neue Frage »

01.11.2008, 09:23	Fletcher	Auf diesen Beitrag antworten »
Beträge in Optimierungsproblemen auflösen Guten Tag, es geht mir hier prinzipiell mal um die Frage, wie man Beträge bei Optimierungsproblemen auflöst um das Problem als lineares Problem zu formulieren: Konkret habe ich mir folgendes Beispiel mal ausgedacht. Es ist ein Minimum folgender Funktion gesucht: $\begin{eqnarray} f(x,y)=10\|3x+5y-200\|+4\|5x-6y+250\|+8\|7x+2y-350\| \end{eqnarray}$ Ich bin bisher soweit, dass ich mir einfach neue Variablen definiere: $\begin{eqnarray} z_1=3x+5y-200 \end{eqnarray}$ $\begin{eqnarray} z_2=5x-6y+250 \end{eqnarray}$ $\begin{eqnarray} z_3=7x+2y-350 \end{eqnarray}$ An dieser Stelle komme ich nicht mehr weiter. Ich muss jetzt irgendwie in die Nebenbedingungen packen, dass die Variablen z_i i=1,2,3 auch negativ werden können. Hat jemand eine Idee? Vielen Dank
01.11.2008, 13:48	Huggy	Auf diesen Beitrag antworten »
RE: Beträge in Optimierungsproblemen auflösen Es genügt, f(x,y) an den Schnittpunkten der drei Geraden $\begin{eqnarray} 3x+5y-200=0 \end{eqnarray}$ $\begin{eqnarray} 5x-6y+250=0 \end{eqnarray}$ $\begin{eqnarray} 7x+2y-350=0 \end{eqnarray}$ zu berechnen. Das Minimum befindet sich zwangsläufig an einem der drei Schnittpunkte.
01.11.2008, 13:59	Fletcher	Auf diesen Beitrag antworten »
Danke für den Tip, allerdings sollen wir nichts berechnen, sondern das ganze als lineares Optimierungsproblem formulieren, deshalb gilt es eine geeignete Zielfunktion aufzustellen und anschließend die Restriktionsmenge richtig zu definieren. Dabei bin ich gerade und komme nicht so recht weiter.
01.11.2008, 14:13	Huggy	Auf diesen Beitrag antworten »
Mein obiger Tipp beruht auf der Betrachtung der Aufgabe als lineares Optimierungsproblem! Prinzipiell kannst du die Betragsfunktion durch eine Fallunterscheidung auflösen. Da es drei Betragsfunktionen gibt, erhielte man insgesamt 8 Fälle. Für jeden der 8 Fälle wird das zulässige Gebiet durch obige Geraden begrenzt. Es wechseln nur die Seitengebiete der Geraden. Für jeden der 8 Fälle ist das eine normale lineare Optimierungsaufgabe. Nach einem Satz der linearen Optimierung befindet sich das Minimum der Zielfunktion (sofern es ein solches gibt) auf einem der durch die Nebenbedingungen erzeugten Eckpunkte. Die Eckpunkte sind aber für alle 8 Teilprobleme dieselben. Also genügt es f(x,y) an diesen Eckpunkten zu berechnen.
02.11.2008, 16:14	Fletcher	Auf diesen Beitrag antworten »
Hallo Huggy, ich verstehe natürlich was du meinst. Allerdings geht es in der genannten Aufgabe einfach darum, dass Problem korrekt zu formulieren und formal richtig hinzuschreiben, deshalb bin ich nun soweit gekommen, dass ich die oben angegebenen Funktionen $\begin{eqnarray} z_1,z_2,z_3 \end{eqnarray}$ nochmals mit Hilfe von Variablen $\begin{eqnarray} z_1^+,z_1^- \end{eqnarray}$ usw. zerlege und zwar je nachdem ob die Variablen $\begin{eqnarray} z_1,z_2,z_3 \end{eqnarray}$ positiv oder negativ sind. Dann bekomme ich einfach die zielfunktion: min $\begin{eqnarray} 10z_1^+ -10z_1^- +4z_2^+ -4z_2^-+ 8z_3^+ - 8z_3^- \end{eqnarray}$ Als Nebenbedingung habe ich ich dann z.b. $\begin{eqnarray} 3x+5y-200+z_1^+ -z_1^-=0 \end{eqnarray}$ usw. Was sagst du dazu?
02.11.2008, 19:08	Huggy	Auf diesen Beitrag antworten »
Da habe ich Probleme, das formal einzuordnen. Denn die Variablen $\begin{eqnarray} z_1^+ \end{eqnarray}$ usw. scheinen mir gar keine Variablen zu sein, sondern Sprungfunktionen. Oder verstehe ich da etwas falsch?
Anzeige

02.11.2008, 22:05	Fletcher	Auf diesen Beitrag antworten »
Hallo, also $\begin{eqnarray} z_i^+, i=1,2,3 \end{eqnarray}$ sind Variablen die folgendermaßen definiert sind. Mit dem Plus oben bedeutet, dass die Variable = $\begin{eqnarray} z_i \end{eqnarray}$ ist falls $\begin{eqnarray} z_i \leq 0 \end{eqnarray}$ sonst Null sind und eben mit - oben genau umgekehrt. Hoffe das war genau genug
02.11.2008, 22:28	Huggy	Auf diesen Beitrag antworten »
Dann hatte ich das richtig verstanden. Du nennst die $\begin{eqnarray} z_i^+ \end{eqnarray}$ Variablen. Ihrer Definition nach sind es aber Funktionen. Nun spricht nichts dagegen, neue Variablen einzuführen, wie z. B. die $\begin{eqnarray} z_i \end{eqnarray}$ , solange diese lineare Funktionen der ursprünglichen Variablen sind. Bei nichtlinearen Funktionen wie den $\begin{eqnarray} z_i^+ \end{eqnarray}$ ist man aber doch nicht mehr im Gebiet der linearen Optimierung?
03.11.2008, 08:57	Fletcher	Auf diesen Beitrag antworten »
Hallo Huggy, warum sollten diese Funktionen $\begin{eqnarray} z_i^+ \end{eqnarray}$ keine linearen Funktionen sein? Sie sind doch nur abschnittsweise definiert, aber jeder diese Abschnitte ist doch linear! Diese Methode steht bei mir im Skript und zwar findet sie allgemein Anwendung, wenn man ein geg. lineares Optimierungsproblem als lineares Optimierungsproblem in Normalform formulieren möchte. Denn in Normalform muss ja für alle Variablen $\begin{eqnarray} \geq 0 \end{eqnarray}$ gelten.
03.11.2008, 09:48	Huggy	Auf diesen Beitrag antworten »
Es ist keineswegs meine Absicht, dir deinen angedachten Weg madig zu machen. Vielleicht würde ich ihn besser verstehen, wenn du mal sagst, wie du jetzt mit deinen zusätzlichen Variablen konkret auf die Lösung kommst.
03.11.2008, 10:09	Fletcher	Auf diesen Beitrag antworten »
Um Schreibarbeit zu sparen, spiele ich das ganze jetzt nur für eine Funktion durch: $\begin{eqnarray} z_1=3x+5y-200 \end{eqnarray}$ Diese Funktion kann sowohl negativ als auch positiv sein, also führe ich noch weitere Variablen bzw. Funktionen ein, die wie oben erwähnt abschnittsweise definiert sind, dh. $\begin{eqnarray} z_1=z_1^+ - z_1^- \end{eqnarray}$ Damit ergibt sich mein lineares Optimierungsproblem zu: $\begin{eqnarray} min 10z_1^+ -10z_1^- \end{eqnarray}$ unter den Nebenbedingungen: $\begin{eqnarray} 3x+5y-z_1^+ + z_1^- = 200 \end{eqnarray}$ $\begin{eqnarray} x,y,z_1^-,z_1^+ \geq 0 \end{eqnarray}$ Das ganz funktioniert dann analog auch für die beiden anderen Funktionen, die ich hier jetzt nicht behandelt habe. Allerdings bin ich mir keineswegs sicher, ob das auch richtig ist, sonst hätte ich diese Frage nicht gestellt Für mich schaut es aber mittlerweile korrekt aus und ich werde es wohl auch so lassen. Es macht immerhin Sinn, so die Beträge wegzubekommen oder nicht? Klar ist, dass eine der Variablen $\begin{eqnarray} z_1^-,z_1^+ \end{eqnarray}$ ohnehin gleich Null ist, welche kommt eben auf $\begin{eqnarray} z_1 \end{eqnarray}$ selbst an.
03.11.2008, 10:18	Huggy	Auf diesen Beitrag antworten »
Das sind erst mal nur Gleichungen. Wie kommst du jetzt zu den konkreten Losungszahlen für x und y, die f(x,y) minimieren?
03.11.2008, 10:20	Fletcher	Auf diesen Beitrag antworten »
Überhaupt nicht, da das in dieser Aufgabenstellung nicht verlangt war. Ich glaube da hatten wir dann von Anfang an ein Kommunikationsproblem. Ich soll das ganze nicht lösen, sondern nur als lineares Problem formulieren! Das hatte ich oben schon einmal erwähnt. Was sagst du denn nun zu der Formulierung?
03.11.2008, 10:32	Huggy	Auf diesen Beitrag antworten »
Ich habe das schon verstanden, dass ihr das Problem nur korrekt umformulieren sollt. Nur muss diese Umformulierung es ja auch vom Prinzip her gestatten, die Lösung zahlenmäßig zu berechnen, auch wenn das nicht Teil eurer Aufgabestellung ist. Gestattet die Umformulieriung keine zahlenmäßige Berechnung der Lösung, ist es auch keine korrekte Umformulierung. Und da mir nicht klar ist, wie du von deiner Umformulierung zur zahlenmäßigen Lösung kommen würdest, bin ich noch skeptisch, ob dein Weg tragfähig ist.
03.11.2008, 10:35	Fletcher	Auf diesen Beitrag antworten »
Achso meinst du das. Jetzt verstehe ich das. Leider stehen wir noch ziemlich am Anfang der Vorlesung und haben uns über die Lösbarkeit noch nicht so viele Gedanken gemacht. Bisher haben wir nur 2-3 Optimierungsprobleme grafisch gelöst. Ansonsten haben wir uns darüber Gedanken gemacht, wie man ein lineares Optimierungsproblem in Normalform umschreiben kann. Inwiefern das ganze tragfähig ist, kann ich also selbst nicht einschätzen. Die Lösung erscheint mir mit dem Wissen was ich habe, logisch, aber ob sie wirklich richtig ist kann ich schwer einordnen.
03.11.2008, 10:54	Huggy	Auf diesen Beitrag antworten »
Habt ihr das Lösungsverfahren vom Prinzip her schon kennengelernt? Später geht es ja hauptsächlich um die effiziente algorithmische Umsetzung für Probleme mit vielen Variablen.
03.11.2008, 11:35	Fletcher	Auf diesen Beitrag antworten »
Meinst du das Simplexverfahren? Nein, das haben wir noch nicht kennengelernt. Wir haben bisher nur kennengelernt, dass die Minimallösung eine Ecke enthält und ein paar allg. Aussagen dazu bewiesen. Im Moment geht es in erster Linie darum, gestellte Probleme in lineare Optimierungsprobleme umzuschreiben. Den Algorithmus werden wir entweder diese oder nächste Woche kennenlernen, nehme ich an.
03.11.2008, 11:46	Huggy	Auf diesen Beitrag antworten »
Für die Lösung einfacher Probleme genügt ja das Wissen, dass die Minimallösung eine Ecke enthält. Bleibt also die Frage, wie könntest du aus deiner Formulierung zu den Ecken kommen?
03.11.2008, 20:25	Fletcher	Auf diesen Beitrag antworten »
Hatte heute die Möglichkeit, die Lösung einen Übungsleister zu präsentieren und leider Gottes stimmt das ganze nicht. Der Betrag wird nicht so wirklich aufgelöst. Weiß jetzt nicht mehr weiter.

Neue Frage »

Antworten »

Beträge in Optimierungsproblemen auflösen

Verwandte Themen