Letzte Woche war ich kurz vorm Verzweifeln. Es ist ja normal, dass man sich die Studienhefte anschaut und die Aufgaben, Formeln etc. zwar teilweise komplex, aber dennoch irgendwie nachvollziehbar sind. Aber was im EBWL-Studienheft 2 ab Seite 31 los war, raubte mir ja echt den letzten Nerv!
Das Simplexverfahrenist ja schon kompliziert genug, aber wenn man dann noch vor einem Gleichungssystem mit 5 Gleichungen und 7 Variablen sitzt, das Optimum erst nach der 4. Umformung erreicht ist und im Studienheft nur das Ausgangstableau, die erste Umformung und das Enttableau zu finden sind, fragt man sich schon: Äh, und was ist mit den anderen Tabelaus (2. + 3. Umformun). Ganz zu schweige von den Lösungswegen, die im Studienheft eher schlecht, als recht erklärt werden.
D.h. für Menschen, die sich auch sonst gerne mit dem Auflösen von Simplextabelaus beschäftigen ist das sicherlich ein Klacks, aber für Doofe, wie mich ist es eine Herausforderung. Ich war diese Woche also ziemlich nervös und unruhig, was ich der Tatsache zu verdanken hatte, dass ich weder das Verfahren 100%ig verstanden habe, noch wusste, wie ich auf die Lösung aus dem Endtableau komme.
In meiner Verzweiflung habe ich einen Post auf studienservice.de verfasst und auf Hilfe gewartet. Ich habe mich sehr gefreut, als ich 3 Mails mit Hilfsangeboten erhalten habe. Eine Email hat mich besonders gefreut, in der sich jemand die Mühe gemacht hat, mit das Verfahren ausführlich zu erklären und mir auch noch eine eingescannte, handschriftliche Umformung des Tableaus von der 1. bis zur 2. Umformung mitgeschickt hat.
Das hat mir schon etwas weitergeholfen, jedoch den Schalter nicht wirklich umgelegt, sodass ich auch die 3. und 4. Umformung hätte alleine berechnen können. Im Internet bin ich zwar auf viele Erläuterungen und Beispiele dazu gestoßen, aber die haben mich eher noch mehr verwirrt, als mir das Simplexverfahren näher zu bringen. Aber eine Sache habe ich schon herausgefunden: Es ist definitiv von Vorteil, wenn man sich mit dem Gaußschen Eliminationsverfahren, bzw. mit dem Gauß Algorithmus auskennt. Aber: Lang, lang ist es eher (obwohl ich erst 25 bin). Ich führe es einfach mal auf mein schlechtes Langzeitgedächtnis zurück… ;).
Mir ging es aber in erster Linie darum, mit dem geringsten Aufwand dieses Beispiel aus dem Studienheft zu verstehen (Minimalprinzip). Nach stundenlangem Suchen und Verzweifeln bin ich auf einen Link gestoßen, der mir wirklich weitergeholfen hat. Dort waren Beispiele und interaktive Aufgaben zum Ausprobieren aus dem Kurs „Einführung in die Betriebswirtschaftslehre“ von Prof. Hering zu finden! Juhuu! Unter „Simulationen und Animationen“ > Kurseinheit 2 ist auch ein Beispiel zum Umformen eines Simplextableaus. Und es wird noch besser: Das Beispiel behandelt exakt das selbe Tableau, mit den selben Gleichungen, wie in den Studienheften. Zwar wird dort nur erklärt, wie man das Simplextableau von der 1. Umformung in die 2. Umformung bringt, aber dafür wird das Prinzip super erklärt. Und wenn man das Prinzip erstmal verstanden hat, dann sind die 3. und 4. Umformung (bis zum Endtableau) auch kein Problem mehr.
Ich möchte daher das Beispiel aus den Studienheften hier nochmal aufführen und in allen wichtigen Schritten aufzeigen, wie man die Simplexmatrix umformt, bzw. vom Ausgleichtabelau in das Endtableau führt. Da das Ausgangstableau später insgesamt vier mal umgeformt werden muss, könnte dieser Post etawas länger werden…aber dafür garantiert bis ins Detail erklärt ;).
Für alle, die es etwas kürzer mögen, habe ich noch das kleine PDF Simplextableau-Umformung für Dummies erstellt, in der die wesentlichen Umformungsschritte kurz & bündig zusammengefasst sind. Ansonsten geht es jetzt hier mit der vollständigen Aufgabe weiter ;):
Beispiel Simplexverfahren
In der 2. Kurseinheit des Moduls EBWL geht es um folgenden Linearen Optimierungsansatz:
Zielfunktion (ZF):
- ZF: max. GDB; GDB:= 40X2 + 20X4
Nebenbedingungen:
- I: 20X2 + 7X4 <= 1400
- II: 7X2 + 10 X4 <= 1600
- III: 8X2 + 2X4 <= 500
- IV: X2 <= 50
- V: X4 <= 150
- VI: X2, X4 >= 0 (Nichtnegativitätsbedingungen)
Das Optimierungsproblem kann sowohl graphisch, als auch rechnerisch (mit dem Simplexverfahren) gelöst werden.
Graphische Optimierung
Die graphische Optimierung möchte ich nur kurz erwähnen, um die spätere rechnerische Lösung besser veranschaulichen zu können. Auf graphische Weise löst man das Optimierungsproblem, indem man die Nebenbedingungen in ein X2/X4-Koodinationssystem einträgt. Dadurch erhält man einen Raum zulässiger Lösungen, in welchem sich das Optimum befinden muss, also der Punkt, an dem der DB am höchsten ist (siehe rotes X).
Wie man aus dem Bild jetzt schon ungefähr ablesen kann, liegt das Optimum für X2 bei etwa 20 und für X4 bei etwa 145.
Der Gesamt-Deckungsbeitrag läge demnach bei etwa:
GDB = (40 x ca. 20) + (20 x ca. 145) = ca. 800 + ca. 2900 = ca. 3700
Doch anhand der Simplexmethode lässt sich die richtige und vor allem exakte Lösung rechnerisch bestimmen.
Rechnerische Lösung angand der Simplexmethode
Die Rechenschritte des Simplexverfahrens sind in einem Gleichungssystem vorzunehmen. Daher gilt es zunächst einmal, die o.g. Ungleichungen in Gleichungen umzustellen. Dies geschieht durch das Hinzufügen von sog. „Schlupfvariabeln“ (s1 bis s5).
Beispiel:
Die Nebenbedingung I: 20X2 + 7X4<= 1400 ist eine Ungleichung weil das Ergebnis nur kleiner oder gleich 1400 ist, aber dadurch auch nicht genau 1400 ist oder sein muss. Diese Nebenbedingung wird nun von einer Ungleichung zu einer Gleichgung gemacht, indem man die Schlumpfvariable s1 hinzufügte. Das Ergebnis lautet dann I: 20X2 + 7X4 + S1 = 1400. Die Schlupfvariablen stehen für freie/nicht beanspruchte Kapazitäten (der Rohstoff- oder Absatzmengen) bis zur entsprechenden Obergrenze.
Der Gesamteckungsbeitrag, der sich aus der Formel:
GDB: 40X2 + 20X4
ergibt, ist formal als Schlupfvariable der Zielfunktion anzusehen:
ZF: GDB – 40X2 – 20X4 =0
X2 und X4 sind hierbei sog. Strukturvariablen oder Nichtbasisvasiablen und s1 bis s5 die Basisvariablen. Die Nichtbasisvariablen werden gleich Null gesetzt, da man sich (graphisch betrachtet) vom Koordinatenursprung der richtigen Lösung annähert. Dort sind x2 und x4 gleich Null.
Demnach ergibt sich folgendes Gleichungssystem, welches sich aus der Zielfunktion und den Nebenbedingungen ergibt:
- ZF: GDB -40X2 – 20X4 =0
- I: 20X2 + 7X4 +s1 = 1400
- II: 7X2 + 10 X4 + s2 = 1600
- III: 8X2 + 2X4 + s3 = 500
- IV: X2 + s4= 50
- V: X4 + s5 = 150
- VI: X2, X4, s1, s2, s3, s4, s5 >= 0
Das Gleichungssystem besteht also (ohne Berücksichtigung der Zielfunktion und der Nebenbedingungen) aus 5 Gleichungen (I-IV) und 7 Variablen (X2, X4, s1, s2, s3, s4, s5)).
Ziel des Simplex-Optimierungsverfahrens ist es nun, den DB der Zielfunktion (ZF) zu erhöhen. Das Optimum, bzw. der maximale DB befindet sich (wie aus der Grafik ersichtlich) irgendwo innerhalb des Lösungsraums, welcher durch die Nebenbedingungen eingeschränkt ist, bwz. aus diesen konstruiert werden kann. Die optimale Lösung muss ggf. in mehreren Schritten gefunden werden und mindestens einen Eckpunkt des zulässigen Lösungsraums beinhalten.
Methode des Simplexverfahrens:
Ausgehend von einer Basislösung geht man von Eckpunkt zu Eckpunkt des zulässigen Lösungsraums und schaut, ob damit schon die optimale Lösung gefunden ist. Die einfachste zulässige Basislösung ist der Koordinatenursprung. Hierfür werden die Strukturvariablen X2 und X4 als Nichtbasisvariablen gleich Null gesetzt (Nullproduktion). Die Werte der Schlupfvariablen sind als Basisvariablen direkt aus dem Ausgangstableau ablesbar.
Ausgangstableau
Im Ausgangtableau werden die ZF, sowie die Nebenbedinungen I – V eingetragen:
Das Ausgangstabelau enthält in der Kopfzeile die Strukturvariablen x2 und x4, sowie die Schlupfvariablen s1 bis s5. In der linken Spalte sind die Schlupfvariablen s1 bis s5 nochmal als Basisvariablen zu sehen. In der Zielfunktionszeile kann man den Gesamtdeckungsbeitrag (GDB) ablesen, der im Ausgangstableau noch Null ist (siehe grünes Feld unter „RS“). „RS“ steht hierbei für rechte Seite der Gleichung, also was nach dem Gleichzeichen stehen würde.
Die Basis- und Ausgangslösung lautet (wenn X2 und X4 = 0): s1=1400, s2=1600, s3=500, s4=50, s5=150. Der GDB lautet auch Null. Kann dieser noch erhöht werden? Sicher, denn wenn man X2 und X4 erhöhen würde, würde auch der DB steigen.
Die Optimallösung ist solange nicht gegeben, solange X2 und X4 negativ sind. In unserem Fall sind sowohl X2, als auch X4 noch negativ. Das Ausgangstableau ist demnach nicht optimal. Man versucht nun, solange von Eckpunkt zu Eckpunkt des Lösungsraums zu gelangen, bis das Optimum gefunden ist und die Koeffizienten der Zielfunktion keinen negativen Wert mehr aufweisen.
Das Austauschverfahren
Zum Finden der Optimallösung geht man nun von Eckpunkt zu Eckpunkt, indem man eine aktuelle Basisvariablen durch eine aktuelle Nichtbasisvariable austauscht. Die Basisvariablen stehen in der ersten Zeile (X2 bis s5) und nicht Nichtbasisvariablen sind in der linken Spalte zu finden (s1 bi s5). Nun wird ausgetauscht.
Wo fängt man an? Woher weiß man, welche Nichtbasisvariable zur Basisvariablen werden soll?
Man sucht sich zunächst die Nichtbasisvariable aus, die in die Basis treten soll. Das ist die BV, welche den größten Zuwachs an DB verspricht. In unserem Fall ist es X2. Aus dem Tableau wählt man daher die BV mit dem höchsten negativen Wert.
Die Spalte mit dem höchsten negativen Koeffizienten (in diesem Fall X2) nennt man Pivotospalte. Diese ist im Ausgangstableau grau markiert. Die Spalte X2 wird also zur neuen Basisvariablen. Nun gilt es die Zeile auszuwählen, an deren Stelle X2 jetzt treten soll. Welche aktuelle Basisvariable wird jetzt zur Nichtbasisvariablen? Hier wählt man die Zeile mit dem niedrigsten Quotienten aus der Spalte „RS“ und dem jeweiligen Zeilenwert der Pivotspalte. Hierbei werden nur positive Pivotspaltenwerte berücksichtigt. Man rechnet also:
- Q von I: 1400/20 = 70
- Q von II: 1600/7 = 228,57
- Q von III:500/8 = 62,5
- Q von IV: 50/1 =50
Ein Quotient aus der ZF wird nicht gebildet, weil der Spaltenwert negativ ist (-40) und ein Quotient aus der Gleichung V wird nicht gebildet, weil er Null beträgt und ein Teilen durch Null nicht zulässig ist.
Nun wählt man den kleinsten der errechneten Quotienten, in diesem Fall ist es der Quotient der Basisvariablen s4. Die dazugehörige Zeile nennt man Pivotzeile, diese ist im Ausgangstableau ebenfalls grau markiert. Der Schnittpunkt zwischen Pivotspalte und Pivotzeile ist das Pivotelement.
Durch Umformung tritt die Pivotspalte später an die Basis. D.h. die Beschriftung der Pivotspalte (in diesem Fall X2) tritt an die Stelle der Beschriftung der Pivotzeile (s4). Es findet ein sogenannter Basistausch statt, denn dadurch, dass X2 von einer Nichtbasisvariablen zu einer Basisvariablen wird, tritt sie an die Basis. Das ist später im Simplextableau nach der 1. Umformung zu sehen (Update: 16.02.11).
1. Umformung
Da der Deckungsbeitrag im Ausgangstableau noch Null ist (siehe grünes Feld) und Koeffizienten der Zielfunktion (ZF) noch negativ sind, kann der DB durch eine erste Umformung erhöht werden. Wir haben hierzu bereits Pivotspalte, Pivotzeile und das Pivotelement bestimmt. Nun geht es ans Umformen.
1. Schitt: Das Pivotelement muss durch Multiplikation/Division der gesamten Pivotzeile eine 1 werden.
Im Ausgangstableau ist das Pivotelement bereits eine 1, sodass wir uns diesen Schritt sparen können.
2. Schritt: Ist das Pivotelement eine 1, müssen alle anderen Elemente der Pivotspalte (durch Addition/Subtraktion) zu einer Nullwerden. Dieser Schritt ist etwas komplizierter aber wenn man ihn erstmal verstanden hat, geht alles (fast) wie von selbst ;).
Fangen wir mal ganz oben bei der Zeile mit der ZF an: Dort ist der Wert der Pivotspalte noch -40. Er muss nun durch Addion, bzw. Subtraktion eine Null ergeben. Dies erreicht man logischerweise mit der Rechenoperation +40 (-40 + 40 = 0). Doch auch die anderen Zeilenwerte müssen umgeformt werden. Wie formt man z.B. den benachbarten Zeilenwert -20 um? Dies geht so:
Neuer Zeilenwert= (+40 x Spaltenwert der Pivotzeile) + aktueller Zeilenwert = (+40 x 0) + (-20) = -20
Genauso geht man mit den anderen Werten in der Zeile vor. Man nimmt also immer den umgekehrten Wert des Feldes, der Null werden muss, also hier +40. Diesen multipliziert man dann mit dem Wert, der sich aus aktueller Spalte und dem Wert der Pivotzeile ergibt und addiert ihn dann anschließend zum bisherigen Zeilenwert. Für die gesamte Zeile GDB ergeben sich folgende Rechenwege, analog zu dem obigen:
- Feld ZF/s1 = (40 x 0) + 0 = 0
- Feld ZF/s2= (40 x 0) + 0 = 0
- Feld ZF/s3= (40 x 0) + 0 = 0
- Feld ZF/s4= (40 x 1) + 0 = 40
- Feld ZF/s5 =(40 x 0) + 0 =0
- Feld ZF/RS= (40 x 50) + 0 =2.000
Die erste Zeile wäre damit umgeformt. Jetzt macht man mit der Zeile s1 weiter. Hier haben wir den Wert 20, der ebenfalls durch Addition/Subtraktion zu Null werden muss. Dies erreichen wir mit der Rechenoperation -20, denn: 20 – 20 = 0. Die anderen Felder dieser Zeile s1 ergeben sich wie folgt:
- Feld s1/X4 = (-20 x 0) + 7 = 7
- Feld s1/s1= (-20 x 0) + 1 = 1
- Feld s1/s2= (-20 x 0) + 0 = 0
- Feld s1/s3= (-20 x 0) + 0 = 0
- Feld s1/s4 =(-20 x 1) + 0 =-20
- Feld s1/s5= (-20 x 0) + 0 =0
- Feld s1/RS= (-20 x 50) + 1400 =400
Ebenso verfährt man mit der nächsten Zeile s2. Hier muss man den vom Zeilenwert in der Pivotspalte (7) die Zahl 7 substrahieren, um auf Null zu kommen. Die weiteren Rechenschritte für die Felder der Zeile s2 lauten demnach:
- Feld s2/X4 = (-7 x 0) + 10 = 10
- Feld s2/s1= (-7 x 0) + 0 = 0
- Feld s2/s2= (-7 x 0) + 1 = 1
- Feld s2/s3= (-7 x 0) + 0 = 0
- Feld s2/s4 =(-7 x 1) + 0 = -7
- Feld s2/s5= (-7 x 0) + 0 = 0
- Feld s2/RS= (-7 x 50) + 1600 = 1.250
In der Zeile s3 werden die Zeilenwerte mit der Rechenoperation -8 neu bestimmt, damit der Wert der Zeile s3 in der Pivotspalte zur Null wird:
- Feld s3/X4 = (-8 x 0) + 2 = 2
- Feld s3/s1= (-8 x 0) + 0 = 0
- Feld s3/s2= (-8 x 0) + 0 = 0
- Feld s3/s3= (-8 x 0) + 1 = 1
- Feld s3/s4 =(-8 x 1) + 0 = -8
- Feld s3/s5= (-8 x 0) + 0 = 0
- Feld s3/RS= (-8 x 50) + 500 = 100
Die Zeile s4 wurde zur neuen Nichtbasisvariablen, an deren Stelle die vorherige Nichtbasisbariable X2 getreten ist.
Daher beenden wir die 1. Umformung bei Zeile s5. Auch hier muss nicht mehr gerechnet werden, da der Wert der Zeile s5 in der Pivotspalte bereits 0 beträgt.
Die neue Simplextabelle nach der 1. Umformung ergibt sich aus den eben errechneten Werten:
Nach der 1. Umformung beträgt der Deckungsbeitrag schon 2.000 € (siehe grünes Feld) und wurde im Vergleich zum Ausgangstableau verbessert. Kann das Ergebnis nach der ersten Umformung noch weiter verbessert werden? Ja, denn noch sind nicht alle Koeffizienten der Zielfunktion (ZF) positiv. X4 ist mit -20 immer noch negativ. Daher geht es wieder von vorne los.
Wie vorher bereits erwähnt, wurde die vorherige Nichtbasisvariable durch Basistausch zur Basisvariablen. Da wo vorher in der linken Spalte s4 stand, steht jetzt X2. In der ganz oberen Zeile ändert sich dabei nichts. Diese bleibt immer gleich.
2. Umformung
Ausgehend vom Tableau nach der 1. Umformung formen wir nun ein zweites Mal um, mit dem Ziel, den DB weiter zu erhöhen und uns der optimalen Lösung anzunähern. Der größte negative Wert der Zielfunktion wäre mit X4 = -20 gefunden. Daher ist das unsere neue Pivotspalte (grau hinterlegt). Zur Bestimmung der neuen Pivotzeile berechnen wir wieder die Quotienten aus der Spalte „RS“ und der neuen Pivotspalte (nur bei Werten > O), also:
- Q von I: 400/7 = 57,14286
- Q von II: 1250/10 = 125
- Q von III: 100/2 = 50
- Q von V: 150/1 =150
Da der Wert bei ZF -20 und bei IV Null ist, wird für diese kein Quotient berechnet.
Auch hier wählt man anschließend wieder den kleinsten Quotienten, der bei Gleichung III zu finden ist (50). Die Pivotzeile wäre damit mit s3 bestimmt, das Pivotelement ist 2.
Auch hier geht es wieder ans umformen. Zuerst muss das Pivotelement durch Multiplikation/Division zur 1 werden. Dies erreichen wir, indem wir alle Werte der Zeile s3 durch 2 teilen:
Jetzt müssen noch die neuen Zeilenwerte bestimmt werden. Hierbei geht man analog zur ersten Umformung vor. Fangen wir ganz oben an. Zuerst muss der Wert der Pivotspalte in der Zeile ZF Null werden. Noch beträgt er -20. Wir nehmen also den Rechenschritt +20 vor. Die Rechenschritte zur Bestimmung der neuen Werte für die weiteren Felder der Zeile ZF lauten:
- Feld ZF/X2 = (20 x 0) + 0 = 0
- Feld ZF/s1= (20 x 0) + 0 = 0
- Feld ZF/s2= (20 x 0) + 0 = 0
- Feld ZF/s3 =(20 x 0,5) + 0 = 10
- Feld ZF/s4= (20 x -4) + 40 = -40
- Feld ZF/s5= (20 x 0) + 0 = 0
- Feld ZF/RS= (20 x 50) + 2000 = 3.000
Die neuen Werte der Zeile ZF nach 2. Umformung sehen im Tableau dann so aus:
Genauso geht man mit den anderen Zeilen (s1, s2 und s5 vor).
Bei der Zeile s1 rechnet man mit -7, damit der Wert in der Pivotspalte (7) zu Null wird:
- Feld s1/X2 = (-7 x 0) + 0 = 0
- Feld s1/s1= (-7 x 0) + 1 = 1
- Feld s1/s2= (-7 x 0) + 0 = 0
- Feld s1/s3 =(-7 x 0,5) +0 = -3,5
- Feld s1/s4= (-7 x -4) + (-20) = 8
- Feld s1/s5= (-7 x 0) + 0 = 0
- Feld s1/RS= (-7 x 50) + 400 = 50
Für Zeile s2 rechnet man mit -10:
- Feld s2/X2 = (-10 x 0) + 0 = 0
- Feld s2/s1= (-10 x 0) + 0 = 0
- Feld s2/s2= (-10 x 0) + 1 = 1
- Feld s2/s3 =(-10 x 0,5) +0 = -5
- Feld s2/s4= (-10 x -4) + (-7) = 33
- Feld s2/s5= (-10 x 0) + 0 = 0
- Feld s2/RS= (-10 x 50) + 1250 = 750
Für die Zeile s3 rechnen wir nichts, da das die Pivotzeile ist. In der Zeile X2 beträgt der Wert der Pivotspalte bereits 0, sodass auch hier nicht mehr umgeformt werden muss. In der Zeile s5 muss aber noch umgeformt werden, da der Wert der Pivotspale hier noch 1 beträgt, aber zur Null umgeformt werden muss. Man rechnet hier mit -1.
- Feld s5/X2 = (-1 x 0) + 0 = 0
- Feld s5/s1= (-1 x 0) + 0 = 0
- Feld s5/s2= (-1 x 0) + 0 =0
- Feld s5/s3 =(-1 x 0,5) + 0 = -0,5
- Feld s5/s4= (-1 x -4) + 0 = 4
- Feld s5/s5= (-1 x 0) + 1 = 1
- Feld s5/RS= (-1 x 50) + 150= 100
Nach Umformung aller Zeile ergibt sich ein neues Simplextableau nach 2. Umformung:
Wie man an dem grünen Feld sieht, haben wir den DB im Vergleich zum Simplextableau nach der ersten Umformung wieder erhöht (von 2.000 auf 3.000 €). Geht´s noch besser? Hierzu stellt sich wieder die Frage: Gibt es in der Zielfunktion (ZF) noch negative Koeffizienten?
Ja. S4 beträgt noch -40 und daher kann der maximale DB, bzw. das Optimum noch nicht erreicht sein. Es geht also wieder von vorne los. Da s4 den höchsten (in diesem Fall auch einzigen) negativen Koeffizienten hat, ist s4 die neue Pivotspalte. Zur Bestimmung der Pivotzeile teilen wir wieder die Werte der Spalte RS durch die Werte der Pivotzeile, die größer als Null sind also:
- Q von I: 50/8 = 6,25
- Q von II: 750/33 = 22,72727
- Q von IV: 50/1 = 50
- Q von V: 100/4 =25
Der kleinste Koeffizient ist 6,25 in der Zeile s1. Die Zeile s1 ist daher die neue Pivotzeile, das neue Pivotelement beträgt 8. Jetzt geht es zur 3. Umformung, ausgehend vom Simplextableau nach der 2. Umformung.
3. Umformung
Zuerst formen wir das Pivotelement wieder in eine 1 um, indem wir alle anderen Werte der Pivotzeile durch 8 teilen:
Jetzt müssen alle anderen Werte ober- und unterhalb der 1 in Nullen umgeformt werden.
Wir fangen wieder bei der Zeile ZF an. Hier muss der Zeilenwert in der Pivotspalte mit 40 addiert werden, um Null zu ergeben. Die Rechenschritte für die anderen Felder der Zeile ZF lauten demnach:
- Feld ZF/X2 = (40 x 0) + 0 = 0
- Feld ZF/X4= (40 x 0) + 0 = 0
- Feld ZF/s1= (40 x 0,125) + 0 = 5
- Feld ZF/s2 =(40 x 0) + 0 = 0
- Feld ZF/s3= (40 x -0,4375) + 10 =-7,5
- Feld ZF/s5= (40 x 0) + 0 = 0
- Feld ZF/RS= (40 x 6,25) + 3000 = 3250
Genauso geht man in den anderen Zeilen s2, X4, X2 und s5 vor. Die Rechenschritte für die nächste Zeile, s2 lauten:
- Feld s2/X2 = (-33 x 0) + 0 = 0
- Feld s2/X4= (-33 x 0) + 0 = 0
- Feld s2/s1= (-33 x 0,125) + 0 = -4,125
- Feld s2/s2 =(-33 x 0) + 1 = 1
- Feld s2/s3= (-33 x -0,4375) + (-5) = 9,4375
- Feld s2/s5= (-33 x 0) + 0 = 0
- Feld s2/RS= (-33 x 6,25) + 750 = 543,75
Für die nächste Zeile X4 lautet die Umformung:
- Feld X4/X2 = (4 x 0) + 0 = 0
- Feld X4/X4= (4 x 0) + 1 = 1
- Feld X4/s1= (4 x 0,125) + 0 = 0,5
- Feld X4/s2 =(4 x 0) + 0 = 0
- Feld X4/s3= (4 x -0,4375) + 0,5 = -1,25
- Feld X4/s5= (4 x 0) + 0 = 0
- Feld X4 /RS= (4 x 6,25) + 50 = 75
Für die darunter liegende Zeile x2 rechnen wir:
- Feld X2/X2 = (-1 x 0) + 1 = 1
- Feld X2/X4= (-1 x 0) + 0 = 0
- Feld X2/s1= (-1 x 0,125) + 0 = -0,125
- Feld X2/s2 =(-1 x 0) + 0 = 0
- Feld X2/s3= (-1 x -0,4375) + 0 = 0,4375
- Feld X2/s5= (-1 x 0) + 0 = 0
- Feld X2/RS= (-1 x 6,25) + 50 = 43,75
In der letzten Zeile s5 muss der Pivotspaltenwert mit 4 subtrachiert werden, um Null zu ergeben. Die anderen Zeilenwerte errechnen sich aus:
- Feld s5/X2 = (-4 x 0) + 0 = 0
- Feld s5/X4= (-4 x 0) + 0 = 0
- Feld s5/s1= (-4 x 0,125) + 0 = -0,5
- Feld s5/s2 =(-4 x 0) + 0 = 0
- Feld s5/s3= (-4 x -0,4375) + (-0,5) = 1,25
- Feld s5/s5= (-4 x 0) + 1 = 1
- Feld s5/RS= (-4 x 6,25) + 100 = 75
Somit wären alle Zeilen umgeformt. Das Simplextableau nach der 3. Umformung sieht dann so aus:
Der DB beträgt, wie man der Ziefunktionszeile entnehmen kann jetzt 3250 € und wieder fragen wir uns: Ist damit schon das Optimum, also der maximal erreichbare DB erreicht? Nein, denn ein Wert der Zielfunktion ist noch negativ, nämlich s3. Wir müssen also noch einmal umformen und s3 ist unsere neue Pivotspalte. Die neue Pivotzeile ermitteln wir wieder, indem wir den niedrigsten positiven Quotienten aus der Spalte RS und den positiven Werten der Pivotspalte errechnen:
- Q von II: 543,75/9,4375 = 57,61589
- Q von IV: 43,75/0,4375 = 100
- Q von V: 75/1,25 =60
Der niedrigste Quotient ist daher in der Zeile s2 zu finden, welche dann unsere Pivotzeile ist. Das Pivotelement lautet: 9,4375.
Wie in den anderen Umformungen bereits gehabt, muss zuallererst das Pivotelement zu einer 1 werden. Wir dividieren also alle Elemente der Pivotzeile durch 9,4375:
Das Pivotelement beträgt nun eins. jetzt müssen auch noch die Zeilen umgeformt werden, sodass alle Werte über und unter dem Privotelement Null werden.
Dies erreichen wir durch Umformungen, analog zu den bereis vorgenommenen. In der Zeile ZF rechnen wir:
- Feld ZF/X2 = (7,5 x 0) + 0 = 0
- Feld ZF/X4= (7,5 x 0) + 0 = 0
- Feld ZF/s1= (7,5 x -0,437086) + 5 = 1,72185
- Feld ZF/s2 =(7,5 x 0,106) + 0 = 0,795
- Feld ZF/s4= (7,5 x 0) + 0 = 0
- Feld ZF/s5= (7,5 x 0) + 0 = 0
- Feld ZF/RS= (7,5 x 57,61589) + 3250 = 3.682,119
Man kann eigentlich jetzt, nach Umformung der Zeile ZF, schon sehen, dass kein Wert der Zielfunktion mehr negativ ist:
Damit kann man also sagen, dass der DB mit 3.682,12 € sein Maximum erreicht hat. Kein Koeffizient der Zielfunktion ist mehr negativ und somit wäre das Simplexverfahren beendet.
Der Vollständigkeit halber hier noch die Umformungen für die verbleibenden Zeilen s4, X4, X2 und s5.
Für Zeile s4 (mit +0,4375):
- Feld s4/X2 = (0,4375 x 0) + 0 = 0
- Feld s4/X4= (0,4375 x 0) + 0 = 0
- Feld s4/s1= (0,4375 x -0,437086) + 0,125 = -0,0662
- Feld s4/s2 =(0,4375 x 0,106) + 0 = 0,046
- Feld s4/s4= (0,4375 x 0) + 1 = 1
- Feld s4/s5= (0,4375 x 0) + 0 = 0
- Feld s4/RS= (0,4375 x 57,61589) + 6,25 =31,45695
Für Zeile X4 (mit +1,25):
- Feld X4/X2 = (1,25 x 0) + 0 =0
- Feld X4/X4= (1,25 x 0) + 1 = 1
- Feld X4/s1= (1,25 x -0,437086) + 0,5 = 0,0464
- Feld X4/s2 =(1,25 x 0,106) + 0 = 0,1325
- Feld X4/s4= (1,25 x 0) + 0= 0
- Feld X4/s5= (1,25 x 0) + 0 = 0
- Feld X4/RS= (1,25 x 57,61589) + 75 =147,0199
Für Zeile X2 (mit -0,4375):
- Feld X2/X2 = (-0,4375 x 0) + 1 =1
- Feld X2/X4= (-0,4375 x 0) + 0 = 0
- Feld X2/s1= (-0,4375 x -0,437086) + (-0,125) =0,06623
- Feld X2/s2 =(-0,4375 x 0,106) + 0 = -0,05
- Feld X2/s4= (-0,4375 x 0) + 0= 0
- Feld X2/s5= (-0,4375 x 0) + 0 = 0
- Feld X2/RS= (-0,4375 x 57,61589) + 43,75 =18,453
Für Zeile s5 (mit -1,25):
- Feld s5/X2 = (-1,25 x 0) + 0 =0
- Feld s5/X4= (-1,25 x 0) + 0 = 0
- Feld s5/s1= (-1,25 x -0,437086) + (-0,5) =0,04636
- Feld s5/s2 =(-1,25 x 0,106) + 0 = -0,13
- Feld s5/s4= (-1,25 x 0) + 0= 0
- Feld s5/s5= (-1,25 x 0) + 1 = 1
- Feld s5/RS= (-1,25 x 57,61589) + 75 =2,980132
Das Endtableau nach 4. Umformung lautet entsprechend:
Da in der Zielfunktion keine negativen Koeffizienten mehr vorhanden sind, ist die optimale Lösung gefunden, der Deckungsbeitrag ist bei 3682,12 € maximal. Wenn wir uns an die graphische Lösung am Anfang erinnern, kommt das gut hin ;). Die Werte für X4 und X2, bei denen der DB maximal ist lauten:
X4 = 147,0199
X2 = 18,54305
Damit wäre das Gleichungssystem mit dem Simplexverfahren gelöst.
Fazit
Ich bin froh, dass ich es letztendlich doch einigermaßen verstanden habe und freue mich, dass der Großteil der anderen Kurseinheiten nur aus Text besteht ;). Ich habe jetzt genug vom Rechnen und hoffe, denjenigen, die sich mit der Simplexmethode, bzw. dem Beispiel aus der Kurseinheit 2 den Kopf zerbrechen, etwas geholfen zu haben.
Nachtrag vom 21.07.2011
Eine kleine Ergänzung zum Kommentar von Stefan vom 19.07.:
In diesem Beispiel wird ein lineares Optimierungsproblem behandelt, in welchem die Zielfunktion, bzw. der Gesamtdeckungsbeitrag (GDB) maximiert werden sollen und der Lösungsraum durch alle Nebenbedingungen eingeschränkt werden kann. Durch das Einfügen der Schlupfvariablen (s1-s5) in jede Nebenbedingung kann dann das „<=“-Zeichen durch ein „=“-Zeichen ersetzt werden.
Diese Umformung ist notwendig, denn das System muss erst in eine sog. „Standardform“ gebracht werden.
Diese sieht in „kanonischer Form“ wie folgt aus:
max cTx
Ax ≤ b
x ≥ 0
In „Standarform“ werden alle Ungleichungen durch Einfügen von Schlupfvariablen in Gleichungsform gebracht. Dabei müssen alle Variablen die Nichtnegativitätsbedingung erfüllen:
min cTx
Ax = b
x ≥0
Jedes Lineare Problem muss in diese Standardform gebracht werden. Nun kann es aber auch Fälle geben, bei denen es nicht so einfach ist. Folgende Probleme könnte auftreten:
- Zielfunktion soll minimiert statt maximiert werden
- Es gibt Variablen ohne Nichtnegativitätsbedingung
- Es gibt Nebenbedingungen, die eine Gleichung sind
- Es gibt Nebenbedingungen, die eine Ungleichung sind, die aber „≥“ statt „≤“ fordern
Lösungen:
- Ist ein Minimierungsproblem, statt eines Maximierungsproblems gegeben, müssen alle Koeffizienten c der Zielfunktion negiert, also durch ein Minuszeichen zu einem negativen Wert gemacht werden.
- Gibt es Variablen ohne Nichtnegativitätsbedingung, muss man diese in zwei Komponenten aufspalten. Für jedes xi werden zwei neue Variablen xi‚ ≥0 und xi“ ≥ 0 eingeführt. Alle xi werden dann durch xi‚- xi“ ausgetauscht. Zusätzlich wird die Nebenbedingung xi‘, xi“ ≥0 zum LP hinzugefügt.
- Gleichungsbedingungen der Form Ax = b werden zu Ungleichungen gemacht, indem man Ax = b durch Ax ≤ b und Ax ≥ b und, bzw. Ax ≤ b und (-A)x ≤ -b ersetzt.
- Ungleichungen mit ≥ statt ≤ werden in Standardform gebracht, indem man einfach beide Seiten mit (-1) multipliziert.
Mit diesen Transformationen ist es möglich, jedes lineare Optimierungsproblem in die Standardform zu bringen.
Tipp: Mehr Infos und ein ausführliches Beispiel zum Simplex-Algorithmus gibt es in diesem Online-Tutorial von Lecturio.de.
Dafür gehört dir der Nobelpreis!!!
Suuuuuuuuper!!!
Liebe Grüße!
Jasi
Hey Jasi,
tausend Dank für das Kompliment ;).
Freut mich, dass sich die Mühe gelohnt hat 😀
Liebe Grüße,
Alicia
Hi,
eine wirklich schöne Ausarbeitung! Aber ich kapiere einfach nicht, nach welcher Regel sich die erste, linke Spalte im Tableau von anfangs
s1, s2, s3, s4, s5
auf
s1, s2, s3, x2, s5
dann später auf
s1, s2, x4, x2, s5
und schließlich auf
s4, s2, x4, x2, s5
ändert. Warum wird das so gemacht? Auf der Seite 7 im PDF-Dokument steht zwar „Die Zeile s4 wurde zur neuen Nichtbasisvariablen, an deren Stelle die vorherige Nichtbasisvariable x2 getreten ist“, doch ich werde nicht schlau daraus, warum gerade diese Variable derart verändert wird.
Kannst Du das bitte noch einmal etwas deutlicher erläutern? – Es wäre eine riesige Hilfe für mich (und vielleicht auch für andere?)!
Vielen lieben Dank im Voraus,
Simon
Hallo Alicia,
vielen Dank für Deine Ausarbeitung; das war sicherlich sehr viel Arbeit. Aber eine Sache fehlt noch, damit das Ganze perfekt wird: Nach welcher Regel werden denn die Spaltenvariablen von anfangs GDB, s1, s2, s3, s4, s5 auf GDB, s1, s2, s3, x2, s5 und dann später weiter auf GDB, s1, s2, x4, x2, s5 und dann ganz zum Schluss auf GDB, s4, s3, x4, x2, s5 geändert?
Zurzeit sehe ich da überhaupt keinen Zusammenhang und verstehe daher nicht, wie Du die Aufgabe zur Lösung führst.
Vielen lieben Dank im Voraus,
Swen
Hey Swen,
danke für den Hinweis! Ich habe die Sache mit dem Basistausch jetzt im Artikel ergänzt und auch das PDF auf aktuellen Stand gebracht ;).
Beim Basistausch tritt die Pivotspalte an Stelle der Pivotzeile (von der Beschriftung her). Daher ändert sich die Beschriftung der ganz linken Spalte nach jeder Umformung, bzw, nach jedem Basistausch. Die oberste Zeile bleibt immer gleich.
Viele Grüße,
Alicia
Hey Simon,
vielen Dank für deinen Kommentar und die Nachfrage!
Die linke Spalte ändert sich nach jeder Umformung. Und zwar so, dass die Pivotspalte (vorher Nichtbasisvariable) dann zur Basisvariablen wird.
D.h. die Beschriftung der Pivotspalte (x2, x4, s1, s2, s3, s4,s5) wird bei Umformung zur Beschriftung der Pivotzeile und überschreibt diese.
Beispiel:
In der 1. Umformung ist x2 die Pivotspalte und s4 die Pivotzeile. Dann wird umgeformt und am Schluss der Umformung tritt x2 an Stelle von s4. In der ganz oberen Zeile ändert sich dabei nichts. Dort steht weiterhin (x2, x4, s1, s2, s3, s4,s5). Nur in der ganz linken Spalte steht jetzt statt vorher (s1, s2, s3, s4,s5) -> jetzt (s1, s2, s3, x2,s5). Weil s4 sozusagen durch x2 getauscht wurde.
Ausgehend von dem neuen Tableau macht man jetzt weitere Umformungen, sodass immer die Beschriftung der (neuen) Pivotspalte durch die Beschriftung der (neuen) Pivotzeile getauscht wird.
Diesen Tausch nennt man dann „in die Basis treten“ oder „Basistausch“. Bei der 1. Umformung tritt x2 „an die Basis“.
Dieser Basistausch entspricht dem „von Ecke zu Ecke“ des zulässigen Lösungsraums Gehens und der Optimierung des Zielfunktionswert.
Hoffe, dir damit etwas geholfen zu haben ;)!
Viele Grüße,
Alicia
Super, vielen lieben Dank für die Erläuterungen!
Wenn Du übrigens das PDF überarbeitest, dann schaue doch mal, ob sich auf Seite 4 nicht ein Fehler eingeschlichen hat. Dort steht:
o ZF: GDB -40X2 + 7X4 + S1 =0
o II: 7X2 + 10 X4 + s1 = 1600
Aber müsste es denn nicht richtigerweise wie folgt lauten:
o ZF: GDB -40X2 -20X4 =0 (ohne s)
o II: 7X2 + 10 X4 + s2 = 1600 (anstatt s1)
Oder stehe ich da immer noch auf dem Schlauch?
Viele Grüße,
Simon
Hey Simon,
du hast Recht, s1 gehört in Gleichung I und s2 in Gleichung II. In der Gleichung der ZF seht keine Schlupfvariable. Ich habe das im Gleichungssystem jetzt geändert.
Im PDF wird die 2. Umformung als Beispiel verwendet, sodass das Ursprungs-Gleichungssystem dort nicht vorkommt. Im PDF ist das Ausgangstableau also das Tableau aus diesem Artikel nach 1. Umformung.
Vielen Dank für den Hinweis & Liebe Grüße,
Alicia
Nochmals „Simon“ hier!
ich habe mich in einer Sache vertan und möchte kurz Klarheit in das evtl. entstandene Durcheinander bringen: Dieser oben stehende Blog-Text von Dir wurde von mir als PDF ausgedruckt. Mit den Blog-Einträgen bis zum 14.02.2011 entstanden so insgesamt 17 Seiten. Meine o. g. Anmerkungen zu den einzelnen Seiten im PDF beziehen sich also auf die Seiten, die man erhält, wenn man den Blog-Text ausdruckt.
Auf Dein erstelltes PDF mit der Kurzdokumentation „für Dummies“ beziehe ich mich in keinem meiner Blog-Einträge. – Bis jetzt!: Vielleicht hast Du ja noch die Muße in der Kurzdokumentation den Fehler auf der Seite 2 zu eliminieren. Dort beziehen sich die Überschriften nämlich nicht auf die Tabelle (z. B. „Pivotspalte: X2“, markiert ist aber x4 usw.).
Das wird nun wohl einer meiner letzten Einträge gewesen sein, weswegen ich Dir für Dein Studium alles Beste im Weiteren wünsche. Ich selbst habe mich für ein anderes Fernstudium entschieden und bin erstaunt, dass ich hier als Gast überhaupt mitdiskutieren kann.
Vielen, vielen Dank für Deine Anmerkungen und Anregungen.
Simon
… hab‘ mich jetzt doch noch einmal mit dem obigen Thema beschäftigt. Bitte prüfe doch mal, ob die folgenden Dinge (im Blogtext) falsch sind:
i. Seite 4: statt
o ZF: GDB -40X2 + 7X4 =0
müsste es heißen
o ZF: GDB -40X2 – 20X4 =0
(siehe Gleichungsblock vor der Überschrift „Methode des Simplexverfahrens“.)
ii. Seite 13 (Abschnitt „3. Umformung“, Text unterhalb einer Tabelle): „Da die Zeilen X2 und s5 in der Pivotspalte bereits den Wert 0 haben, müssen sie nicht umgeformt werden.“
Das stimmt doch nicht: Die Werte lauten für X2 0,4375 und für s5 1,25. Nichts desto trotz ist der Rest aber korrekt.
iii. In der folgenden Tabelle steht dann in der Zeile GDB (bzw. in der ZF) und der Spalte s1 eine 1,7219. Aber das müsste doch 8,2775 lauten, oder?
Die komplette Aufgabe habe ich indes nun auch durchgerechnet und komme wie Du auf’s gleiche Ergebnis.
Simon
Hey Simon,
danke nochmal für die Klarstellung! Ich hab mich schon gewundert…
Ich habe das PDF eben auch nochmal angepasst, sodass es jetzt stimmen sollte. Im Macken im Artikel sind ebenfalls ausgebügelt. Bis auf den letzten Punkt war alles korrekt. Im Endtableau ist der Wert in der Zeile ZF und Spalte s1 0,172185…, weil du rechnest: (+7,5 x -0,4370386) + 5 = 1,72185. Bei „0,4370386“ ist ein Minus davor, wenn es Plus wäre, kämen wir auf 8,2777894.
Aber vielen Dank für den Hinweise!
Ich freu mich auch immer über Kommentare und Besuche von anderen Fernstudenten. Schließlich besuchen wir zwar andere Fernhochschulen, ziehen aber letztendlich doch an einem Strang und kennen die Probleme und Vorzüge des Fernstudierens ;).
Du bist hier immer gern gesehen (bzw. gelesen!).
Also hoffentlich bis bald, würd mich freuen.
Viele Grüße,
Alicia
Hey Alicia,
jetzt bin ich doch wieder am Verzweifeln. Ich dachte nun, ich hätte mit Deiner Anleitung eine Möglichkeit, nach dem Simplexverfahren jegliche „ungleiche Nuss“ zu knacken. Nun muss ich aber doch feststellen, dass ich nicht immer zu einer Lösung komme.
Kannst Du mir mal einen Gefallen tun und schauen, ob Du Folgendes gelöst bekommst?
Zielfunktion (ZF):
f(x) = x1 + x2 + 3 x3 => max
Nebenbedingungen (NB):
I: x1 + x2 ≤ 18
II: 2 x1 + x2 ≤ 26
III: x1 + x2 + x3 ≤ 12
Des Weiteren habe ich noch einen weiteren Lösungsalgorithmus im Internet gefunden. Unter „http://www.antigauss.de/numerik/simplex.pdf“ ist eine Beschreibung dargestellt, die grundsätzlich ganz gut ist. Allerdings gibt es eine Sache, die ich dabei nicht verstehe. In der Anleitung ist die „Rechte Seite“ ganz links in der zweiten Spalte dargestellt.
Auf der Seite 3 unten im PDF wird dann der Basistausch vorgenommen und die Werte der „rechten Seite“ ebenso verändert. Die Beschreibung erklärt alle Schritte soweit ganz gut, aber warum die alte rechte Seite 0, 18, 26, 12 und die neue 12, 6, 2, 12 heißt, ist mir vollkommen unverständlich. Ich habe den Autor schon angeschrieben, aber nur einen Zustellungsfehler erhalten; vermutlich gibt es die eMail-Adresse nicht mehr.
Hast Du ggf. mit Deinen nun schon recht tief gehenden Kenntnissen eine Idee, nach welcher Gesetzmäßigkeit die „rechte Seite“ in der anderen Beschreibung verändert wird?
Vielen Dank!
Simon
Hey Simon,
ich habe mir das Gleichungssystem eben mal angeschaut und versucht es umzuformen. Hier meine Ergebnisse: https://www.fernstudium-wiwi.de/wp-content/uploads/2011/02/Simplexverfahren-Beispiel.pdf.
Vielleicht bist du ja auf das selbe Ergebnis gekommen ;). Ich habe mir das andere PDF auch eben angeschaut und es ist schon etwas wirr erklärt. Dass die Spalte „RS“ (rechte Seite) dort links in der zweiten Spalte steht ist einfach Geschmackssache. Die einen setzen sie links, die anderen rechts. Da muss man sich einfach etwas umgewöhnen, ist aber ansonsten ok.
Die Zahlenreihe 0, 18, 26, 12 ist ja die Spalte „RS“ aus dem Ausgangstableau. Wie und warum er dann auf 12, 6, 2, 12 kommt, kann ich nicht sagen. Man hätte den ganzen Vorgang auch abkürzen können, schließlich muss nur ein Mal umgeformt werden. Er hat dort noch irgendwelche Zwischenschritte eingebaut, die ich auch nicht so ganz nachvollziehen kann….
Ich hätte es einfach viel kürzer gerechnet. Aber vielleicht komm´ich ja noch auf seinen Zwischenschritt, dann poste ich den gerne nochmal!
Viele Grüße,
Alicia
Hi Alicia,
vielen Dank für Deine Mühen!
Da auch Du das Verfahren nach „Antigauss“ nicht nachvollziehen kannst, gebe ich dieses nun auf. Ich dachte erst, dass es an mir liegt …
Danke auch für die oben stehende Aufgabe, die Du durchgerechnet hast. Ich habe zwar die gleiche „Lösung“, d.h. mein Tableau sieht identisch aus, ABER welche Werte haben denn x1 und x2?
x3 lese ich aus dem Tableau mit 12 ab. Das Maximum von 36 errechnet sich nur, wenn x1 = x2 = 0 ist wie folgt:
f(x) = x1 + x2 + 3 x3 = 36 = 0 + 0 + 3 * 12
Aber woher weiß ich (aus dem Tableau), dass x1 und x2 den Wert Null haben?
Irgend eine Idee?
Simon
Hi Simon,
gerne ;).
Genau, x3 ist 12. Und x1 + x2 sind, wie du schon richtig sagst Null. Das siehst du daran, dass weder x1, noch x2 in der Basis sind. Dort befindet sich (nach der 1. Umformung) nur x3, sodass x1 und x2 der Wert Null zugewiesen wird.
Die Werte für s1 und s2, also 18 und 16 bedeuten, dass für diese Schlupfvariablen noch freie Kapazitäten zur Verfügung stehen.
Viele Grüße,
Alicia
Suuuper! – Vielen Dank.
Wenn ich könnte, würde ich Dir am Feierabend ein großes, kühles Bier ausgeben!
Vermutlich war das jetzt mein letzter Blogeintrag in diesem Forum. Vielleicht gibt es ja in der nahen Zukunft weitere Probleme, die wir gemeinsam lösen könnten? Daher die Frage: Kann man hier in diesem Forum zu allen möglichen Themen (also z.B. auch zur Buchführung o.ä.) Fragen einstellen oder gibt es andere Rubriken?
Die Internetadresse heißt ja „https://www.fernstudium-wiwi.de/simplextableau-umformung-fuer-dummies“ und ich gehe einmal davon aus, dass Studenten der FernUni Hagen – so wie Du – basierend auf „https://www.fernstudium-wiwi.de“ weitere Seiten einrichten können??!
Für mich als Gast und Außenstehender stellt sich die Frage, ob weitere Blogeinträge auf „https://www.fernstudium-wiwi.de/simplextableau-umformung-fuer-dummies“ in der Zukunft überhaupt gesehen und gelesen werden oder ob diese Site nun mit den darin vorhandenen Inhalten im Netz „verwaist“.
Gibt es weitere Anlaufstellen per Blog auf „https://www.fernstudium-wiwi.de“ zu anderen Themen aus der Welt der BWL oder kann man beliebige Fragen zu anderen Themen auch hier hinein posten?
Ist denn eigentlich auch meine vollständige eMail-Adresse für Dich sichtbar? – Ich sehe hier im Blog nur Nicknames.
Simon
Hey Simon,
die Einladung mit dem kühlen Bier nehme ich (wenn auch leider nur auf Distanz) gerne imaginär an ;).
Ich glaube, dass war auch die längste Diskussion, die ich je in einem Artikel hatte! Aber ich freue mich über solche Beiträge, weil sie allen Beteiligten helfen und eventuelle Fragen aufklären.
Leider besteht zurzeit nur die Möglichkeit, einen bestimmten Blogartikel zu kommentieren, so wie diesen hier zum Beispiel. Neue Themen als Gast anzulegen ist daher (noch) nicht möglich.
Aber du hast mich damit auf eine Idee gebracht. Ich schaue mal, ob ich auf meinen Blog ein Forum integriert bekomme, wo sich jeder anmelden und Fragen + Antworten posten kann.
Das wäre echt noch eine super Ergänzung.
Mal schauen, was sich machen lässt & Danke für den Tipp ;)!
Viele Grüße,
Alicia
@Alicia
@Simon
@Jasi
@Sven
Der Lösungsweg müsste auch in den Kurs Grundlagen der Mathe und Statistik behandelt werden? (Denke ich mir halt so als Dipl.-studierender)
Wenn nicht, kann ich hier mal Mathematik für BWL-Bachelor (Kap 19. ab Seite 293 ff) oder auch Mathematik für BWL-Master (Kap 6 . ab Seite 115ff) zum Durchlesen empfehlen. (Verlag Vieweg & Teubner)
Allgemein sollte man sich den Besuch einer Uni-bibliothek (BWL-Fachbereich) auch mal gönnen. Dort sind oft sehr gute Lehrbücher die einen weiterhelfen.
Für die Prüfungsvorbereitung ist es dort auch nicht schlecht im Lesesaal!
Weil keine Ablehnkung halt vorhanden ist.
Hallo Alicia,
Besten Dank für die Erläuterung. Mein Professor hat das, was du mir in 2 Minuten erklären konntest in vielen Stunden nicht geschaft.
Am Besten wäre es, wenn ein „Nicht-Mathematiker“ ein Mathematikbuch schreiben würde, dann wäre es auch für „normale“ Menschen verständlich!
Gruß
B
Hey,
freut mich, dass dir Artikel geholfen hat! Ich habe das Simplex-Verfahren aus den Studienheften auchnicht verstanden. Es hat zwar mehrere Stunden, bzw. Tage gedauert, bis die Erleuchtung kam, aber schneller wäre mir damals auch lieber gewesen ;).
Viele Grüße,
Alicia
Hi Alicia,
man, das hätte ich mal vor ein paar Wochen finden müssen. Naja, jetzt ist es zu spät. Habs zwar nur überflogen, aber super Zusammenfassung und auch wirklich für Dummies.
Eine kleine Anmerkung (evtl. habe ich es auch nur übersehen): So ein tolles Tutorial sollte auf jeden Fall auch komplett sein. Deshalb wäre es super, wenn du noch die Fälle mit aufnehmen könntest, falls Nebenbedingungen
1.) >= positive Zahl
2.) <= negative Zahl 3.) = 0 und falls nicht für alle Variablen gilt,dass diese >= 0 sein müssen.
Grüße
Ein FuH Informatik Student 😉
Hey Stefan,
vielen Dank für deinen Kommentar und die Ergänzungen!
In diesem Beispiel müssen alle Nebenbedingungen die Nichtnegativitätsbedingung erfüllen und die Zielfunktion maximieren. Auf die von dir genannten möglichen Probleme, bin ich hier daher noch nicht eingegangen werde, werde sie aber der Vollständigkeit halber gerne ergänzen!
Vielen Dank für den Tipp!
Grüße aus Hamburg,
Alicia
Habe den Tipp von Stefan (vom 19.07.) soeben unterhalb des Artikels als Nachtrag ergänzt und dort vier mögliche Fälle geschildert, die erst transformiert werden müssen, um sie in Standardform zu bringen.
Danke nochmal an Stefan für den Tipp!
Liebe Alicia,
vielen Dank für dieses epische Werk! Es hat mir kurz vor unserer Klausur sehr geholfen und mir viel Zeit erspart.
Somit kann ich deinen Beitrag nicht nur WiWi, sondern auch Informatik studenten empfehlen, die (hoffentlich) ihre Klausur mit dem Beherrschen des Algos überstehen können, ohne dabei alle mathematischen Hintergründe kennen zu müssen 😉
Alles Gute!
Hey LH,
vielen Dank für deinen Kommentar ;). Der hat mich echt gefreut!
Das motiviert doch gleich zu neuen Artikeln zu Wirtschaftsmathe ;).
Ich wünsche dir auch alles Gute bei deinem Studium!
Viele Grüße,
Alicia
Hallo Alicia,
vielen Dank für die tolle Erläuterung. Aber das Thema raubt mir immer noch den letzten Nerv ;-). Ich weiss nicht, wie ich in den folgenden Fällen vorgehen bzw. beachten muss:
1. Zielfunktion soll minimiert statt maximiert werden
2. Es gibt Variablen ohne Nichtnegativitätsbedingung
3. Es gibt Nebenbedingungen, die eine Gleichung sind
4. Es gibt Nebenbedingungen, die eine Ungleichung sind, die aber „≥“ statt „≤“ fordern
Kannst Du hierzu auch Beispiele liefern? Vor allem zu Punkt 1.
Das wäre super…..
Danke im Voraus.
Hey Kemal,
vielen Dank für deinen Kommentar und dafür, dass du dich durch den Artikel gekämpft hast. Ich habe dir hier mal zu jedem Optimierungsproblem ein kleines Beispiel aufgeschrieben:
Problem 1: Zielfunktion soll minimiert statt maximiert werden
Lösung: Alle Koeffizienten der Zielfunktion negieren.
Beispiel: Aus ZF: GDB -40X2 – 20X4 = 0 wird ZF: GDB + 40X2 + 20X4 = 0
Problem 2: Es gibt Variablen ohne Nichtnegativitätsbedingung
Lösung: Variable xi in zwei neue Variablen xi‘, xi” ≥ 0 aufspalten. Anschließend alle xi durch xi‘- xi” ersetzen.
Beispiel: Wäre bei der Variable s3 die Nichtnegativitätsbedingung nicht erfüllt (also s3 < 0), würde man alle s3 durch den Ausdruck s3‘-s3” ersetzen. Zusätzlich wird die neue Nichtnegativitätsbedingung s3i‘, s3” ≥ 0 zum LP hinzugefügt. Problem 3: Es gibt Nebenbedingungen, die eine Gleichung sind Lösung: Aus der Gleichung zwei Ungleichungen machen. Beispiel: Wäre die Nebenbedingung 7X2 + 10 X4 <= 1600 eine Gleichung, also 7X2 + 10 X4 = 1600, so müsste man die Gleichung 7X2 + 10 X4 = 1600 durch 7X2 + 10 X4 < 1600 und 7X2 + 10 X4 > 1600 ersetzen.
Problem 4: Es gibt Nebenbedingungen, die eine Ungleichung sind, die aber „≥“ statt „≤“ fordern
Lösung: Beide Seiten mit (-1) multiplizieren, bzw. einfach die Vorzeichen auf beiden Seiten ändern.
Beispiel: Aus der Nebenbedingung 8X2 + 2X4 >= 500 würde dann durch Vorzeichenwechsel -8X2 – 2X4 <= - 500 werden. Die "Problemfälle" kommen recht selten vor, da sich meistens alle Funktionen in der Normalform befinden, aber es ist trotzdem gut, im Fall der Fälle einigermaßen Bescheid zu wissen. Ich hoffe, dass dir die zusätzlichen Erläuterungen etwas weiterhelfen! Viele Grüße, Alicia
Hey Alicia,
Vielen Dank für die schnelle Antwort. Ich will nicht nerven, aber eine Frage habe ich noch 😉 Zu Problem 1: Wenn ich im Falle der Minimierung die Zielfunktion negiert habe, gehe ich dann rechentechnisch so vor wie bei der Maximierung? Oder sind hierbei weitere Regeln bei den Umformungen zu beachten? Hierfür waere eine Aufgabe mit einer Loesung sehr hilfreich.
Wenn ich mal wieder in HH bin, gebe ich einen aus 😉
Danke im Voraus.
Hey Kemal,
ja, soweit ich weiß reicht es aus, die Koeffizienten der Zielfunktion zu negieren, die Nebenbedingungen nicht.
Denn wenn du etwas minimieren möchtest, ist das ja das Gleiche, als würdest du das Negative maximieren.
Ich weiß, das ist echt komplex und ich hatte bisher auch nicht den Fall, das ich das anwenden musste. Aber ich habe in einem Buch (Lineare Optimierung: Ein Rezeptbuch
) noch ein kleines Beispiel gefunden. Unter http://goo.gl/P6nKI kannst du dir das in der Preview ja mal anschauen (Seite 76).
Sorry, dass ich kein komplettes Beispiel liefern kann, aber vielleicht hilft dir der Link ja etwas weiter!
Viele Grüße,
Alicia
Hey Alicia,
danke für diese tolle Erklärung, ich hatte es mit dem Simplex-Verfahren schon mal in der Höheren Handelsschule zu tun, das ist aber schon 20 Jahre her, ich dachte im ersten Moment als ich das Thema im Lehrbrief kam, „das hattest du doch schon mal“ und ich wusste auch noch das ich das damals konnte umso größer war die Ernüchterung als ich nach dem durchlesen erstmal nur Bahnhof verstanden hatte. Dank deiner Erklärung hab ich es jetzt wieder kapiert. :o)
Dankbare Grüße
Kinnert
Hey Kinnert!
Vielen Dank für das nette Kompliment ;)!
Freut mich total, wenn ich dir mit dem Artikel weiterhelfen konnte. Dann hat sich die Arbeit definitiv gelohnt!
Viel Erfolg bei deinem Studium & Grüße aus Hamburg,
Alicia
Hi,
klasse Erklärung!
Im PDF ist allerdings ein Fehler: Auf Seite 2 in der Erklärung zu „Pivotzeile: s3“ muss es „x4“ statt „x2“ heißen.
Gruß,
Roegel
Hey Roegel,
vielen Dank für den Hinweis, ist bereits berichtigt ;)!
Grüße,
Alicia
Jetzt muss ich mir schon von einem Mädl erklären lassen, wie ein Simplex funktioniert……;-)
Spaß beiseite, das hat echt super geholfen, mein Prof von der „achso elitären Münchner Elite Uni“ hat nicht mal im Ansatz das so eindeutig erklären können wie du es hier gemacht hast.
Also, auch in München wartet ein imaginäres Bier (oder doch Glühwein?) auf dich.
Besten Dank nochmals!
Hallo Gerhard!
Vielen Dank für deinen Kommentar, da hat sich die Mühe für den Artikel auf jeden Fall gelohnt 🙂
Schade, dass ich am anderen Ende Deutschlands wohne, aber bei meinem ersten Glühwein auf dem Weihnachtsmarkt denke ich an dich!
Liebe Grüße,
Alicia
Vielen, vielen Dank!!!
Wesentlich besser verständlich als in diesem bescheuerten Kursheft!!
Hallo,
ich vermisse die optimalen Werte für x2 und x4 in dem Endtableau oder ist das Endtableau gar nicht das Endtableau?
Gruß
Simple
Hey,
die optimale Lösung liege bei X4 = 147,0199 und X2 = 18,54305. Der Deckungsbeitrag ist bei 3682,12 Euro maximal.
Viele Grüße,
Alicia
Hallo,
als Erstes :Danke fuer diese Ausarbeitung!
Mein einziges Problem beim Simplex dass ich die Werte fuer x2 und x4 nicht auslesen bzw nicht nachvollziehen kann. Ich habe IMMER „NUR“ da das Problem. Perfektes Simplex Verfahren, kille alles was negativ ist in der Zielfunktionszeile dann das ablesen…. In manchen kann man es direkt ablesen aber in vielen wie z. B in diesem Bsp auch nicht.
Irgendwelche Tipps?
Lg Amin
Hi Amin,
vielen Dank für deinen Kommentar! Leider kann ich dir bzgl. des direkten Ablesens von X2 und X4 derzeit keinen Tipp geben, da ich mich erstmal wieder in das Thema einarbeiten müsste – ist schon etwas länger her :).
LG,
Alicia
Hallo,
Danke für die Ausarbeitung, das hat mir sehr geholfen. Wie komme ich denn auf X2 und X4 am Ende? Also wie rechne ich die aus?
Viele Grüße
Hallo Johanna,
die Rechenwege findest du ein paar Zeilen weiter oben.
Für Zeile X4 (mit +1,25):
…
Feld X4/RS= (1,25 x 57,61589) + 75 =147,0199
Für Zeile X2 (mit -0,4375):
…
Feld X2/RS= (-0,4375 x 57,61589) + 43,75 =18,453
Viele Grüße,
Alicia