Simplexalgorithmus

02.10.2006, 15:54

Guennikolode

Simplexalgorithmus

Hallo

Hätte da ein Beispiel wo ich nicht weiter weiß, kann man das überhaupt mit simplex lösen????

ZF:
Min 3x+2,5y
s.t.:
30x+40y>=120
40x+20y<=80
-----------------------------
Mein Ansatz, der wahrscheinlich falsch ist lol
----------------------------
ZF:
Min 3x+2,5y
s.t.:
30x+40y>=120
-40x-20y>=-80
-----------------------------
DP nach PP (oder umgekehrt, kenn mi mit de Bezeichnungen net aus)
-----------------------------
ZF:
Max 120x-80y
s.t.:
30x-40y<=3
40x-20y<=2,5
-----------------------------
Simplextabelle:
____x___y___x2___y2
x2|_30_-40___1___0_|_3_|0,1
y2|_40_-20___0___1_|2,5|0,0625
___120_-80__0___0__|0_|
1.Spalte & 2. Zeile
____y2__y___x2___x
x2|_0__-25___1___0_|_1,125
y1|_1__-0,5___0_1/40_|0,0625
____0_-20___0___-3__|-7,5

Wenn ich wieder zurückrechne ins DP kommt heraus:

x=3
y=20

das kann aber auf grund von s.t. net stimmen, was mach ich falsch????

02.10.2006, 19:55

Guennikolode

Auf diesen Beitrag antworten »

es gibt aber nicht viele antworten!?!

02.10.2006, 19:58

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Guennikolode
es gibt aber nicht viele antworten!?!

... was sich durch pushen auch nicht ändern wird.

02.10.2006, 20:00

JochenX

Auf diesen Beitrag antworten »

Zitat:

Original von Dual Space

Zitat:

Original von Guennikolode
es gibt aber nicht viele antworten!?!

... was sich durch pushen auch nicht ändern wird.

Stattdessen wäre lesbar darstellen angebracht.

Dein Beitrag ist einfach völlig unlesbar, dafür gibt es LaTeX (Formeleditor) hier im Forum.

02.10.2006, 20:13

swerbe

Auf diesen Beitrag antworten »

RE: Simplexalgorythmus

Zitat:

Original von Guennikolode

Hätte da ein Beispiel wo ich nicht weiter weiß, kann man das überhaupt mit simplex lösen????

Also, ohne deine Aufgabe durchgerechnet zu haben (sorry, ist einfach zu unleserlich...), kann ich dir sagen, dass sich mit dem Simplex-Verfahren IMMER eine Lösung finden lässt (solange die Lösungsmenge nicht leer ist bzw. sich die Ungleichungsrestriktionen nicht wiedersprechen). Sollte dies jedoch der Fall sein, erkennst du einen leeren Lösungsbereich ganz einfach daran, dass sich in irgendeinem Simplex-Tableau nicht weiterrechnen lässt, bsp. wenn eine Divison durch 0 kommt oder ähnliches...

Versuch doch deine Lösung mal hinsichtlich der Restriktionen zu prüfen, wenn sich kein Widerspruch ergibt, ist es ja vielleicht schon ein zulässige Basislösung (wenn vielleicht auch nicht die optimalste...)

Gruß
swerbe

02.10.2006, 20:15

Guennikolode

Auf diesen Beitrag antworten »

Hier nochmal schöner:
(besser bekomme ich keine Simplextabelle zusammen)

ZF:
$\begin{eqnarray*} \min 3x+2.5y \end{eqnarray*}$
s.t.:
$\begin{eqnarray*} 30x+40y \geq 120 \end{eqnarray*}$
$\begin{eqnarray*} 40x+20y \leq 80 \end{eqnarray*}$
-----------------------------
Mein Ansatz, der wahrscheinlich falsch ist lol
----------------------------
ZF:
$\begin{eqnarray*} \min 3x+2.5y \end{eqnarray*}$
s.t.:
$\begin{eqnarray*} 30x+40y\geq 120 \end{eqnarray*}$
$\begin{eqnarray*} -40x-20y \geq -80 \end{eqnarray*}$
-----------------------------
DP nach PP (oder umgekehrt, kenn mi mit de Bezeichnungen net aus)
-----------------------------
ZF:
$\begin{eqnarray*} \max 120x-80y \end{eqnarray*}$
s.t.:
$\begin{eqnarray*} 30x-40y \leq 3 \end{eqnarray*}$
$\begin{eqnarray*} 40x-20y \leq 2,5 \end{eqnarray*}$
-----------------------------
Simplextabelle:
$\begin{eqnarray*} \begin{vmatrix} .. & x & y & x2 & y2 & .. \\ x_2 & 30 & -40 & 1 & 0 & 3 \\ y_1 & 40 & -20 & 0 & 1 & 2,5 \\ .. & 120 & -80 & 0 & 0 & 0 \end{vmatrix} \end{eqnarray*}$
1.Spalte & 2. Zeile
$\begin{eqnarray*} \begin{vmatrix} .. & y_2 & y & x2 & x & .. \\ x_2 & 0 & -25 & 1 & 0 & 1,125 \\ y_1 & 1 & -0,5 & 0 & 0,025 & 0,0625 \\ .. & 0 & -20 & 0 & -3 & -7,5 \end{vmatrix} \end{eqnarray*}$

Wenn ich wieder zurückrechne ins DP kommt heraus:

$\begin{eqnarray*} x=3 \end{eqnarray*}$
$\begin{eqnarray*} y=20 \end{eqnarray*}$

das kann aber auf grund von s.t. net stimmen, was mach ich falsch????

Edited by Stefan: $\begin{eqnarray*} \text{\LaTeX} \end{eqnarray*}$

02.10.2006, 20:18

Guennikolode

Auf diesen Beitrag antworten »

sorry bei der 2. Simplex gehört natürlich x statt y1!

02.10.2006, 20:21

Dual Space

Auf diesen Beitrag antworten »

Zitat:

Original von Guennikolode
sorry bei der 2. Simplex gehört natürlich x statt y1!

Editier das mal selbst. Augenzwinkern

03.10.2006, 00:50

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Guennikolode

1.Spalte & 2. Zeile
$\begin{eqnarray*} \begin{vmatrix} .. & y_2 & y & x2 & x & .. \\ x_2 & 0 & -25 & 1 & 0 & 1,125 \\ y_1 & 1 & -0,5 & 0 & 0,025 & 0,0625 \\ .. & 0 & -20 & 0 & -3 & -7,5 \end{vmatrix} \end{eqnarray*}$

Hier ist noch ein RF in der ersten Zeile (die letzte Null ?).

Zitat:

Wenn ich wieder zurückrechne ins DP kommt heraus:

$\begin{eqnarray*} x=3 \end{eqnarray*}$
$\begin{eqnarray*} y=20 \end{eqnarray*}$

das kann aber auf grund von s.t. net stimmen, was mach ich falsch????

Im Ausgangsproblem hast du eine degenerierte Basislösung (dh. eine der Basisvariablen ist Null). Das könnte hier zu Verwirrung führen.
Hier musst du noch einmal überlegen, welche Struktur- und Schlupfvariablen sich primal/dual entsprechen. Bei korrekter Zuordnung könnte hier (0, 3) rauskommen.

Grüße Abakus smile

03.10.2006, 15:36

Guennikolode

Auf diesen Beitrag antworten »

Stimmt, da gehört statt der Null 1,125!
(hat aber auf das ergebnis jetzt keinen einfluss)

Stimmt, das ist kein DP in standardform. Schön langsam komme ich drauf wie das mit den dualen linearem programm und dem primalen linearen programm gemeint ist. Tue mir hier noch etwas schwer.

Danke Abakus, du hast mir echt weitergeholfen (auch wenn ich mir mit PP und DP noch immer schwer tue)!!

mfg

Neue Frage »

Antworten »

Simplexalgorithmus

Verwandte Themen