Optimierungsproblem < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Untersuchen Sie, für welche Werte der Parameter a,b [mm] \in \IR [/mm] das folgende Optimierungsproblem optimale Lösungen besitzt.
[mm] max_{x_{1},x_{2}} {ax_{1} + bx_{2}}
[/mm]
Nebenbedingungen:
[mm] 5x_{1} [/mm] - [mm] x_{2} \le [/mm] -4
[mm] x_{1} [/mm] - [mm] 2x_{2} \le [/mm] 1
[mm] x_{1},x_{2} \ge [/mm] 0 |
Zunächst weiß ich aus der Vorlesung, dass optimale Lösungen dann vorliegen, wenn ich für das Primalproblem sowie das Dualproblem zulässige Kösungen finde und der Wert der Zielfunktion der Gleiche ist.
Aber ist komme hier einfach nicht darauf. Ich habe eine Matrix erstellt:
A = [mm] \pmat{ 5 & -1 \\ 1 & -2 }; [/mm] b = [mm] \pmat{ -4 \\ 1}; [/mm] c = [mm] \pmat{a \\ b}
[/mm]
Aber ich stehe komplett auf dem Schlauch, ich hab keine Ahnung wie und was ich rechnen muss. Mich verwirren die beiden Parameter a und b.
Zudem komme ich beim Lösen mit dem Simplexverfahren nicht weiter...
Ich hoffe ihr könnt mir sagen wie und was ich als Ansatz machen muss... Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:04 Do 01.05.2008 | | Autor: | Zneques |
Hallo,
Alle einschränkenden Ungleichung lassen nur Lösungen in einem Halbraum zu. Zusammen entsteht so ein Polyeder, in dem die Lösung zu finden ist.
Wenn man sich das genauer anschaut, sieht man dass die Lösung in einer Ecke ist. D.h. sie erfüllt mehere Ungleichungen exakt.
Z.B.: [mm] x_1=0 [/mm] und [mm] x_2=0 [/mm] wäre eine dieser Ecken.
Gibt es nun a und b, so dass diese Ecke, also [mm] x_1=x_2=0 [/mm] optimal/maximal ist ? Ab welchen Werten ist es keine optimale Ecke mehr ? (Nachbarecken sind besser)
Welche Ecken gibt es noch ?
Wie sieht es dort aus ?
Ciao.
|
|
|
| |
|
[mm] x_{1} [/mm] und [mm] x_{2} [/mm] können doch nicht = 0 sein, es sonst die erste Nebenbedingung nicht erfüllt ist? 0 > -4? Was ich heute nacht versucht habe war und ist, dass ich alles in ein simplex- Tableau geschrieben habe, was aber auch nicht geht, da a,b [mm] \in \IR [/mm] also größer bzw. kleiner null sein kann. Hab jetzt für die x Werte 0 und 4 gewählt. Dann habe ich da stehen: 0a + 4b unter den Nebenbedingungen. Oder ist das total falsch?
Könnte mir bitte jemand noch ein wenig auf die Sprünge helfen? Vielen Dank und einen Schönen Feiertag!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:54 Do 01.05.2008 | | Autor: | Zneques |
Da wollte ich ein leichtes Beispiel nehmen und dann stimmt es nicht.
Ok, also [mm] x_1=0 [/mm] und [mm] x_2=0 [/mm] ist somit natürlich keine Ecke.
Aber du hast ja eine gefunden. [mm] x_1=0 [/mm] und [mm] x_2=4 [/mm] erfüllen die Ungleichungen
[mm] 5x_{1}-x_{2}\le-4 [/mm] und [mm] x_1\ge0 [/mm] exakt.
Nun musst du noch die restlichen finden. Dann kannst du entscheiden welche Werte für a und b für welche Ecke die Besten sind.
Das Problem das dann auftritt ist das, das der Polyeder an einer Seite offen is. D.h. Man kann die Werte in einer Richtung beliebig vergrößern und somit kein Maximum finden.
Ciao.
|
|
|
| |
|
hallo Stephan,
das Ganze spielt sich ja in der Ebene ab, also kann man das
durch die Ungleichungen beschriebene Gebiet leicht aufzeichnen.
Das entstehende (offene) "Polygon" (eher Monogon...) ist sehr
einfach: es ist ein Gebiet G, das zwischen zwei von (0/4) ausge-
henden Strahlen liegt und ins Unendliche reicht.
Ich schreibe x und y anstelle von [mm] x_1 [/mm] und [mm] x_2 [/mm] .
Die zu maximierende Funktion ist [mm]F(x,y) = a*x+b*y = \vektor{a \\ b} * \vektor{x \\ y} [/mm]
Der Vektor [mm] \vec{n} [/mm] = [mm] \vektor{a \\ b} [/mm] ist der "Gradientenvektor" der Funktion F:
[mm] \vec{n} [/mm] = [mm] \vektor{\partial F / \partial x\\ \partial F / \partial y}
[/mm]
Nun geht es darum, herauszufinden, in welche Richtungen der
zeigen kann, wenn [mm]F[/mm] in dem Gebiet G ein Maximum (natürlich auf dem Rand von G)
annehmen soll.
|
|
|
|
