Frage zu Modul/Klausur Simplex-Algorithmus

Studiengang
B.Sc. Wirtschaftsinformatik
ECTS Credit Points
70 von 180
Hallo zusammen,

ich stehe ein wenig auf dem Schlauch:

Ich habe, auf mein Nachfragen hin, eine Info vom Lehrstuhl erhalten.

---

Meine Frage war:


Wenn in der Aufgabenstellung in der Klausur steht, dass wir uns das Lösungverfahren aussuchen können, reicht es dann aus, den Simplex-Algorithmus auch ohne Hilfsspalten durchzuführen oder ist es gewünscht, immer mit Hilfsspalten zu arbeiten?

Antwort des Lehrstuhls:

Wenn in der Klausur steht, dass Sie ein Verfahren Ihrer Wahl benutzen duerfen,
so heisst dies, dass Sie ein fuer dieses Problem sinnvolles (!) Verfahren
nutzen sollen.
Zum Beispiel ist bei einem linearen Optimierungsproblem mit fuenf Variablen in
der Regel die grafische Methode nicht sinnvoll, weil sie (ohne Vereinfachungen
des Problems auf ein Problem mit zwei Variablen) nicht anwendbar ist.
Ebenso kommt es bei der Anwendung vom Simplexalgorithmus darauf an, ob man aus
dem Problem schon eine zulaessige Startbasis ablesen kann, dann kann man
direkt mit Phase II anfangen, ansonsten muss man eine Phase I vorschalten (und
demgemaess das Hilfsproblem fuer Phase I benutzen und die Hilfsspalten
auffuehren).

Also: wenn Sie den Zwei-Phasen-Simplex-Algorithmus benutzen (und dieser ist
sehr oft erforderlich!), so muessen Sie in Phase I natuerlich auch immer die
Hilfsspalten auffuehren, sonst sind Ihre Tableaus schon vom Ansatz her falsch.


-----

Meine Fragen hierzu:

  1. Woran erkenne ich, dass mein Starttableau bzw. dass Optimierungsproblem falsch ist und ich somit Hilfsspalten einfügen muss?
  2. Woran erkenne ich, wie viele Hilfsspalten ich dazunehmen muss?
  3. Wann kann ich die Hilfsspalten "löschen"?


Ich bedanke mich schon mal vorab für eure Mühe!

VG
 
Ich kann mich nicht mehr recht erinnern, denke aber, dass Simplex mit Gleichungen funktioniert. Wenn Deine Bedingungen jetzt Ungleichungen enthalten, dann müssen sie in Gleichungen überführt werden indem der Teil vom ungleich zum gleich mit einer Schlupfvariablen ausgeglichen (dargestellt) wird. Die müssen im Tableau mitgeführt werden. So jedenfalls meine blasse Erinnerung.
Ich denke jedenfalls, dass es feste Bedingungen gibt für simplex (muss man kennen) und wenn die nicht erfüllt sind muss man was tun, damit es wieder passt und das merkt man dann schon.
LG Teresa
 
Genau das was Teresam sagt. Du brauchst die Schlupfvariablen für die Ungleichungen. Hast du davon drei, brauchst du auch drei. Hast du nur Gleichungen brauchst du keine Schlupfvariablen. Dann gäbe es aber auch kein Optimierungsproblem.

Die Wahl des Verfahrens bezieht sich auf rechnerisch vs zeichnerisch.

such mal bei yt nach the simple math. Damit hatte ich gelernt.
 
Hallo zusammen,

ich habe noch eine Frage bezüglich des Simplex-Algorithmus, konkret zu einem Schritt aus einer alten Klausur:

Es handelt sich um Klausur 1142KS09, Aufgabe 8. Folgender Schritt aus der ML ist mir nicht ganz klar:

Warum wurde hier angegeben, dass man bei dem Schritt nur eine Möglichkeit hat zu pivotisieren (also das Kästchen um 1/2). Ich habe es so verstanden dass man von Spalte 1 anfängt und das man dann immer die nächste Spalte zum pivotieren dazunimmt (also erst Spalte 1, rechnen. Dann Spalte 2, rechnen, dann Spalte 3 rechnen.....)

upload_2019-2-18_15-45-0.png



Meine Vermutung ist, dass ich die zweite Spalte nicht pivotisieren muss, da in der ZF-Zeile bereits ein negativer Wert steht. Ist das so?
Warum steht in der ML, dass man nur eine Möglichkeit hat zu pivotisieren (die 1/2 in dem Kästchen) ?

Kann mir da jemand helfen?

Vielen Dank!
 
Methode
KOCHREZEPT SIMPLEX-ALGORITHMUS:


1. Bestimme die Pivot-Spalte
Suche hierzu die Spalte mit dem größten Zielfunktionskoeffizienten

2. Bestimme die Pivot-Zeile

•teile alle Elemente der rechten Seite durch die – streng positiven – Elemente der Pivot-Spalte

•nimm das Minimum der Zahlen aus a.

3. Bestimme das Pivot-Element

Dies befindet sich im Schnittpunkt aus Pivotspalte und Pivotzeile

4. Dividiere die Elemente der Pivotzeile durch das Pivotelement

Dadurch wird das Pivotelement zu eins

5. Mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements selbst – zu null

Subtrahiere geeignete Vielfache der Pivotzeile von den jeweiligen Zeilen des Tableaus.
 
Die oberste Spalte enthält die Zielfunktionswerte, ganz rechts befindet sich die Spalte Rechte Seite oder Spalte. Das Pivotelement kann überall sein, es liegt am höchsten ZF-Wert. Mal auf you tube gucken.
 
Methode
KOCHREZEPT SIMPLEX-ALGORITHMUS:


1. Bestimme die Pivot-Spalte
Suche hierzu die Spalte mit dem größten Zielfunktionskoeffizienten

2. Bestimme die Pivot-Zeile

•teile alle Elemente der rechten Seite durch die – streng positiven – Elemente der Pivot-Spalte

•nimm das Minimum der Zahlen aus a.

3. Bestimme das Pivot-Element

Dies befindet sich im Schnittpunkt aus Pivotspalte und Pivotzeile

4. Dividiere die Elemente der Pivotzeile durch das Pivotelement

Dadurch wird das Pivotelement zu eins

5. Mache alle Elemente der Pivotspalte – mit Ausnahme des Pivotelements selbst – zu null

Subtrahiere geeignete Vielfache der Pivotzeile von den jeweiligen Zeilen des Tableaus.



Vielen Dank für deine Hilfe. Ich habe gerade gesehen, dass es im vorheringen Schritt (gleiche Aufgabe), nicht passt (also größter ZF-Koeffizient):

upload_2019-2-19_7-56-20.png
 
Hast du dir das mal aufgemalt? Das sind mehrere Geraden die sich schneiden. Du läufst dann quasi die Ecken ab um die Optimallösung zu finden.
Ob du aber rechts rum oder links rum gehst ist egal. Du kannst in der ZF Spalte immer das größte oder immer das kleinste Element nehmen. Musst es dann nur durchziehen. Du kannst res ja mal versuchen, das Ergebnis wird das gleiche sein.
 
Ok super, vielen Dank!

Wenn ich eine Hilfszeile habe, richte ich mich dann trotzdem an dem größten oder kleinste ZF-Wert oder muss ich auch die Werte aus der Zeile beachten?
 
Zuletzt bearbeitet:
Zurück
Oben