Simplex Algorithmus - Pivotelement |
| 13.03.2012, 14:11 | Rankor | Auf diesen Beitrag antworten » | ||
| Simplex Algorithmus - Pivotelement Hallo, Ich habe eine vermutlich recht simple Frage zum Simplex Algorithmus: Wenn ich ein Pivot-Element im Tableu gewählt habe, wie wird dann die Zeile im nächsten Schritt verändert. Bisher dachte ich immer, dass ich die ganze Zeile durch das Pivot-Element teilen müsste oder zumindest jedes Element der Zeile (außer Pivot) durch das Ergebnis aus b-Vektor / Pivotelement (wir hatten bisher auch immer nur Beispiele, in denen der b-Vektor == 1 und das Pivot-Element auch == 1 war). Ich habe mich jetzt mit der Lösung der letzten Übungsaufgabe beschäftigt und komme nun gar nicht mehr klar. Wir hatte zuvor die folgende Zeile in unserer Aufgabe. Vor dem ersten Trennstrich die Variablen Mittelere Block = Schlupfvariablen Hinterer Blick = b-Vektor -1 0 0 | -2 3 1 0 | 2 Die Spalte mit der 3 hatte in der z-Zeile noch einen negativen Wert und die 3 ist hier das einzig logisch wählbare Pivotelement. Im nächsten Schritt unserer Simplex wurde in der Lösung die Zeile unverändert hingeschrieben. Warum das? Müsste ich nicht die gesamte Zeile mit 2/3 multiplizieren oder habe ich das nur völlig missverstanden? Ich wäre hier für Hilfe echt dankbar. Und noch eine gaaaanze große Bitte: bitte keine komplizierte Erklärung des Verfahrens - ich bin ein verdammt guter Programmierer (sowohl Hochsprachen, als auch auf Betriebssystemebene), aber ein lausiger Mathematiker. Ich bräuchte hier nur das richtige Vorgehen anhand dieser genannten Zeile. Den Rest bekomme ich dann wieder hin. Meine Ideen: wie gesagt: ich hätte die gesamte Zeile mit Ausnahme des Pivot-Element mit dem Ergebnis von b-Vektor / Pivot (also in diesem Falle 2/3) multipliziert. Da käme dann raus -2/3 0 0 | -4/3 3 2/3 0 | 4/3 |
||||
| 13.03.2012, 18:34 | Kasen75 | Auf diesen Beitrag antworten » | ||
Hallo, Das Pivotelement muss ja 1 werden. Wenn das Pivotelement z.b. 5 ist, dann muss man es durch 5 teilen. Das gleiche gilt dann auch für die Zeile. Das mit dem Bruch ist hilfreich um ein geeignetes Pivoelement zu finden. Im Simplex-Allogorithmus nimmt man die jenige Spalte, die die größte Steigerung in der Zielfunktion verspricht. Beim Maximierungsproblem ist das die kleinste Zahl. Z.B. bei zielfunktionskeoffizienten im Simplextableau: -10 -30 5 -6. Hier wäre die Pivotspalte bei -30. Um jetzt die Pivozeile zu ermitteln nimmt man das Minimum aus wobei sowohl ais als auch bi positiv sein müssen. So viel zur Auswahl von einem Pivoelement. Bei deinem Beispiel soll eine Schlupfvariable als Pivotelement genommen werden. Dies ist jeodoch gar nicht zulässig. Und wenn ich mir die Zeile so anschaue, dann bin ich mir nicht ganz sicher, ob das Gleichungssystem insgesamt eine Lösung hat. Vielleicht habt ihr einfach nur aufgehört und das Gleichungssystem für unlösbar erklärt.
Mein Frage: Warum ist das Pivoelement jetzt nicht 1? Sollte ja so sein, wenn man schon die Schlupfvariable als Pivotelement nimmt. Wenn du noch Fragen, Anmerkungen hast: Bitte poste. Mit freundlichen Grüßen |
||||
| 13.03.2012, 21:01 | Rankor | Auf diesen Beitrag antworten » | ||
Achsoo, ich muss einfach die ganze Zeile durch das Pivot-Element teilen. Danke dafür schon mal. Hmm, bei uns wurde aber irgendwie noch weiter gerechnet. Also zu maximieren war in diesen Beispiel folgende Funktion x1 + x2 + x3 unter der Nebenbedingung x 0 Ich schicke Euch anbei mal unsere Musterlösung als Bild - vielleicht habe ich mein Problem einfach nur doof erklärt/nicht verstanden oder da ist wirklich ein Fehler drinne, wenn das okay ist. Lieben Gruß Edit: Und ja, der Übertragungsfehler oben ist mir aufgefallen =) |
||||
| 13.03.2012, 22:20 | Kasen75 | Auf diesen Beitrag antworten » | ||
Hallo, Man kann/muss ein Schlupfvariable als Pivotelement nehmen, wenn wie hier x1 nicht genommen kann, da bi/ais negativ ist. Die Zielfunktion weist jetzt nur noch postitive Koeffizienten auf, d. h. der Zielfunktionswert kann nicht verbessert werden. Die optimale Lösung ist also x1=0, x2=2, x3=5/3, x4=0, x5=2/3, x6=0, x7=0 mit dem Zeilfunktionswert 11/3. Man kann gut sehen, dass sich an den Zielfunktionswerten orientiert worden ist, bei der Auswahl der Pivot-Spalte. Und bei der Pivot-Spalte wurden auch nur die positiven Brüche aus bi/ais berücksichtigt und daraus der kleinste Bruch ausgewählt. Ich hoffe du siehst ein bischen klarer. Wenn du noch ein kronkrete Frage hast, bitte stelle sie. Mit freundlichen Grüßen |
||||
| 15.03.2012, 15:55 | Rankor | Auf diesen Beitrag antworten » | ||
Nochmals vielen, vielen Dank! Eine weitere Frage ist mir nun doch noch gekommen. Sowohl in unseren Vorlesungsfolien, als auch in allen Übungen wurde das Pivot-Element irgendwie immer 1:1 übernommen...war das Pivot-Element eine 2, stand im nächsten Tableau wieder eine 2... Gibt es eine Situation oder ein "Unterverfahren" des Simplexverfahren, in welchem das eine gültige Operation (Exception: Pivot == 1) ist, oder liegt hier ein Fehler in der Semester-Veranstaltung vor? liebe Grüße Rankor |
||||
| 15.03.2012, 17:29 | Kasen75 | Auf diesen Beitrag antworten » | ||
Hallo, Für die Lösung macht es letztendlich keinen Unterschied ob da steht: -1 0 0 | -2 3 1 0 | 2 oder -1/3 0 0 | -2/3 1 0 | 2/3 In den einem Fall sind drei mal gleich 2. Und in dem anderen Fall ist einmal gleich 2/3. Kommt auf das gleiche heraus. Wir haben immer das Pivot-Element auf 1 normiert. Wenn man den Simplex-Algorithmus streng auslegt, sollte man das Pivot-Element immer auf 1 normieren. Eigentlich auch beim letzten Pivot-Element. Aber am Besten mal nachfragen, was gewünscht ist. Mit freundlichen Grüßen |
||||
| Anzeige | ||||
|
|
||||
| 16.03.2012, 22:27 | Rankor | Auf diesen Beitrag antworten » | ||
Danke! Deine Hilfe ist echt klasse! Hilft gerade nicht nur mir, sondern noch ein paar Anderen hier =) Und eine Frage habe ich noch, die sich mir noch nicht erschlossen hat: -> Wenn ich Maxmierungsproblem habe, lese ich ja das Ergebnis der Zielfunktion direkt aus dem Tableau ab. -> Was mache ich, wenn ich ein Minimierungsproblem habe? Muss der Wert dann immer negativ sein? -> Muss er ggf. bei Maximierung immer positiv sein (hatte noch nie einen Fall, bei dem es anders war) Lieben Gruß |
||||
| 18.03.2012, 13:46 | Mystic | Auf diesen Beitrag antworten » | ||
Was wäre für dein Optimierungsproblum das Minimum? Ist dieses positiv? Was wäre, wenn man die 4. Nebenbedingung (die hier sowieso wegen der ersten redundant ist und ersatzlos gestrichen werden könnte!) abändert in Was wäre dann das Maximum? Ist dieses positiv? |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
