Maximierungsaufgabe Nebenbedingung

13.06.2012, 17:46

Nini2012

Maximierungsaufgabe Nebenbedingung

Meine Frage:
Liebe Mathe-Gemeinde,

ich sitze vor einer Aufgabe, die ich nun schon drei mal gerechnet habe. Immer kommt ein anderes Ergebnis raus, aber nicht das richtige! Vielleicht weiß ja von Euch jemand Rat?!

Zur Herstellung von drei Produkten werden zwei Maschinen eingesetzt. Die benötigen Maschinenzeiten in ZE pro Einheit des jeweiligen Prodktes, die maximal zur Verfügung stehenden Kapazitäten in ZE pro Woche und die Deckungsbeiträge in GE sind der nachstehenden Tabelle zu entnehmen (pdf).
Von Produkt 3 müssen doppelt so viele Einheiten produziert werden wie von Produkt 1 und von Produkt 2 sind mindestens 50 Einheiten zu produzieren.
Bestimmen Sie mit Hilfe des Zwei-Phasen-Modells den optimalen Produktionsplan zur Maximierung des Deckungsbeitrages.

Meine Ideen:
Ich kann mir gut vorstellen, dass sich mein Fehler bereits beim Aufstellen der Nebenbedingungen eingeschlichen hat. Das mathematische Modell hab ich folgendermaßen definiert:

Max. $\begin{eqnarray*} D= 5x1+ 2x2+ 8x3 \end{eqnarray*}$

NB: $\begin{eqnarray*} x1+ 2x2+ 2x2\leq 1200 \end{eqnarray*}$
$\begin{eqnarray*} 2x1+ x2+ 4x3\leq 2100 \end{eqnarray*}$
$\begin{eqnarray*} x3= 2x1 \end{eqnarray*}$
$\begin{eqnarray*} x2\geq 50 \end{eqnarray*}$

Die dritte Nebenbedingung habe ich umgeformt in $\begin{eqnarray*} - 2x1+ x3= 0 \end{eqnarray*}$ . Kann mir bis hierhin jemand sagen, ab das richtig ist?

13.06.2012, 18:05

Kasen75

Auf diesen Beitrag antworten »

Hallo,

dein Gleichungssystem sieht gut aus. Wie sieht den Simplex-Tableau aus?

Mit freundlichen Grüßen.

14.06.2012, 01:24

Nini2012

Auf diesen Beitrag antworten »

Anbei meine Simplex "Lösung" ... der letzte Absatz ist definitiv falsch. Der Fehler liegt wahrscheinlich im vorletzten Kasten - die grün unterlegte Lösung ist der optimalen Lösung ähnlich. Wo könnte der Fehler sein?

Die Pivotspalte richtet sich m.E. nach dem betragsgrößten negativen Koeffizienten der Zielfunktion, die Pivotspalte jeweils nach dem kleinsten Wert aus Pivotspalte und Ergebnis. Wobei hier keine negativen Werte berücksichtigt werden - im zweiten Block macht es aber wieder Sinn, da sich dort das Minus aufhebt. Ansonsten bin ich mit meinem Latein am Ende.

14.06.2012, 01:28

Nini2012

Auf diesen Beitrag antworten »

Anhang vergessen

14.06.2012, 01:28

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich glaube du hast vergessen das Simplex-Tableau anzuhängen.

Mit freundlichen Grüßen.

Edit: Doch nicht. Big Laugh

14.06.2012, 06:17

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich es gestern noch durchgerechnet. Du hast meiner Meinung das erste Pivotelement nicht regelgerecht ausgesucht.

Kriterium ist bei der Zeilenauswahl:

$\begin{eqnarray*} min\left\{ \frac{b_i}{b_{is}} \vert \ ai \geq 0 \right\} \end{eqnarray*}$

Somit kann $\begin{eqnarray*} b_{is} \end{eqnarray*}$ durchaus Null sein.

Somit wäre das erste Pivotelement $\begin{eqnarray*} (y_{H1}/x_3)=1. \end{eqnarray*}$

Sonst hast du aber ganz gut gerechnet. Mir ist nur aufgefallen, dass im zweiten Tableau bei $\begin{eqnarray*} (y_{H1}/y_2) \end{eqnarray*}$ 0,75 steht. Ich glaube es müsste -0,25 sein. Flüchtigkeitsfehler sind bekommt man beim Simplex-Algorithmus gratis mitgeliefert.

Ich werde im Laufe des Tages meine Version hier reinstellen.

Mit freundlichen Grüßen.

14.06.2012, 13:11

Nini2012

Auf diesen Beitrag antworten »

Bin gespannt auf Deine Lösung!

14.06.2012, 23:21

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich habe mich erst bei der Pivotauswahl an der Hilfszielfunktion orientiert. Im dritten Tableau konnte ich dann die 2 künstilichen Variablen streichen. Jetzt brauchst du nur noch ein eine Iteration und schon bist du bei der (hoffentlich) optimalen Lösung. Die y ohne * sind Schlupfvariablen.

