lineares Optimierungsproblem < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:19 Fr 02.11.2012 | | Autor: | Sam90 |
| Aufgabe | Gegeben sei das folgende lineare Optimierungsproblem LP1:
min [mm] 4x_{1} [/mm] + [mm] 2x_{2} [/mm] + [mm] x_{3}
[/mm]
unter [mm] x_{1} [/mm] + [mm] x_{3} \ge [/mm] 1
[mm] x_{1} [/mm] - [mm] x_{2} [/mm] - [mm] x_{3} \le [/mm] 2
[mm] x_{2} \ge [/mm] 1
[mm] 4x_{2} [/mm] - [mm] 2x_{3} [/mm] = 4
[mm] x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] x_{3} \ge [/mm] -1
[mm] x_{1} \ge [/mm] 0
[mm] 3x_{2} [/mm] - [mm] x_{3} \le [/mm] 7
(a) Skizzieren Sie die durch die Restriktionen gegebene Punktmenge in der [mm] x_{1}-x_{2}-Ebene.
[/mm]
Hinweis: Die Variable [mm] x_{3} [/mm] lässt sich aus dem obigen System eliminieren.
(b) Gibt es redundante Restriktionen, die weggelassen werden können?
(c) Geben Sie LP1 in der (zweidimensionalen) kanonischen Form LP2 an, d.h. bei Eliminierung von [mm] x_{3}.
[/mm]
(d) Ist LP2 unbeschränkt?
(e) Zeigen Sie, dass der Punkt x = [mm] (x_{1}, x_{2})^{T} [/mm] = [mm] (0,\bruch{3}{2} )^{T} [/mm] eine optimale Lösung von LP2 ist. |
Hallo :)
Ich habe leider überhaupt keine Ahnung, wie ich an diese Aufgabe rangehen soll. Es fängt schon dabei an, dass ich nicht weiß, wie ich [mm] x_{3} [/mm] eliminieren soll, ansonsten kann ich doch nicht anfange zu zeichnen, aber verlangt wird das erst in Teil (c)?! Es wäre wirklich nett, wenn mir hier jemand helfen könnte bzw. einen Anstoß geben könnte.
LG Sam
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi,
bei deinen Nebenbedingung ist eine Gleichung. Diese stellst du nach [mm] $x_3$ [/mm] um und ersetzt jedes weitere [mm] $x_3$ [/mm] durch den entsprechenden Ausdruck.
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:35 Fr 02.11.2012 | | Autor: | Sam90 |
Oh Gott stimmt ;) Danke!
Dann werd ich mich mal an die Arbeit machen und hinterher meine Ergebnisse hier zur Kontrolle posten :)
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:24 Sa 03.11.2012 | | Autor: | Sam90 |
Also hier meine Lösung:
(a) Die Skizze habe ich gezeichnet, indem ich die 4. Nebenbedingung nach [mm] x_{3} [/mm] umgestellt und in die anderen Bedingungen eingesetzt habe.
[mm] x_{3}=2x_{2}-2
[/mm]
(b) Die 5. Nebenbedingung kann weggelassen werden. An der Skizze kann man erkennen, dass sie außerhalb des Lösungsbereichs liegt und somit überflüssig ist.
(c) LP2:
min [mm] 2x_{1}+2x_{2}-1
[/mm]
unter [mm] x_{1}+2x_{2}\ge3
[/mm]
[mm] x_{1}-3x_{2}\le0
[/mm]
[mm] x_{2}\ge1
[/mm]
[mm] (x_{1}+3x_{2}\ge1)
[/mm]
[mm] x_{1}\ge0
[/mm]
[mm] x_{2}\le5
[/mm]
(d) LP2 ist nicht unbeschränkt. Es existieren 5 optimale Lösungen (Eckpunkte), die den Lösungsbereich eingrenzen.
(e) Hier bin ich mir nicht ganz sicher, wie ich das beweisen kann.
An der Skizze kann man doch schon erkennen, dass der Punkt eine Optimallösung ist, aber ich kann mir nicht vorstellen, dass das als Antwort reicht. Kann ich den Punkt irgendwo einsetzen und das so beweisen?
LG Sam
|
|
|
| |
|
zur d)
Nicht jede Ecke ist eine Optimallösung!
zur e)
Eine optimale Lösung wird in den Ecken angenommen, wie du schon schriebst. Wodurch zeichnen sich Ecken von einem Simplex aus?
Setze doch einmal eine optimale Lösung in die Nebenbedingungen ein.
Was erhälst du?
Was schlussfolgerst du daraus?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:11 Sa 03.11.2012 | | Autor: | Sam90 |
> zur d)
> Nicht jede Ecke ist eine Optimallösung!
Okay, dann werde ich das umformulieren, aber beschränkt ist LP2 doch trotzdem?!
> zur e)
> Eine optimale Lösung wird in den Ecken angenommen, wie du
> schon schriebst. Wodurch zeichnen sich Ecken von einem
> Simplex aus?
>
> Setze doch einmal eine optimale Lösung in die
> Nebenbedingungen ein.
> Was erhälst du?
> Was schlussfolgerst du daraus?
Wenn ich die optmiale Lösung in die Nebenbedingungen einsetze, dann gehen alle Gleichungen auf. Somit ist der angegebene Punkt wirklich eine optimale Lösung von LP2.
|
|
|
| |
|
> > zur e)
> > Eine optimale Lösung wird in den Ecken angenommen, wie
> du
> > schon schriebst. Wodurch zeichnen sich Ecken von einem
> > Simplex aus?
> >
> > Setze doch einmal eine optimale Lösung in die
> > Nebenbedingungen ein.
> > Was erhälst du?
> > Was schlussfolgerst du daraus?
>
> Wenn ich die optmiale Lösung in die Nebenbedingungen
> einsetze, dann gehen alle Gleichungen auf. Somit ist der
> angegebene Punkt wirklich eine optimale Lösung von LP2.
>
Was heißt hier Gleichung?
Wie habt ihr denn optimale Lösung definiert?
Ich würde für so eine Antwort keine Punkte geben.
|
|
|
|
