Multikriterielle Lineare Optimierung - Simplex Algorithmus

16.05.2011, 12:32	zaccusx	Auf diesen Beitrag antworten »
Multikriterielle Lineare Optimierung - Simplex Algorithmus Meine Frage: Hallo, ich habe folgendes Problem bei der Lösung eines Teilergebnisses bei der Anwendung des Simplex Algortihmus: 3 Zielfunktionen sind gegeben: $\begin{eqnarray} u_1 = 3x_1 + x_2 + 2x_3 + x_4<br /> u_2 = x_1 - x_2 + 2x_3 + 4x_4<br /> u_3 = -x_1 + 5x_2 + x_3 + 2x_4 \end{eqnarray}$ die gemäß diesen beiden Nebenbedingungen maximiert werden sollen: $\begin{eqnarray} 2x_1 + x_2 + 4x_3 + 3x_4 \leq 60 & (Schlupf: x_5)<br /> 3x_1 + 4x_2 + x_3 + 2x_4 \leq 60 & (Schlupf: x_6) \end{eqnarray}$ Da der Lösungsraum ja mehrdimensional ist, liefert der Simplex Algortihmus mehrere Eckpunkte als mögliche Lösungen. Im ersten Berechnungsschritt erweist sich nun folgende Lösung als die Optimale: $\begin{eqnarray} \begin{vmatrix} x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & u_1 & u_2 & u_3\\ 0 & 6 & 0 & 18 & 0 & 0 & 24 & 66 & 66 \end{vmatrix} \end{eqnarray}$ Diese Lösung erhält man bei der Addition von $\begin{eqnarray} u_1 \end{eqnarray}$ und $\begin{eqnarray} u_2 \end{eqnarray}$ Wie man oben erkennen kann sind bei dieser Lösung $\begin{eqnarray} x_1, x_3, x_5, x_6 \end{eqnarray}$ Nichtbasisvariablen. Soweit so gut - Jetzt heißt es im weiteren Aufgabenverlauf wörtlich: The reduced costs for each of the three objective functions corresponding to these variables are for $\begin{eqnarray} x_1: -2, +0,5, +4,5 \end{eqnarray}$ for $\begin{eqnarray} x_3: -1, +4,5, -0,5 \end{eqnarray}$ for $\begin{eqnarray} x_5: +0,2, +1,8, -0,2 \end{eqnarray}$ and for $\begin{eqnarray} x_6: +0,2, -0,7, +1,3 \end{eqnarray}$ So und nun bin ich mit meinem Latein am Ende... Weiß jemand wie man diese Werte ermitteln kann? Meine Ideen: Ich gehe davon aus, dass die Zahlen die Werte wiederspiegeln, um die sich die Zielfunktionsvariablen bei der Ermittlung des Eckpunktes, also der vorläufig optimalen Lösung, verändert haben - könnte das sein? Aber auch nach, tja mittlerweile etlichen Stunden, die ich über diesem Problem brüte kann ich diesen Zwischenschritt nicht nachvollziehen... Für eine kleine Hilfestellung wäre ich sehr dankbar. Viele Grüße
17.05.2011, 10:39	Reksilat	Auf diesen Beitrag antworten »
RE: Multikriterielle Lineare Optimierung - Simplex Algorithmus Hallo zaccusx, Die "reduzierten Kosten" sind die Einträge der veränderten Zielfunktion im Simplex-Tableau (also das, was da in der letzten Zeile steht - siehe dazu hier oder wiki). Normalerweise liest man hier die Abbruchbedingung ab, nämlich, ob sich die Zielfunktion weiter optimieren lässt, oder ob man fertig ist. Warum Du hier drei Zielfunktionen stehen hast und wie man die gleichzeitig maximieren will, verstehe ich nicht. Wenn man die Summe $\begin{eqnarray} u_1+u_2+u_3 \end{eqnarray}$ maximieren will, dann wäre es sinnvoll, diese Summe als neue Zielfunktion zu wählen. Gruß, Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »