 |
 |
 |
 |
 |
 |
Startseite » Forum » Simplex-Verfahren
Simplex-Verfahren
Universität / Fachhochschule
angewandte lineare Algebra
Tags: Optimierung, Simplex Verfahren
 
|
  |
|---|
|
Hallo zusammen, ich habe ein Problem mit der Anwendung des Simplex-Algorithmus: Folgende Aufgabe muss ich berechnen: z(x,y)=9x+2y+31 NNB: x>=0, y>=0 Zusätzliche NB: -x+y 2x+2y 3x+y Ich habe dann die Tabelle so ausgefüllt: ____x___y_S1__S2__S3___RS S1_-1___1__1___0___0____1 S2__2___2__0___1___0___14 S3__3___1__0___0___1___15 Z___9___2__0___0___0__-31 Habe ich die Tabelle richtig aufgestellt? Jetzt weiß ich nicht genau wie ich weiter machen soll. Wie wähle ich die Piwospalte oder das Piwoelement aus? Gruß Simone |
|
 |
|
Hallo, Du hast leider etwas wenig zur Aufgabenstellung geschrieben, deswegen gehe ich davon aus, dass Deine Daten bereits alle in Standardform vorliegen, d.h. die angegebene Zielfunktion soll maximiert werden und die NB liegen in der Form ">=" vor (falls nicht, musst Du diese Standardform erst erzeugen). Das Tableau ist dann von der grundsätzlichen Struktur her so richtig aufgebaut. Normalerweis gilt aber die Konvention, dass alle positiven Koeffizienten der Zielfunktion in der Zielfunktionszeile mit einem negativen Vorzeichen dargestellt werden und umgekehrt. Außerdem sind im Ausgangstableau x und y mit 0 belegt, so dass der Zielfunktionswert 31 beträgt , nicht -31. Die Vorzeichen in der Zielfunktionszeile sollten entsprechend geändert werden. Das weitere Verfahren läuft dann so ab: - Suche den betragsmäßig größten, aber negativen Eintrag in der Zielfunktionszeile ( hier -9). Die Spalte, in der dieser Eintrag steht, ist die Pivotspalte.Begründung: die zugehörige Variable leistet den höchsten Beitrag zum Zielfunktionswert, da ihr Koeffizient in der Zielfunktion positiv und maximal ist. Es ist deshalb zum Maximieren vorteilhaft diese Variable mit einem möglichst hohen Wert zu belegen. - Teile dann alle Elemente der Ergebnisspalte (bei Dir: "RS") durch die entsprechenden Elemente der Pivotspalte. Die Zeile, für die sich der kleinste positive Quotient ergibt,ist die Pivotzeile. Begründung: der kleinste Quotient gibt an, mit welchem Wert die zu erhöhende Variable maximal belegt werden kann( die "strengste" Restriktion). Das Element im Schnittpunkt von Pivotzeile und -spalte heisst Pivotelement. Erzeuge an dieser Stelle eine 1, in dem Du die komplette Pivotzeile durch den Wert des Pivotelementes dividierst. In allen anderen Zeilen, einschließlich der Zielfunktionszeile wird an dieser Stelle eine 0 erzeugt durch Multiplikation der Elemente der Pivotzeile mit einem geeigneten Wert und Aufaddieren auf die jeweilige Zeile. -Danach folgt die nächste Iteration, d.h. es wird in der Zielfunktionszeile wieder der nächste betragsmäßig maximale aber negative Wert gesucht ... Das Verfahren terminiert, wenn es in der Zielfunktionszeile keine negativen Werte mehr gibt. Dann kannst Du die Variablenbelegung ablesen: Mit Werten belegt sind nur solche Variablen in deren Tableauspalte ein Eintrag 1 und alle anderen Einträge 0 sind. Der Wert lässt sich in der Ergebnisspalte ablesen. |
 |
|
Ups, irgendwie hab ich bei der Aufgabenstellung nicht alles richtig aufgeschrieben. Aber du hast vollkommen Recht. Es soll also maximiert werden. Die Nebenbedingungen sollten richtig heißen: -x+y<=1 Engpass 1 2x+2y<=14 Engpass 2 3x+y<=15 Engpass 3 Habe jetzt versucht die ganze Sache mal zu berechnen und bin da noch auf ein paar Probleme gestoßen. Geht es nur darum die Z Zeile (Zielfunktion) bei x und y eine Null hinzubekommen? Wie lese ich jetzt x und y ab? Ich habe ausgerechnet: ____x__y__s1__s2__s3__RS s1_-1__1__1___0___0____1 s2__0__1__0__3/4_-1/2__3 s3__1__0__0_-1/4__1/6__4 z___0__0__0_-3/4__7/2__43 Somit ist bei mir der Zielfunktionswert 43 |
|
|
|
Hallo, zunächst einmal, muss ich mich korrigieren: Die NB müssen natürlich in der Form "<=" vorliegen, so wie das bei Dir auch der Fall ist. Du kannst den Simplex auf Dein gegebenes Modell tatsächlich "gefahrlos" anwenden. Nein, es geht nicht darum, nur in der Zielfunktionszeile in den Spalten für x,y eine 0 zu erzeugen. Du musst nach den beschriebenen Regeln das Pivotelement suchen, an dieser Stelle eine 1 und in allen(!!) anderen Zeilen an der entsprechenden Stelle eine 0 erzeugen. Das Pivotelement in Deinem Tableau ist das Element in der 1.Spalte und 3.Zeile ,dort steht eine 3(die Regeln zur Ermittlung des Pivotelements habe ich Dir ja angegeben). Du erzeugst dort eine 1, indem Du alle Elemente der dritten Zeile durch 3 dividierst. Anschließend musst Du in allen (!) anderen Zeilen, also der 1., 2. und der Zielfunktionszeile in der ersten Spalte eine 0 erzeugen. Das Verfahren ist abgeschlossen, sobald keine negativen Einträge mehr in der Zielfunktionszeile stehen. Dein Endtableau kann nicht stimmen, da noch ein negativer Wert in der Zielfunktionszeile steht, das Verfahren also noch gar nicht abgeschlossen wäre! Ausserdem sind nur Variablen mit Werten belegt, in deren Spalte ein Einheitsvektor steht (ein Eintrag 1, der Rest 0), das ist bei Dir aber für keine Spalte der Fall. Ich habe die Aufgabe auch einmal gerechnet und bei mir war das Verfahren bereits nach einer Iteration abgeschlossen. Wähle das Element im Schnittpunkt von erster Spalte und dritter Zeile als Pivotelement und erzeuge dann für die komplette erste Spalte einen Einheitsvektor. Das Tableau hat dann folgendes Aussehen: x y S1 S2 S3 0 4/3 1 0 1/3 6 0 4/3 0 1 2/3 4 1* 1/3 0 0 1/3 5* ------------------------ 0 1 0 0 3 76 Du siehst, dass in den Spalten x, S1 und S2 jeweils ein Einheitsvektor steht, d.h. nur diese Variablen sind mit Werten belegt. Das Verfahren ist abgeschlossen, da in der Zielfunktionszeile kein negativer Eintrag mehr steht. Die Belegung der beiden Schlupfvariablen S1, S2 ist zweitrangig.In der Spalte der Variablen x steht die 1 in der dritten Zeile(*), d.h. ihr Wert wird in der dritten Zeile der Ergebnisspalte angezeigt und beträgt 5(*). Die Lösung ist also x=5 ; y=0 mit einem optimalen Zielfunktionswert von 76 . |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
501909
501836