Optimales Minimum mit Hilfe des Simplexverfahrens

19.06.2012, 12:52

BWL 1990

Optimales Minimum mit Hilfe des Simplexverfahrens

Meine Frage:
Hallo,

ich habe ein paar Fragen zum Simplexverfahren, da ich mit den Anwendungsregeln nicht ganz vertraut bin.

Folgende Aufgabenstellung habe ich gegeben:

minimiere ZF= 2x1-x2
unter den Nebenbedingungen:
NB1= 10? x1+x2
NB2= 5? x1+x2
NB3= 2? -x1+x2 mit x1, x2 ? 0

Meine Ideen:
Ich bin jetzt folgendermaßen vorgegangen:

1. Die Nebenbedingungen passend umstellen und mit Schlupfvariablen erweitern:

NB1= x1+x2+u1?10
NB2= -x1-x2+u2?-5
NB3= -x1+x2+u3?2

min ZF= 2x1-x2 --> max ZF=(-ZF)= -2x1+x2

Eingesetzt sieht das dann folgendermaßen aus:

x1 x2 u1 u2 u3 b
u1 1 1 0 0 0 10
u2 -1-1 0 1 0 -5
u3 -1 1 0 0 1 2
(-ZF) -2 1 0 0 0 0

Meine Frage ist: wie beginne ich jetzt?
Also ich weiß dass ich in der Zielfunktion keinen negativen Wert mehr haben darf, daher würde ich die Spalte mit (-2) nehmen und in dieser Spalte mein Pivotelement wählen. Mich irritieren jetzt allerdings die (-5) in der zweiten Zeile. Darf da -5 stehen oder muss auch hier schauen dass diese Zahl positiv wird?
Und wenn ja, was muss ich dann zuerst betrachten, die -2 oder die -5?

Zusätzliche Frage: Müssen alle Werte in der ZF am Ende positiv sein, also auch die Werte für u1 u2 etc.?

Danke schon mal für eure Hilfe!

19.06.2012, 17:02

Kasen75

Auf diesen Beitrag antworten »

Hallo,

durch die Fragezeichen kann man die (Un-)Gleichungen nicht erkennen.
So ist es schwierig eine adäqute Anwort auf deine Fragestellung zu geben.
Auf jeden Fall würde ich die mich an der 1 in der Zielfunktion orientieren, da es sich um ein Minimierungsproblem handelt.

Mit freundlichen Grüßen.

19.06.2012, 18:32

BWL 1990

Auf diesen Beitrag antworten »

Oh mist, das habe ich jetzt erst gesehen.

Hier der verbesserte Teil:

Folgende Aufgabenstellung habe ich gegeben:

minimiere ZF= 2x1-x2
unter den Nebenbedingungen:
NB1= 10>= x1+x2
NB2= 5<= x1+x2
NB3= 2>= -x1+x2 mit x1, x2 ? 0

Meine Ideen:
Ich bin jetzt folgendermaßen vorgegangen:

1. Die Nebenbedingungen passend umstellen und mit Schlupfvariablen erweitern:

NB1= x1+x2+u1<=10
NB2= -x1-x2+u2<=-5
NB3= -x1+x2+u3<=2

min ZF= 2x1-x2 --> max ZF=(-ZF)= -2x1+x2

Wir haben in den Vorlesungen nur eine Minimierungsaufgabe durchgenommen, daher kenn ich mich da nicht so gut aus.
Wir haben dann die ZF einfach maximiert und am Ende die Vorzeichen wieder getauscht. So wie ich es in meinem Schritt oben getan habe.

Ich verstehe jetzt nicht wieso du mit der 1 anfangen würdest. Es soll doch kein negatives Vorzeichen mehr in der ZF stehen und die 1 ist ja schon positiv.
Was ist eigentlich mit den -5 in der zweiten Zeile, darf der Wert negativ sein?

20.06.2012, 06:17

Kasen75

Auf diesen Beitrag antworten »

Hallo,