Mit freundlichen Grüßen.

14.06.2012, 23:39

Nini2012

Auf diesen Beitrag antworten »

Ok - wenn ich nun ausgehend von Deiner Rechnung die zweite Phase berechne, dann komme ich auf das richtige Ergebnis.
Allerdings bin ich nun total verwirrt, wie man das Pivotelement aussucht. Ich dachte immer man muss sich an der Zeile der Zielfunktion orientieren r- de betragsgrößte negative Wert zeitg einem die Pivotspalte, dann durch Dividieren der einzelnen Ergebnisse durch die entsprechenden Werte der Pivotspalte in der Zeile herausfinden, für welchen Wert das am kleinsten wird.

Du hast Dich nun an den positiven Werten in der Hilfszielfunktion orientiert. Kann man sich das einfach aussuchen oder gibt es dafür Regeln?

Bei den anderen Übungsaufgaben bin ich auch auf Minimierungsaufgaben gestoßen. Wenn ich die Zielfunktion mit -1 multipliziere und dann ausgehend davon das Problem maximiere, sind ja häufig keine negativen Werte in der Zielfunktion im Tableau gegeben. Scheinbar wird sich dort an dem höchsten positiven Wert der Zielfunktion oder dem betragsgrößten negativen Wert der Hilfszielfunktion orientiert.

Wann muss ich denn nun welche negativen oder positiven Werte der Ziel- oder Hilfszielfunktion auswählen? geschockt

15.06.2012, 00:05

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Nini2012
Du hast Dich nun an den positiven Werten in der Hilfszielfunktion orientiert. Kann man sich das einfach aussuchen oder gibt es dafür Regeln?

Nur als kurzer Einwurf gedacht:

Du musst prinzipiell mit der Hilfszielfunktion anfangen (das hattest du in deiner Lösung offenbar falsch!) und wenn du sie minimieren willst, musst du dich an den größten positiven Werten orientieren (wie Kasen!), wenn du die negative Hilfszielfunktion (also alle Vorzeichen umgedreht) maximieren willst an den betragsgrößten negativen Werten...

15.06.2012, 02:02

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich kann Mystic im Prinzip nichts hinzufügen. Wenn du $\begin{eqnarray*} (-w) \end{eqnarray*}$ (negative Zielhilfsfunktion bzw. negative zweite Zielfunktion) maximierst,
dann musst du dich an den kleinsten (negativen) Werten orientieren.

In deinem Beispiel hatten wir $\begin{eqnarray*} +w \end{eqnarray*}$ . Also musst du dich an den größten positiven Zahlenwerten orientieren. Also $\begin{eqnarray*} Min \ w \end{eqnarray*}$ .

Das gilt immer, unabhängig davon, ob du als Aufgabenstellung ein Maximierungs- oder Minimierungsproblem hast.

In deinem Beispiel waren die beiden Nebenbedingungen mit den künstlichen Variablen:

$\begin{eqnarray*} -2x_1+x_3+y_4^*=0 \end{eqnarray*}$
$\begin{eqnarray*} x_2-y_3+y_5^*=50 \end{eqnarray*}$

$\begin{eqnarray*} y_4^*=2x_1-x_3 \end{eqnarray*}$
$\begin{eqnarray*} y_5^*=50-x_2+y_3 \end{eqnarray*}$
$\begin{eqnarray*} w=y_4^*+y_5^*=50+2x_1-x_2-x_3+y_3 \end{eqnarray*}$

Trägt man das in das Simplextableau ein, sieht das dann so aus:
$\begin{eqnarray*} w-2x_1+\textcolor{red}{1}x_2+\textcolor{red}{1}x_3-y_3=50 \end{eqnarray*}$

Und da man w minimiert (siehe oben) orientiert man sich an den roten (positiven) Ziffern.

Ich weiß, dass es kompliziert ist. Aber das ist es für jeden.

Weitere Fragen sind willkommen.

Mit freundlichen Grüßen.

15.06.2012, 09:59

Nini2012

Auf diesen Beitrag antworten »

Zusammengefasst:

Zielhilfsfunktion negativ: Pivotspalte ist diejenige mit dem kleinsten negativen Wert (also der betragsgrößte negative Wert)

Zielhilfsfunktion positiv: Pivotspalte ist diejenige mit dem größten positiven Wert

Beides unabhängig davon, ob es sich um ein Max. oder Min. Problem handelt?

15.06.2012, 14:08

Kasen75

Auf diesen Beitrag antworten »

Genau.

Mit freundlichen Grüßen.

16.06.2012, 15:44

Nini2012

Auf diesen Beitrag antworten »

Super - vielen Dank für die Hilfe!

16.06.2012, 16:19

Kasen75

Auf diesen Beitrag antworten »

Freut mich, dass alles klar ist. smile