Simplex-Algorithmus < Abivorbereitung < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:33 Do 09.08.2012 | | Autor: | rubi |
| Aufgabe | Auszug aus einer Abiaufgabe:
Ein lineares Maximierungsproblem führt auf folgendes Simplextableau:
[mm] \vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 & 3 & 70 \\ 0 & 0,2 & 1 & 0 & 0 & -2 & 5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 }
[/mm]
Es gilt x,y,z,u,v,w [mm] \ge [/mm] 0.
Erläutern Sie, warum das Optimierungsproblem mehrere Lösungen besitzt.
Bestimmen Sie alle ganzzahligen Werte von z, für die es optimale Lösungen gibt. |
Hallo zusammen,
leider bin ich beim Simplex-Algorithmus nicht ganz so fit.
Folgendes weiß ich:
Die x, z und v sind Basisvariable und y,w und u sind Nicht-Basisvariable.
Aus dem Simplex-Tableau ergibt sich x = 20, z = 5 und v = 70.
Außerdem ist y = u = w = 0.
Als maximale Größe ergibt sich E = 78000.
Da in der letzten Zeile keine positiven Zahlen mehr stehen, ist ein weiterer Simplex-Schritt nicht notwendig.
Woher erkenne ich jedoch, dass es mehrere Lösungen gibt ?
Ich könnte mir folgenden Weg vorstellen, weiß aber nicht, ob das passt.
Aufgrund der letzten Zeile ergibt sich zwangsläufig u = w = 0, ansonsten würde mein E kleiner werden.
Es bleiben daher noch folgende Gleichungen stehen:
1.Zeile: x + y = 20
2.Zeile: v = 70
3.Zeile: 0,2y + z = 5
Da ich nun ein überbestimmtes LGS habe, gibt es mehrere Lösungen:
1.Fall: z = 5, y = 0 und x = 20
2.Fall: z = 4, y = 5 und x = 15
3.Fall: z = 3, y = 10 und x = 10
4.Fall: z = 2, y = 15 und x = 5
5.Fall: z = 1, y = 20 und x = 0
In allen Fällen wäre v = 70 und als Maximum ergäbe sich E = 78000.
Ist dies so richtig ?
Oder müsste ich mit dem Simplex-Tableau einen Simplexschritt durchführen ?
Falls ja, was wäre dann meine Pivotspalte bzw. Pivotzeile ?
Viele Grüße
Rubi
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
Hallo!
> Auszug aus einer Abiaufgabe:
>
> Ein lineares Maximierungsproblem führt auf folgendes
> Simplextableau:
>
> [mm]\vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 & 3 & 70 \\ 0 & 0,2 & 1 & 0 & 0 & -2 & 5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 }[/mm]
>
> Es gilt x,y,z,u,v,w [mm]\ge[/mm] 0.
> Erläutern Sie, warum das Optimierungsproblem mehrere
> Lösungen besitzt.
> Bestimmen Sie alle ganzzahligen Werte von z, für die es
> optimale Lösungen gibt.
> Hallo zusammen,
>
> leider bin ich beim Simplex-Algorithmus nicht ganz so fit.
>
> Folgendes weiß ich:
> Die x, z und v sind Basisvariable und y,w und u sind
> Nicht-Basisvariable.
> Aus dem Simplex-Tableau ergibt sich x = 20, z = 5 und v =
> 70.
> Außerdem ist y = u = w = 0.
> Als maximale Größe ergibt sich E = 78000.
>
> Da in der letzten Zeile keine positiven Zahlen mehr stehen,
> ist ein weiterer Simplex-Schritt nicht notwendig.
Nun, solange sich in der F-Zeile noch negative Eintragungen befinden, liegt noch keine optimale Basislösung vor.
> Woher erkenne ich jedoch, dass es mehrere Lösungen gibt ?
Im Tableau mit der erhaltenen optimalen Lösung ist für mindestens eine Nichtbasisvariable der Eintrag in der F-Zeile gleich 0. Würde man diese Variable in die Basis aufnehmen, so erhielte man eine weitere optimale Basislösung. Mit zwei optimalen Basislösungen [mm] x_{1} [/mm] und [mm] x_{2} [/mm] sind auch alle durch Konvexkombinationen
[mm] x=\lambda*x_{1}+(1-\lambda)*x_{2}, [/mm] mit [mm] \lambda\in(0,1)
[/mm]
erhältlichen Nichtbasislösungen optimal. Diesen Fall bezeichnet man auch als duale Degeneration, da eine Basisvariable des dualen Problems den Wert 0 besitzt.
> Ich könnte mir folgenden Weg vorstellen, weiß aber nicht,
> ob das passt.
> Aufgrund der letzten Zeile ergibt sich zwangsläufig u = w
> = 0, ansonsten würde mein E kleiner werden.
>
> Es bleiben daher noch folgende Gleichungen stehen:
> 1.Zeile: x + y = 20
> 2.Zeile: v = 70
> 3.Zeile: 0,2y + z = 5
>
> Da ich nun ein überbestimmtes LGS habe, gibt es mehrere
> Lösungen:
> 1.Fall: z = 5, y = 0 und x = 20
> 2.Fall: z = 4, y = 5 und x = 15
> 3.Fall: z = 3, y = 10 und x = 10
> 4.Fall: z = 2, y = 15 und x = 5
> 5.Fall: z = 1, y = 20 und x = 0
> In allen Fällen wäre v = 70 und als Maximum ergäbe sich
> E = 78000.
>
> Ist dies so richtig ?
>
> Oder müsste ich mit dem Simplex-Tableau einen
> Simplexschritt durchführen ?
s.o.
> Falls ja, was wäre dann meine Pivotspalte bzw. Pivotzeile
> ?
Pivotspalte t: Nun, du suchst diejenige Spalte t mit dem kleinsten (negativen) Wert in der F-Zeile.
Pivotzeile s: Bestimme eine Zeile s für die gilt: [mm] \bruch{b_{s}'}{a_{st}'}=min\vektor{\bruch{b_{i}'}{a_{it}'}|i=1,...,m; {mit:} {a_{it}'}>0}
[/mm]
> Viele Grüße
> Rubi
>
> Ich habe diese Frage in keinem anderen Forum gestellt.
Viele Grüße, Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:09 Fr 10.08.2012 | | Autor: | rubi |
Hallo zusammen,
was ist denn eine "optimale Basislösung" ?
Bisher habe ich gedacht (und auch in Schulbüchern so nachgelesen), dass der Simplexalgorithmus bei einem Maximieriungsproblem sein Optimum erreicht hat, wenn in der letzten Zeile (damit ist vermutlich die "F-Zeile" gemeint) keine positiven Zahlen mehr stehen.
Und da dies in dem Tableau der Fall ist, bin ich der Meinung, dass E = 78000 bereits schon das Maximum darstellt.
Ist dies falsch ??
Wenn ich in einem nächsten möglichen Pivotschritt die 2.Spalte (Also y) zur Pivotspalte mache und die erste Zeile als Pivotzeile erhalte ich folgendes Tableau:
[mm] \vmat{ x & y & z & u & v & w & Ergebnis \\ 1 & 1 & 0 & 1 & 0 & -2 & 20 \\ 0 & 0 & 0 & -1 & 1 &3 & 70 \\ 1 & 0 & -5 & 1 & 0 & 8 & -5 \\ 0 & 0 & 0 & -3 & 0 & -1 & E-78000 }
[/mm]
Daraus würde sich ergeben: x = u = w = 0
y = 20, z = 1, v = 70
Und diese Lösung habe ich ja als 5.Fall in meiner ursprünglichen Frage auch gehabt.
Also gibt es für z = 1,2,3,4,5 optimale Lösungen, die jeweils E = 78000 ergeben.
Stimmt das ?
Viele Grüße
Rubi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:07 Sa 11.08.2012 | | Autor: | rubi |
kann mir niemand helfen ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:58 Di 14.08.2012 | | Autor: | rubi |
kann mir jemand helfen ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:58 Di 14.08.2012 | | Autor: | rubi |
das ganze nochmals als Frage, da ich noch keine Antwort bekommen habe.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:50 Mi 15.08.2012 | | Autor: | Stoecki |
hallo ruby,
deine lösung ist in ordnung. du kannst das aber auch direkt ohne berechnung im ersten tableau sehen, dass es weitere lösungen geben muss.
die letzte zeile in deinem tableau gibt dir die sog reduzierten kosten an. ist der wert einer nicht basisvariable 0, so weißt du, dass du diese immer ans pivotspalte verwenden kannst, ohne den zielfunktionswert zu ändern. du kannst dann natürlich die expliziten lösungen so ausrechneen, wie du es gemacht hast.
der kommentar von marcel, dass für optimalität alle eintraäge der letzten zeile nichtnegativ sein müssen stimmt im übrigen nur, wenn man minimiert. von daher ist dein gegebenes tableau optimal.
gruß bernhard
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 Do 16.08.2012 | | Autor: | rubi |
Hallo Bernhard,
danke, deine Antwort hilft mir deutlich weiter.
Ich habe nur noch eine Frage:
Du schreibst
"ist der wert einer nicht basisvariable 0, so weißt du, dass du diese immer ans pivotspalte verwenden kannst, ohne den zielfunktionswert zu ändern"
Ist es nich so, dass die Nicht-Basisvariablen sowieso = 0 gesetzt werden.
Im ersten Tableau sind y = u = w = 0, da sie Nicht-Basisvariable sind.
Kann ich jetzt einfach eine dieser Variablen als Pivotspalte wählen und es bleibt beim optimalen Wert ?
Woher weiß ich dann, dass es unendlich viele Lösungen gibt ?
Viele Grüße
Rubi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:56 Fr 17.08.2012 | | Autor: | Stoecki |
> Hallo Bernhard,
>
> danke, deine Antwort hilft mir deutlich weiter.
>
> Ich habe nur noch eine Frage:
> Du schreibst
> "ist der wert einer nicht basisvariable 0, so weißt du,
> dass du diese immer ans pivotspalte verwenden kannst, ohne
> den zielfunktionswert zu ändern"
>
> Ist es nich so, dass die Nicht-Basisvariablen sowieso = 0
> gesetzt werden.
du missverstehst mich hier. ich meinte in der unteren zeile in deinem tableau. die werte die dort stehen geben die sog. reduzierten kosten an. sind diese null, weißt du dass ein basiswechsel die zielfunktion nicht beeinflusst. du hingegen meintest die werte der entscheidungsvariablen und in dem punkt hast du recht. ws nicht in der basis steht wird auf 0 gesetzt.
> Im ersten Tableau sind y = u = w = 0, da sie
> Nicht-Basisvariable sind.
> Kann ich jetzt einfach eine dieser Variablen als
> Pivotspalte wählen und es bleibt beim optimalen Wert ?
>
> Woher weiß ich dann, dass es unendlich viele Lösungen
> gibt ?
>
> Viele Grüße
> Rubi
gruß bernhard
|
|
|
|