beim Simplexalgorithmus (SA) sollte die RS nur positive Werte enthalten. Da ist deine Anmerkung berechtigt. Deswegen würde ich bei NB2 die Schlupfvariable einfach negativ wählen um ein = Zeichen zu erreichen. Um noch eine Basisvariable in der NB 2 zu bekommen würde ich noch eine künsliche Variable ( $\begin{eqnarray*} U4^{\ast} \end{eqnarray*}$ ) einführen:

NB1= $\begin{eqnarray*} x1+x2+u1=10 \end{eqnarray*}$
NB2= $\begin{eqnarray*} x1+x2-u2+U4^{\ast}=5 \end{eqnarray*}$
NB3= $\begin{eqnarray*} -x1+x2+u3=2 \end{eqnarray*}$

Wegen den Schlupfvariablen ein Gleichheitszeichen.

$\begin{eqnarray*} min ZF= 2x1-x2 \end{eqnarray*}$
Umformung:
min ZF -2x1+x2=0 So stünde das Min-Problem auch im Tableau.
Jetzt in ein Max-Problem um gewandelt:
$\begin{eqnarray*} max -ZF +2x1-x2=0 \end{eqnarray*}$

Beim Maximieren soll kein negatives Vorzeichen mehr stehen. Auch da würde ich Dir Recht geben. Nur, wenn du deine $\begin{eqnarray*} -ZF \end{eqnarray*}$ ins Tableau einträgst (wie oben gezeigt), dann hat der Ausdruck $\begin{eqnarray*} -x2 \end{eqnarray*}$ ein negatives Vorzeichen.

Mit freundlichen Grüßen

20.06.2012, 17:06

BWL 1990

Auf diesen Beitrag antworten »

Also ich habe die Aufgabe jetzt nochmal durchgerechnet.

Die Aufgabenstellung:

Minimiere die ZF = 2x1-x2

unter den Nebenbedingungen:
NB1= 10>= x1+x2
NB2= 5<= x1+x2
NB3= 2>= -x1+x2 mit x1, x2 >= 0

Meine Rechnung:

Ich habe die Nebenbedingungen jetzt folgendermaßen umgestellt:

NB1= x1+x2+u1<=10
NB2= x1+x2-u2<=5 (Das mit U4 kenn ich nicht)
NB3= -x1+x2+u3<=2

Bei der Zielfunktion behandle ich wie beim maximieren:

ZF= -2x1+x2

Das ganze jetzt eingesetzt sieht das folgendermaßen aus:

$\begin{eqnarray*} \begin{vmatrix} - & x_1 & x_2 & u_1 & u_2 & u_3 & b \\ u_1 & 1 & 1 & 1 & 0 & 0 & 10 \\ u_2 & 1 & 1 & 0 & -1 & 0 & 5 \\ u_3 & -1 & 1 & 0 & 0 & 1 & 2 \\ (-ZF) & -2 & 1 & 0 & 0 & 0 & 0 \end{vmatrix} \end{eqnarray*}$

Ich wähle als Spalte x1 wegen (-2) und als Pivotelement die 1 in Zeile u2

$\begin{eqnarray*} \begin{vmatrix} - & u_2 & x_2 & u_1 & u_2 & u_3 & b \\ u_1 & 0 & 0 & 1 & 1 & 0 & 5 \\ x_1 & 1 & 1 & 0 & -1 & 0 & 5 \\ u_3 & 0 & 2 & 0 & -1 & 1 & 7 \\ (-ZF) & 0 & 3 & 0 & -2 & 0 & 10 \end{vmatrix} \end{eqnarray*}$

Jetzt nehme ich Spalte u2 wegen (-2) in der ZF und als Pivot die 1 in Zeile u1

Daraus ergibt sich:

$\begin{eqnarray*} \begin{vmatrix} - & u_2 & x_2 & u_1 & u_2 & u_3 & b \\ u_1 & 0 & 0 & 1 & 1 & 0 & 5 \\ x_1 & 1 & 1 & 1 & 0 & 0 & 10 \\ u_3 & 0 & 2 & 1 & 0 & 1 & 12 \\ (-ZF) & 0 & 3 & 2 & 0 & 0 & 20 \end{vmatrix} \end{eqnarray*}$

Da ich davon ausging das meine ZF maximiert werden soll, ändere ich jetzt wieder die Vorzeichen --> max ZF = 20 --> min ZF = -20

