Simplex-Unbeschränktheit

21.10.2009, 01:02	Thilo S	Auf diesen Beitrag antworten »
Simplex-Unbeschränktheit Hi Leute, ich habe einen ein lineares Optimierungsproblem mittels des Simplexalgorithmus "gelöst", allerdings ist mein zulässiger Bereicht unbeschränkt durch die x-Achse, die y-Achse, $\begin{eqnarray} x_2 = x_1 + 3 \end{eqnarray}$ und $\begin{eqnarray} x_2 = x_1 /2 -2 \end{eqnarray}$ . Das das Problem im R² liegt, soll ich nun die Konstanten von Min. $\begin{eqnarray} c_1 x_1 + c_2 x_2 \end{eqnarray}$ so finden, dass alle möglichen Lösungsfälle durchgespielt werden, bzw. für welche $\begin{eqnarray} c_1 \end{eqnarray}$ , $\begin{eqnarray} c_2 \end{eqnarray}$ bleibt es unlösbar. Mein Ansatz ist mal: Für $\begin{eqnarray} c_1 \end{eqnarray}$ = 0 ist $\begin{eqnarray} 1x_2 \in [0,3] \end{eqnarray}$ und für $\begin{eqnarray} c_2 \end{eqnarray}$ = 0 ist $\begin{eqnarray} 1x_1 \in [0,4] \end{eqnarray}$ Lösung. Des weiteren denke ich, dass alle Geraden, die durch den Ursprung gehen, aber nicht in der zulässigen Menge liegen (also nur (0,0) als Lösung haben) auch Lösung sind. Für alle c, die Geraden innerhalb des Winkels der zwei Beschränkungsgraden s.o. liegen, bleibt das Problem unbeschränkt. Kann mir jemand weiterhelfen? Vielen Dank im Voraus, Thilo
22.10.2009, 14:25	Reksilat	Auf diesen Beitrag antworten »
RE: Simplex-Unbeschränktheit Hi Thilo, Hier mal der zulässige Bereich als Skizze. Zu minimieren ist $\begin{eqnarray} t=c_1x_1+c_2x_2 \end{eqnarray}$ . Graphisch lässt sich das lösen, indem man $\begin{eqnarray} t \end{eqnarray}$ fixiert und sich die zugehörige Gerade einzeichnet. Dann verringert man $\begin{eqnarray} t \end{eqnarray}$ schrittweise, was sich im Koordinatensystem als Parallelverschiebung bemerkbar macht. Dies macht man so lange, bis die Gerade aus dem zulässigen Bereich wandern würde - das zugehörige $\begin{eqnarray} t \end{eqnarray}$ ist der Optimalwert. Bleibt die Gerade für beliebig kleine $\begin{eqnarray} t \end{eqnarray}$ im zulässigen Bereich, so ist das Problem nicht lösbar (unbeschränkt). Beispiel: Nehmen wir mal an, dass $\begin{eqnarray} c_1=5 \end{eqnarray}$ und $\begin{eqnarray} c_2=-1 \end{eqnarray}$ ist, dann lässt sich die Gerade als $\begin{eqnarray} x_2=5x_1-t \end{eqnarray}$ schreiben. Zeichnet man die Gerade für verschiedene Werte, so sieht man, dass man für $\begin{eqnarray} t<-3 \end{eqnarray}$ aus dem zulässigen Bereich geraten würde. $\begin{eqnarray} t=-3 \end{eqnarray}$ ist die optimale Lösung. Das zur Veranschaulichung. Jetzt musst Du Dir überlegen, wie man das am besten verallgemeinert. Wenn Du den Simplexalgorithmus beherrschst, dann solltest Du einfach mit den Parametern $\begin{eqnarray} c_1 \end{eqnarray}$ und $\begin{eqnarray} c_2 \end{eqnarray}$ losrechnen und wann immer nötig Fallunterscheidungen machen. Gruß, Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »