Nicht eindeutige Pivotspalte beim Simplex-Algorith

Aufrufe: 2211     Aktiv: 12.09.2018 um 14:02
0
Ich habe bei einem Maximierungsproblem folgende Zielfunktion: z=10x+10y Im Ausgangstableau des Simplex-Algorithmus erhalte ich ja dann in der letzten Zeile -10        -10
  1. Wie entscheide ich denn nun welche von den beiden Spalten die Pivotspalte ist?
2. Da schließt sich für mich die Frage an wie sieht es aus wenn es dann zwei gleiche Quotienten gibt und somit die Pivotzeile nicht eindeutig identifizierbar ist? Ich habe zwei Lehrbücher. In dem einen steht dass man den Quotienten nur für diejenigen Werte des Tableauinneren bildet die positiv sind. Im anderen steht, der Quotient der die Pivotzeile bestimmt ist derjenige, der kleinste positive Quotient ist. Nun hab ich außen rechts am Tableau den Wert -2 und in der Pivotspalte den Wert -3/5. Laut dem einen Buch müsste ich den Quotienten bilden und er wäre auch positiv und sogar der kleinste; also der der die Pivotzeile bestimmt. Laut dem anderen Buch dürfte ich den Quotienten aber gar nicht bilden weil der zugehörige Wert in der Pivotspalte ja negativ ist: 3. Was ist denn jetzt richtig?
Diese Frage melden
gefragt

Lehrer/Professor, Punkte: 81

 
Kommentar schreiben
4 Antworten
0

Hallo,

gibt es denn noch Nebenbedingungen zu deinem Problem?

Denn die Funktion \(f(x,y)=10x+10y\) hat kein (globales) Maximum.

“Im Ausgangstableau des Simplex-Algorithmus erhalte ich ja dann in der letzten Zeile

-10        -10”

Damit wärst du dann fertig (aber das kann nicht sein, da die Funktion wie oben erwähnt kein globales Maximum besitzt).

Du erreichst die Optimale Lösung , sobald die Zielfunktion keine positiven Koeffizienten mehr enthält.

Vielleicht hilft dir das hier weiter.

 

Zu deiner zweiten Frage: Du suchst nach dem Stichwort Entartung. Siehe hier und hier.

 

Zur 3. Frage kann ich nicht viel sagen, da ich die besagten Bücher nicht habe. Es könnte durchaus sein, dass beide Möglichkeiten Zielführend sind.

So wie ich es kenne, wählt man den kleinsten, nicht negativen Quotienten (der nicht null ist). 

 

Noch Fragen?

 

Gruß,

Gauß

 

 

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 1.99K

 
zur 3. Frage
wenn ich nun ganz rechts außen einen negativen Wert habe und in der gleichen Zeile in der Pivotspalte auch einen negativen Wert:
Beispiel:

...      -3 ...   ....    ....   .... ... | -2

Bilde ich dann den Quotienten oder nicht? Das Ergebnis wäre ja positiv   ─   valkyrion 12.09.2018 um 15:55
Ok, das hat sich mit dem einen Link von Dir (https://www2.htw-dresden.de/~mvoigt/v4-3-6.pdf">htw Dresden, S. 54) geklärt. Wenn ich in der letzten Spalte einen negativen Wert habe, habe ich einen Fehler gemacht!   ─   valkyrion 12.09.2018 um 16:31

Kommentar schreiben

0
  grafisch komme ich schon auf eine Lösung:   Ich wollte die Aufgabe eben mal mit dem Simplex-Algorithmus nochmal nachrechnen.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 81

 

Kommentar schreiben

0
Man ist dann fertig, wenn in der letzten Zeile nur noch negative Werte vorkommen!? Kommt das nicht darauf an, wie man die Zielfunktion ins Tableau überführt hat? Wenn man die Koeffizienten der Zielfunktion eins zu eins ins Tableau überführt (also ohne Vorzeichenwechsel), dann ja, dann ist man dann fertig, wenn in der letzten Zeile nur noch negative Werte vorkommen. Der Gewinn hat dann aber auch noch ein negatives Vorzeichen. Wenn man aber Zielfunktionskoeffizienten vorzeichenvertauscht ins Tableau übernimmt, hat der Gewinn am Ende schon das richtige Vorzeichen; fertig ist man dann aber doch dann, wenn in der letzten Zeile nur noch positive Werte stehen!? (ich glaube der Dresden Link geht auch diesen Weg, da er die Pivotspalte über den kleinsten negativen Wert auswählt (S. 53)    
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 81

 

Da hast du recht. Ich bin davon ausgegangen, dass du es direkt übernommen hast. Aber klar, wenn du die Vorzeichen tauschst, dann stehen in der letzen Zeile nur noch positive Werte. Das Vorzeichen des Gewinns kannst du ja einfach tauschen, wenn du dein Ergebnis abließt. 

   ─   carl-friedrich-gauss 12.09.2018 um 16:50

Kommentar schreiben

0

Dazu führt man am besten Schlupfvariablen ein.

Deine Nebenbedingungen werden somit zu

\(y+s_{1}=4\)

\(y+3x+s_{2}=18\)

\(5y+3x+s_{3}=30\)

Jetzt Stellst du das Tableau auf:

x y s1 s2 s3 |

0 1  1   0    0 |4

3 1  0  1    0|  18

3 5  0  0   1|  30

----------------- -

10 10  0  0  0 |z

Nun wählst du eine der Spalten mit der 10 aus, nehmen wir also einfach gleich die erste Spalte. Um die Zeile zu finden, müssen wir die rechte Seite mit den Einträgen in der Spalte dividieren.

Division mit 0 nicht möglich -> Weglassen. 18/3=6 ist der kleinste Quotient. Daher ist unsere Zeile die 2te. und damit 3 unser Pivotelement.

Wir dividieren nun die 2te Zeile durch 3 und führen den Gauß-Algorithmus durch, um oberhalb und unterhalb des Pivotelements Nullen zu erzeugen. Wir erhalten dann:

x    y     s1    s2    s3 |

0    1     1     0         0 |4

1  1/3   0  1/3    0   | 6

0   4     0     -1    1|  12

----------------- -

0   20/3  0  -10/3  0|z-60

Gleiches Prozedere wie oben und wir erhalten die 2te Spalte, 2 Zeile und somit 4 als neues Pivotelement.

Nun wieder Division der 3ten Zeile mit 4 und Anwendung des Gauß-Algorithmus um die Nullen zu erzeugen liefert:

x y s1     s2          s3 |

0 0  1     1/4    -1/4 |1

1 0  0     5/12    -1/12|  5

0 1  0     -1/4      1/4|  3

----------------- -

0 0  0     -5/3      -5/3 |z-80

Jetzt können wir Ablesen, dass das Maximum 80 beträgt und an der Stelle \((x,y)=(5,3)\) erreicht wird.

Ich hoffe, es war verständlich.

Gruß,

Gauß

 

PS: ich hoffe, dass ich mich jetzt nicht verrechnet habe. 

Die Stelle und der Wert passen jedoch auf dein Optimierungsproblem.

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 1.99K

 
Is es denn allgemein egal, welche der Spalten mit 10 ich auswähle?   ─   tweekzter 12.11.2019 um 09:56

Kommentar schreiben