Grafische Lösung des Optimierungsproblems

06.07.2019, 15:40

kaizo19

Grafische Lösung des Optimierungsproblems

Meine Frage:
Hallo liebe Community,

ich setze gerade an folgender Aufgabe. Zu Bestimmen ist die grafische Lösung des nachfolgenden Optimierungsproblems:

max F(x1,x2) = -2*x1 + x2
$\begin{eqnarray*} (x-1)^{2}+ 2y^{2} \leq 2 \end{eqnarray*}$
$\begin{eqnarray*} x1\geq 0, x2\geq 0 \end{eqnarray*}$

Meine Ideen:
Grundsätzlich hätte ich die Ungleichungsnebenbedingung nach y umgeformt, damit ich Sie in ein Diagramm zeichnen kann. Allerdings bekomme ich einen Wurzel-Ausdruck heraus, bei dem ich nicht weis, wie man diesen zeichnet.

Zur Aufgabe selbst wundert es mich auch, dass in der Nebenbedingung als Variablen x und y vorkommen, in der Zielfunktion aber x1 und x2.
Hat jemand von euch einen passenden Tipp für mich, wie man an diese Aufgabe rangeht?

Vielen Dank und Grüße
kaizo

06.07.2019, 18:38

Huggy

Auf diesen Beitrag antworten »

RE: Grafische Lösung des Optimierungsproblems

Zitat:

Original von kaizo19
Grundsätzlich hätte ich die Ungleichungsnebenbedingung nach y umgeformt, damit ich Sie in ein Diagramm zeichnen kann. Allerdings bekomme ich einen Wurzel-Ausdruck heraus, bei dem ich nicht weis, wie man diesen zeichnet.

Das bedeutet. dass die durch die Nebenbedingung gegebenen Kurven aus zwei Zweigen bestehen. Der eine ergibt aus der positiven Wurzel, der andere aus der negativen Wurzel. Die Grenzkurven bei fester rechter Seite sind Ellipsen. Die größte ergibt sich bei 2 auf der rechten Seite.

Zitat:

Zur Aufgabe selbst wundert es mich auch, dass in der Nebenbedingung als Variablen x und y vorkommen, in der Zielfunktion aber x1 und x2.

Das ist sicher nur ein Versehen. Verwende überall $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ oder überall $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ .

09.07.2019, 10:25

kaizo19

Auf diesen Beitrag antworten »

Hallo Huggy,

vielen Dank erst mal für deine Antwort. Ich habe die umgestellte Ungleichung-NB

$\begin{eqnarray*} x2 = \pm \sqrt{1-\frac{1}{2} *(x1-1)^{2} } \end{eqnarray*}$

mal in Matlab geplottet
[attach]49467[/attach]

Mein Maximum bekomme ich ja jetzt, wenn ich die Zielfunktion als Gerade zeichne und den Schnittpunkt mit der Ungleichungs-NB Kurve bestimme

[attach]49471[/attach]

Das Maximum ist bei Pmax(x1,x2) = (-0.33,0.33).

Ist diese Vorgehensweise so richtig von mir?

09.07.2019, 11:21

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von kaizo19
Das Maximum ist bei Pmax(x1,x2) = (-0.33,0.33).

Ist diese Vorgehensweise so richtig von mir?

Zunächst mal ist es, wenn man nur graphisch löst, hilfreich, wenn in der Zeichnung die beiden Achsen den gleichen Maßstab haben, obwohl das nicht zwingend erforderlich ist.

Richtig ist, dass man die Gerade der Zielfunktion verschiebt. Allerdings kann man sie nicht so weit verschieben, wie du es getan hast. Dabei hast du die Bedingungen $\begin{eqnarray*} x_1 \geq 0 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \geq 0 \end{eqnarray*}$ nicht beachtet. Bei deiner Lösung ist ja $\begin{eqnarray*} x_1 <0 \end{eqnarray*}$ . Mindestens ein Schnittpunkt der Geraden mit der Ellipse muss diese beiden Bedingungen erfüllen.

09.07.2019, 12:40

kaizo19

Auf diesen Beitrag antworten »

Natürlich hast du recht und die Achsen sollten gleich skaliert sein. Mir ging es dabei nur um die grafische Veranschaulichung.

Ja das stimmt, die Positivitäts-Bedingungen habe ich ganze vergessen (rote Linien).

[attach]49474[/attach]

Das Maximum müsste dann bei (0,0.7) sein. Bei x= 2.5 kann ich ja keine Gerade einzeichnen, da der Kurvenverlauf entlang der x-Achse verläuft. Stimmt das?

09.07.2019, 13:06

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von kaizo19
Das Maximum müsste dann bei (0,0.7) sein.

Als graphische Lösung korrekt!
Durch Einsetzen von $\begin{eqnarray*} x=0 \end{eqnarray*}$ in Ellipsengleichung kann man natürlich leicht die exakte Lösung bestimmen.

Zitat:

Bei x= 2.5 kann ich ja keine Gerade einzeichnen, da der Kurvenverlauf entlang der x-Achse verläuft. Stimmt das?

Die Bemerkung verstehe ich nicht. Zu maximieren ist

$\begin{eqnarray*} c=-2x_1+x_2 \end{eqnarray*}$

Gesucht ist das größte $\begin{eqnarray*} c \end{eqnarray*}$ , bei dem alle Bedingungen erfüllt sind und die zugehörigen Werte von $\begin{eqnarray*} (x_1,x_2) \end{eqnarray*}$ . Wenn man $\begin{eqnarray*} c \end{eqnarray*}$ vergrößert, verschiebt man die Gerade der Zielfunktion nach links oben. Wenn man $\begin{eqnarray*} c \end{eqnarray*}$ verkleinert, verschiebt man sie nach rechts unten. Selbstverständlich kannst du auch eine Gerade zeichnen, die Ellipse irgendwo rechts schneidet. Begrenzend wird dann die Bedingung $\begin{eqnarray*} x_2 \geq 0 \end{eqnarray*}$ . Aber das wäre brotlose Kunst. Denn zu diesen Geraden gehört ein kleineres $\begin{eqnarray*} c \end{eqnarray*}$ . Sie maximieren also nicht die Zielfunktion.

09.07.2019, 14:09

kaizo19

Auf diesen Beitrag antworten »

Ich habe da glaube etwas falsch interpretiert. Bisher habe ich nur Aufgaben gesehen, bei denen die Gerade das zulässige Gebiet nur in einem Punkt schneidet, also eine Tangente an dem Punkt angelegt wird.

Den Punkt bei x = 2.5 habe ich deshalb ausgeschlossen, weil dort keine Tangente angelegt werden kann. Die Funktion wandert ja für x > 2.5 entlang der x-Achse. Ich weis allerdings nicht, ob man das so argumentieren kann...

[attach]49475[/attach]

Natürlich müsste mir klar sein, dass die Zuweisung max F(x1,x2) = c heißt, dass ich den maximalen Wert für c suche. Und hier ist es ja genau so, wie du es argumentiert hast. Die Verschiebung der Geraden nach links führt zu einem Anstieg von c, während eine Verschiebung nach links c verringert.

09.07.2019, 16:05

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von kaizo19
Den Punkt bei x = 2.5 habe ich deshalb ausgeschlossen, weil dort keine Tangente angelegt werden kann. Die Funktion wandert ja für x > 2.5 entlang der x-Achse.

Vielleicht meinst du es ja richtig, aber so passt es nicht. Die Funktion

$\begin{eqnarray*} c=-2x_1+x_2 \end{eqnarray*}$

verläuft für jedes $\begin{eqnarray*} c \end{eqnarray*}$ bei wachsendem $\begin{eqnarray*} x_1 \end{eqnarray*}$ schräg von links unten nach rechts oben. Vermutlich meinst du hier die Nebenbedingung $\begin{eqnarray*} x_2 \geq 0 \end{eqnarray*}$ . Ich habe mal ein eigenes Bild erstellt mit 3 $\begin{eqnarray*} c \end{eqnarray*}$ -Werten, die ich an die Geraden geschrieben habe. Die grüne Gerade würde $\begin{eqnarray*} c \end{eqnarray*}$ unter den Nebenbedingungen minimieren. Aber auch die ist bei $\begin{eqnarray*} x_1=2.5 \end{eqnarray*}$ definiert. Nur hat sie da schon die Ellipse verlassen.

[attach]49476[/attach]

Bei meinem Bild sind auch beide Teile der Ellipse eingezeichnet.

09.07.2019, 18:27

kaizo19

Auf diesen Beitrag antworten »

Danke für das Schaubild. Die andere Seite der Ellipse hätte ich auch zeichnen sollen. Dann ist das mit x1 = 2.5 schon ersichtlich, dass die Ellipse mit der Gerade nicht geschnitten wird. Und die grüne ist dann das Minimum, da hier c am kleinsten ist.

In den Vorlesungen haben wir immer nur das zulässige Gebiet betrachtet und da sah es dann immer nach Tangenten aus.

Dass das immer Tangenten sind ist dann quatsch bzw. es sind Tangenten, wenn ich die Funktion nur unter Berücksichtigung der Positivitäts-Bedingungen zeichnen würde. Denn dann ist es ja genau ein Schnittpunkt mit dem zulässigen Gebiet.

[attach]49480[/attach]

Aber klar ist jetzt, das c wird maximal für (x1,x2) = (0,0.7). Alleine schon die Zuordnung max F(x1,x2) = c hätte mir aufzeigen müssen, dass ich c groß wählen muss.

Vielen Dank für deine ausführlichen Antworten Freude

Neue Frage »

Antworten »

Grafische Lösung des Optimierungsproblems

Verwandte Themen