Aus dem Tableu kann ich rauslesen das x1 = 10

wenn ich das jetzt in meine ZF= 2x1-x2 setze erhalte ich -20= 2*10-x2 folglich muss x2 = -40 sein.

Ich glaube ehrlich gesagt nicht, dass meine Rechnung richtig war....

Danke für deine Hilfe!

Beste Grüße!

20.06.2012, 17:20

BWL 1990

Auf diesen Beitrag antworten »

ich meine natürlich x2 = 40

20.06.2012, 19:06

Kasen75

Auf diesen Beitrag antworten »

Hallo,

wenn ich deine Lösung ( $\begin{eqnarray*} x_1 \end{eqnarray*}$ =10) in die Zielfunktion einsetze, dann bekomme ich $\begin{eqnarray*} \textcolor{red}{+}20 \end{eqnarray*}$ heraus.

Zitat:

wenn ich das jetzt in meine ZF= 2x1-x2 setze erhalte ich -20

Scheint mir ein bisschen hoch. Ich würde es so machen (wie im letzen Beitrag beschrieben). Wobei ich hier die $\begin{eqnarray*} \large\textrm{ZF minimiere} \end{eqnarray*}$ . Somit ist die Zielfunktion genau wie deine im Tableau.

$\begin{eqnarray*} \begin{vmatrix} - & x_1 & x_2 & u_1 & u_2 & u_3 & u_4^{\ast} & b\\ u_1 & 1 & 1 & 1 & 0 & 0 & 0 &10 \\ u_4 & 1 & 1 & 0 & -1 & 0 & 1 & 5 \\ u_3 & -1 & \textcolor{red}{1} & 0 & 0 & 1 & 0 & 2 \\ (ZF) & -2 & 1 & 0 & 0 & 0 & 0 & 0 \end{vmatrix} \end{eqnarray*}$

Die künstliche Variable kann man im Simplex nicht einfach unter den Tisch fallen lassen.

Nehme jetzt die $\begin{eqnarray*} x_2 \end{eqnarray*}$ als Pivotspalte.
$\begin{eqnarray*} \begin{vmatrix} - & x_1 & u_3 & u_1 & u_2 & u_3 & u_4^{\ast} & b\\ u_1 & 2 & 0 & 1 & 0 & -1 & 0 & 8 \\ u_4 & \textcolor{red}{2} & 0 & 0 & -1 & -1 & 1 & 3 \\ x_2 & -1 & 1 & 0 & 0 & 1 & 0 & 2 \\ (ZF) & 1 & 0 & 0 & 0 & 1 & 0 & 2 \end{vmatrix} \end{eqnarray*}$

Ab hier 2 Sätze editiert.

Da der Zielkoeffizient für $\begin{eqnarray*} x_1 \end{eqnarray*}$ wieder positiv ist und gleichzeitig die künstliche Variable $\begin{eqnarray*} u_4^{\ast} \end{eqnarray*}$ in der Basislösung ist, muss man noch einen Pivotschritt durchführen. Und zwar ist hier $\begin{eqnarray*} u_4^{\ast}=3 \end{eqnarray*}$ . Dies darf aber nicht sein. Um die wegzubekommen bleibt nur die 2 in der Zeile $\begin{eqnarray*} u_4^{\ast} \end{eqnarray*}$ . Die anderen $\begin{eqnarray*} a_{2s} \end{eqnarray*}$ sind negativ. Die Bedigung für die Auswahl der Pivozeile ist ja:
$\begin{eqnarray*} min\left\{ \frac{b_i}{a_{is}} \vert \ ais \geq 0 \right\} \end{eqnarray*}$
$\begin{eqnarray*} \textrm{i ist hier 2.} \end{eqnarray*}$
Wenn du die 2 als Pivotelement nimmst, kommst du auch zu optimalen Ergebnis.

Ich hoffe, du kannst meinen Ausführungen folgen. Bei Fragen, bitte nachfragen.

Mit freundlichen Grüßen.

Neue Frage »

Antworten »

Optimales Minimum mit Hilfe des Simplexverfahrens

Verwandte Themen