Pivotisieren/Simplexalgorith. < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:44 Fr 03.07.2009 | | Autor: | Owen |
| Aufgabe | Bestimmen Sie rechnerisch mit Hilfe des Simplexalgorithmus das Maximum der Zielfunktion [mm] Z(x_{1},x_{2})=x_{1}+2*x_{2} [/mm] unter den Nebenbedingungen [mm] x_{1}\ge0,x_{2}\ge0 [/mm] und
[mm] x_{1}+2*x_{2}\le9
[/mm]
[mm] x_{1}+x_{2}\le5
[/mm]
[mm] x_{2}\le3
[/mm]
[mm] x_{1}\le4 [/mm] |
Hallo Leute, ich habe eine eher allgemeine Frage. Beim Simplexalgorithmus verwendet man ja das Pivotisierungsverfahren. Hier ist mein Anfangstableau:
[mm] \pmat{ 1 & 2 & 1 & 0 & 0 & 0 | 9 \\ 1 & 1 & 0 & 1 & 0 & 0 | 5 \\ 0 & 1 & 0 & 0 & 1 & 0 | 3 \\ 1 & 0 & 0 & 0 & 0 & 1 | 4 \\ - & - & - & - & - & - & - \\ -1 & -2 & 0 & 0 & 0 & 0 | 0}
[/mm]
So, nun wähle ich in [mm] a_{32} [/mm] mein Pivoelement (1). Ich muss also mittels Zeilenoperationen in den restlichen Zeilen (Zeilen 1,2,5) eine 0 erzeugen. Ich habe mich bei der Erzeugung der Nullen in den Zeilen 1 und 2 bei den Zeilenoperationen auf die Pivozeile bezogen. Ich habe nämlich folgendes gerechnet: [mm] Z_{1}\to Z_{1}-2*Z_{3} [/mm] ; [mm] Z_{2}\to Z_{2}-Z_{3}. [/mm] Diese Zeilenumformungen waren dann vom Ergebnis her auch richtig. Bei der Zielfunktionszeile jedoch habe ich mich nicht! auf die Pivozeile bei den Zeilenoperationen bezogen. ZFZ [mm] \to ZFZ+Z_{1}. [/mm] Die daraus entstandene Zielfunktionszeile war [mm] \pmat{ 0 & 0 & 1 & 0 & 0 & 0 | 9}, [/mm] und dies war falsch. Es hätte richtigerweise [mm] \pmat{ -1 & 0 & 0 & 0 & 2 & 0 | 6} [/mm] heißen müssen. Ich habe dann nach den Gründen für mein falsches Ergebnis gefragt und bekam als Antwort, dass ich mich hätte auch hier bei den Zeilenoperationen auf meine Pivozeile beziehen müssen. Nun zu meiner Frage: Muss ich mich bei allen Operationen zur Erzeugung von Nullen immer auf die Pivozeile auf irgendeine Weise beziehen? Und ist das nur beim Simplexalgorithmus so oder ist das bei Pivotisierungsverfahren generell immer so? Angenommen ich wende das Pivotisierungsverfahren zur Bestimmung des Rangs einer Matrix an. Muss ich mich auch hier bei den Zeilenumformungen immer auf meine Pivozeile beziehen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:42 Sa 04.07.2009 | | Autor: | Disap |
Hallo!
> Bestimmen Sie rechnerisch mit Hilfe des Simplexalgorithmus
> das Maximum der Zielfunktion [mm]Z(x_{1},x_{2})=x_{1}+2*x_{2}[/mm]
> unter den Nebenbedingungen [mm]x_{1}\ge0,x_{2}\ge0[/mm] und
>
> [mm]x_{1}+2*x_{2}\le9[/mm]
>
> [mm]x_{1}+x_{2}\le5[/mm]
>
> [mm]x_{2}\le3[/mm]
>
> [mm]x_{1}\le4[/mm]
> Hallo Leute, ich habe eine eher allgemeine Frage. Beim
> Simplexalgorithmus verwendet man ja das
> Pivotisierungsverfahren. Hier ist mein Anfangstableau:
> [mm]\pmat{ 1 & 2 & 1 & 0 & 0 & 0 | 9 \\ 1 & 1 & 0 & 1 & 0 & 0 | 5 \\ 0 & 1 & 0 & 0 & 1 & 0 | 3 \\ 1 & 0 & 0 & 0 & 0 & 1 | 4 \\ - & - & - & - & - & - & - \\ -1 & -2 & 0 & 0 & 0 & 0 | 0}[/mm]
Hier wäre es interessant zu wissen, welche Basis du überhaupt gewählt hast.
> So, nun wähle ich in [mm]a_{32}[/mm] mein Pivoelement (1). Ich muss
> also mittels Zeilenoperationen in den restlichen Zeilen
> (Zeilen 1,2,5) eine 0 erzeugen. Ich habe mich bei der
> Erzeugung der Nullen in den Zeilen 1 und 2 bei den
> Zeilenoperationen auf die Pivozeile bezogen. Ich habe
> nämlich folgendes gerechnet: [mm]Z_{1}\to Z_{1}-2*Z_{3}[/mm] ;
> [mm]Z_{2}\to Z_{2}-Z_{3}.[/mm] Diese Zeilenumformungen waren dann
> vom Ergebnis her auch richtig. Bei der Zielfunktionszeile
> jedoch habe ich mich nicht! auf die Pivozeile bei den
> Zeilenoperationen bezogen. ZFZ [mm]\to ZFZ+Z_{1}.[/mm] Die daraus
> entstandene Zielfunktionszeile war [mm]\pmat{ 0 & 0 & 1 & 0 & 0 & 0 | 9},[/mm]
> und dies war falsch. Es hätte richtigerweise [mm]\pmat{ -1 & 0 & 0 & 0 & 2 & 0 | 6}[/mm]
> heißen müssen. Ich habe dann nach den Gründen für mein
> falsches Ergebnis gefragt und bekam als Antwort, dass ich
> mich hätte auch hier bei den Zeilenoperationen auf meine
> Pivozeile beziehen müssen.
Richtig.
> Nun zu meiner Frage: Muss ich
> mich bei allen Operationen zur Erzeugung von Nullen immer
> auf die Pivozeile auf irgendeine Weise beziehen?
Sehr lobenswert von dir, dass du $ZFZ [mm] \to ZFZ+Z_{1}$ [/mm] aufgeschrieben hast, sonst hätte ich nicht verstanden, was du willst.
Jedenfalls funktioniert das so wirklich nicht, denn die Zielfunktionszeile berechnet sich bei jedem (neuen) Simplextableau neu, aus den Pivotzeilen.
Das heisst:
Man wählt das Pivotelement, so wie du das gemacht hast; verändert dann die Pivotzeile so, dass überall sonst nur Nullen stehen (war alles richtig, wie du das beschrieben hast); und währenddessen geschieht mit der Zielfunktionszeile aber nichts! Und auch mit dem Zielfunktionswert nicht; aber die rechte Seite hat sich bereits verändert, also die Spalte 9,5,3,4.
Das bezeichne ich als neues Simplextableau, bei dem du jetzt nur noch die Zielfunktionszeile und Zielfunktionswert berechnen musst. Aber die berechnet sich ja bekanntlich anders (also dort darf man keine Zeile dazuaddieren)
> Und ist
> das nur beim Simplexalgorithmus so oder ist das bei
> Pivotisierungsverfahren generell immer so? Angenommen ich
> wende das Pivotisierungsverfahren zur Bestimmung des Rangs
Pivotisierungsverfahren? Was meinst du damit? Ich verstehe darunter die Strategie, wie man das Pivot auswählen soll (Auswahlregel von Bland z. B. ) aber das meinst du höchstwahrscheinlich nicht.
> einer Matrix an. Muss ich mich auch hier bei den
> Zeilenumformungen immer auf meine Pivozeile beziehen?
Da man da denselben Algorithmus verwendet, würde ich sagen, dein Vorgehen ist generell falsch, auch in diesem Fall.
MfG
Disap
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 So 05.07.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
