Simplex-Algorithmus: Pivotelement/-zeile

ich hätte mal eine Frage zur Wahl des Pivotelements im Simplex-Algorithmus. Welche Zeile nehme ich da? Eigentlich müsste es doch egal sein welche Zeile (außer die erste) man nimmt, um entsprechend nullen bzw. einsen zu erzeugen. Und dies sollte möglichst einfach sein..

2. Frage: Muss ich unbedingt die Schlupfvariablen (bei den Nebenbedingungen) mitnehmen? Ich habe nämlich mal ohne beigebracht bekommen.. In der EA hatte ich es auch so auf die alte Weise gemacht (Obwohl im Aufgabentext explizit Simplex-Algorithmus stand) und es gab keinen Fehlerabzug oder dergleichen..

Vielen Dank im Voraus

"Peter" 🙂
Die Frage ob du die Schlupfvariablen mitnehmen musst, kann ich dir nicht beantworten, sorry.

Wahl der Zeile:
Erstmal: Die Spalte wählt man nach dem höchsten Deckungsbeitrag aus (bzw. niedrigstem Wert in der Z-Spalte...wurde ja umgestellt, sodass die Deckungsbeiträge negativ ins Anfangstableau reingeschrieben werden)

Die Zeile wählst du dann aus, indem du den Wert ganz rechts aus deinem Tableau nimmst und ihn durch das Element teilst, welches in gleicher Zeile in der Pivot-Spalte steht.
Das machst du für jede Zeile. Dort wo du den niedrigsten Wert rausbekommst, das ist deine Pivot-Zeile.

Nochmal ein Beispiel:
Nebenbedingung1: x1 + x2 = 50
Nebenbedingung 2: 3x1 + 8x2 = 80
Dann steht in Zeile 1 ganz Rechts die 50.
Und in Zeile 2 ganz rechts die 80.

Nehmen wir an in der Pivotspalte steht in Zeile 1 der Wert 2.
Und in in Zeile 2 der Wert 5.

Jetzt gehst du wie folgt vor:
min( 50/2 ; 80/5 ).
Deine Pivotzeile wäre also die zweite Zeile, weil 16 < 25.

Kommt bei zwei Zeilen das gleiche raus, darfst du frei wählen.
Aber NIE eine Zeile zweimal als PivotZeile verwenden. Das gleiche gilt für die Spalte.

So, hoffe das war halbwegs verständlich.
Gruß
Max

MaxTB schrieb:

[...]
Aber NIE eine Zeile zweimal als PivotZeile verwenden. Das gleiche gilt für die Spalte.
[...]

Zum Vergrößern anklicken....

das habe ich noch nicht gehört, weißt du warum das so ist? Spalte sollte eigentlich eh nicht passieren, denke ich aber Zeile könnte ja theoretisch sein.

Es wäre unlogisch eine Zeile zweimal zu verwenden. Durch die Pivotschritte hast du ja bei x1 oder bei x2 eine 1 stehen. Dein Ziel ist es ja bei x1 und x2 (bis xn) eine 1 stehen zu haben, aber eben immer in verschiedenen Zeilen.
Ich habe mir den Simplex durch Tutorial-Videos auf Youtube beigebracht. Da sind ein paar richtig gute dabei (auch mit interpretation etc.) Dort wurde das auch einmal erklärt. Und ich habe das mal geprüft, es passt immer.

P.S. Cooler Nickname

ah, okay, das macht schon sinn.

P.S. danke, bist du auch ein fan des spiels? 😉
hab mir gleich mal noch den passenden avatar besorgt.

Kurze frage zur pivolzeile.

Um diese zu bestimmten muss ich ja die werte ganz rechts durch dir werte in der pivotspalte teilen.

Darf ich denn auch durch negative werte teilen? Dann wäre die zeile nämlich die pivotzeile, denn 0 / (-1/4) = 0.

Durch 0 darf nicht geteilt werden, das ist klar. Aber 0 durch etwas anderes schon..auch durch etwas negatives?

die zeile der zielfunktion ist nie pivotzeile, falls das deine frage beantwortet.

Leider nicht.

Das meinte ich nicht. Um die zeile herauszufinden, teilt man doch durch die werte aus der spalte. Darf man durch negative werte teilen?

hm, theoretisch würd ich sagen ja. war diese zeile denn schon mal pivotzeile? normal ist es ja nie dieselbe zeile 2 mal. eigentlich ist es ja auch egal welche zeile man nimmt. dauert halt nur länger aber man kommt auch zum ergebnis. kannst ja mal etwas rumprobieren.

also durch Null und negative zahlen darfst du nie teilen! (nur durch streng positive Werte)

Ob du Null durch irgendetwas teilen darfst kann ich jetzt nicht 100%ig sagen...
Ich hab mal das Beispiel aus der Klausur vom 20.09.13 "so" durchgerechnet und bei der ersten Auswahl der Pivotzeile nicht die erste (150/1=150) genommen sondern die zweite (0/4=0) und komme dann nicht auf das .ideale Ergebnis! (sondern auf 125x1 und 500x2 mit DB von 6000)
Begründen kann ich diese Aussage jetzt aber nicht... ist für mich aber Grund genug darauf zu verzichten!
--> vielleicht kann jemand anderes eine mathematische Erklärung dazu liefern? würde mich auch interessieren!

grüße

Gerhard

Aber x0=6000 x1=125 x=500 sind doch die korrekten Ergebnisse

sorry, leider nicht...
x1=150, x2= 476,92 und x0=6215,38 sind die korrekten Ergebnisse!
kannst du auch ohne Simplex relativ einfach sehen...
x1 muss aufgrund des höheren DB maximal (=150Einheiten) produziert werden. somit werden 150 x 12 = 1800 EH Rohstoffe verbraucht, bleiben also noch 8000 - 1800 = 6200 für x2 übrig.
somit können noch 6200 / 13 = 476,923 Stk. von x2 produzert werden.
DB ergibt das dann 16x150 + 8 x 476 = 6208ct

schau mal hier:
https://www.studienservice.de/fernuni-hagen/67743/seite-2

der tutor in hamburg hat das jedenfalls so vorgerechnet und hatte als ergebnis die zuvor genannten ergebnisse

hmm... seltsam...

ich hoffe ich hab mir keinen Blödsinn eingelernt!! 😱
Im Forum für die Klausur (Klausur 26.09.13 Lösung) wird auch dieses Ergebnis als korrekt dargestellt...

Machiavelli hat den kompletten Simplex hochgeladen... und nach meinem Wissensstand stimmt die Berechnung...

https://www.studienservice.de/dokument/9351/

vor allem da der Deckungsbeitrag definitv höher ist und alle NBs eingehalten werden...??

😕:confused

@levivo ich weiß nicht ob du´s gesehen hast, aber im Nachbarthema wurde der Simplex nochmal besprochen und meine Aussage hier ist falsch! schau dir bitte hier das hochgeladene Dokument an:

https://www.studienservice.de/fernuni-hagen/67743/seite-3#post-1113748

Grüße Gerhard

Danke!

Also zusammengefasst für die bestimmung der pivotzeile:

- Durch 0 teilen verboten.

- 0 durch etwas teilen erlaubt

- durch negative zahlen teilen verboten