Lineares Optimierungsproblem < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:13 Mo 12.11.2012 | | Autor: | Lena23 |
| Aufgabe | Gegeben sei das folgende lineare Optimierungsproblem LP:
max [mm] 6x_{1} [/mm] - [mm] x_{2} [/mm] - [mm] 4x_{3}
[/mm]
unter [mm] 2x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] 2x_{3} \le [/mm] 10
[mm] x_{1} [/mm] - [mm] x_{3} \le [/mm] 2
x [mm] \ge [/mm] 0
(a) Bestimmen Sie alle Ecken des Polyeders sowie die dortigen Zielfunktionswerte.
(b) Geben Sie eine optimale Lösung von LP an. Ist diese optimale Lösung für LP eindeutig? |
Hallo :)
Ich brauche dringend Hilfe bei dieser Aufgabe. Ich weiß absolut nicht, mit welchem Verfahren ich hier rangehen soll bzw. wie man sowas generell löst.
Deshalb würde ich mich unheimlich über Hilfe freuen!
LG Lena
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Gegeben sei das folgende lineare Optimierungsproblem LP:
> max [mm]6x_{1}[/mm] - [mm]x_{2}[/mm] - [mm]4x_{3}[/mm]
> unter [mm]2x_{1}[/mm] + [mm]x_{2}[/mm] + [mm]2x_{3} \le[/mm] 10
> [mm]x_{1}[/mm] - [mm]x_{3} \le[/mm] 2
> x [mm]\ge[/mm] 0
> (a) Bestimmen Sie alle Ecken des Polyeders sowie die
> dortigen Zielfunktionswerte.
> (b) Geben Sie eine optimale Lösung von LP an. Ist diese
> optimale Lösung für LP eindeutig?
> Hallo :)
>
> Ich brauche dringend Hilfe bei dieser Aufgabe. Ich weiß
> absolut nicht, mit welchem Verfahren ich hier rangehen soll
> bzw. wie man sowas generell löst.
> Deshalb würde ich mich unheimlich über Hilfe freuen!
>
> LG Lena
Umgeschrieben steht da
[mm]\pmat{ 2 & 1 & 2 \\
1 &0 & -1 } \vektor{x_1 \\
x_2\\
x_3}\leq \vektor{10 \\
2}[/mm]
i) Ignoriere [mm] $x_3$ [/mm] durch [mm] $x_3:=0$ [/mm] und löse das LGS:
[mm]\pmat{ 2 & 1 \\
1 &0 } \vektor{x_1 \\
x_2}= \vektor{10 \\
2}[/mm]
ii) Ignoriere [mm] $x_2$ [/mm] durch [mm] $x_2:=0$ [/mm] und löse das LGS ...
iii) Ignoriere [mm] $x_1$ [/mm] durch [mm] $x_1:=0$ [/mm] und löse das LGS ...
Du erhälst 3 Ecken durch die jeweiligen Lösungen.
Für i) ist die Lösung [mm] $x_2=6,x_1=2$. [/mm] Somit entspricht somit der Ecke [mm] $(x_1,x_2,x_3):=(2,6,0)$.
[/mm]
Dessen Funktionswert kannst du selber ausrechnen.
In der b) suchst du dir von den 3 Ecken die Optimale aus.
Da soetwas nie so deutlich erklärt wird (immer im Hinterkopf behalten):
Solche LP's, wie dort oben steht können ungemein viele Ecken besitzen. Man weiß, dass eine optimale Lösung in der Ecke angenommen wird. Man müsste nur ALLE Ecken durchgehen.
Falls dann später der Simplex-Algorithmus dran kommt, ist das nur ein geschickter Weg die Ecken in einer bestimmten Reihenfolge anzuschauen und ein paar Ecken auszuschließen.
gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:58 Do 15.11.2012 | | Autor: | Lena23 |
Super, vielen Dank für die ausführliche Erklärung!
|
|
|
|
