Zwei-Phasen-Simplex

13.01.2012, 10:58

MatheMathosi

Zwei-Phasen-Simplex

Meine Frage:
Löse das folgende LP mit dem Zwei-Phasen Simplex Algorithmus

$\begin{eqnarray*} min \ \ -x_{1}-x_{2} \\ s.t. \ \ 2x_{1} + x_{2}\geq 4 \\ x_{1}+2x_{2}=6 \\ x_{1},x_{2} \geq 0 \end{eqnarray*}$

Meine Ideen:
1. Phase : Finden einer zulässigen Basis.
2. Phase : Simplex mit dieser Basis als Startbasis.

Zuerst bringe ich das LP in Standardform:
$\begin{eqnarray*} min \ \ -x_{1}-x_{2} \\ s.t. \ \ 2x_{1} + x_{2}-x_{3}= 4 \\ x_{1}+2x_{2}=6 \\ x_{1},x_{2},x_{3} \geq 0 \end{eqnarray*}$

Nun einfügen von künstlichen Variablen und einführen der Hilfszielfunktion für Phase 1:

$\begin{eqnarray*} min \ \ y_{1}+y_{2} \\ s.t. \ \ 2x_{1} + x_{2}-x_{3}+y_{1}= 4 \\ x_{1}+2x_{2}+y_{2}=6 \\ x_{1},x_{2},x_{3},y_{1},y_{2} \geq 0 \end{eqnarray*}$

Eine zulässige Basis für dieses Problem ist ja nun B{4,5}.
Mir ist jetzt nicht ganz klar wie es weiter geht. Muss ich nun einfach den Simplex Algorithmus anwenden und bekomme meine zulässige Basis für mein ursprüngliches Problem ?

Ich meine ich muss den Vektor der reduzierten Kosten ausrechnen der lautet
$\begin{eqnarray*} z_{N}=c_{N}-A_{N}^{T}y \end{eqnarray*}$ ???

Dann hätte ich hier den Vektor $\begin{eqnarray*} z_{N}=(-3,-3,1) \end{eqnarray*}$

Mit diesem Vektor hätte ich dann das Simplex Tableau:
$\begin{eqnarray*} \begin{array}{cc|ccccc|c} z & & -3 & -3 & 1 & 0 & 0 & \\ y_{1} & 4 & 2 & 1 & -1& 1 & 0 & \\ y_{2} & 6 & 1 & 2 & 0 & 0 & 1 & \end{array} \end{eqnarray*}$

Und nun müsste ich mein Vektor der reduzierten Kosten positiv machen und habe am Ende meine Startbasis ???
Kann mir bitte jmd helfen ?
Danke im Voraus

15.01.2012, 11:07

MatheMathosi

Auf diesen Beitrag antworten »

Kann mir hier niemand weiterhelfen ?

Wink

15.01.2012, 11:37

Abakus

Auf diesen Beitrag antworten »

Hallo,

ich sehe im ganzen Ablauf nicht, was der Sinn von deiner Hilfszielfunktion sein soll. Wenn du Gleichungen als Nebenbedingungen in der "Standardform" hast und da zusätzlich noch $\begin{eqnarray*} y_i \end{eqnarray*}$ reinschreibst, müssen die doch sofort gleich Null sein?

Abakus smile

15.01.2012, 11:49

MatheMathosi

Auf diesen Beitrag antworten »

Ja in der Phase 1 geht es doch nur darum eine zulässige Basis zu finden.
Ich sehe gerade nicht, wo ich hier einen Fehler gemacht habe verwirrt

15.01.2012, 12:52

Abakus

Auf diesen Beitrag antworten »

OK, deine Aufstellung der Hilfsvariablen verstehe ich jetzt (dauert halt, sich da rein zu denken). Als Basislösung hast du dann B(4, 5), was meinst du jetzt damit (Variable 4 und Variable 5) ?

Wie du weiter machst: normal wie beim Simplex auch, nur wirfst du die Hilfsvariablen in den ersten Schritten als Basisvariable wieder raus. Die ursprüngliche Zielfunktion kannst du mitführen und ebenfalls umformen, die Hilfszielfunktion fällt nach 2 Schritten weg.

Abakus smile

15.01.2012, 12:59

MatheMathosi

Auf diesen Beitrag antworten »

Ja genau die 4. und 5. Variable wähle ich mir als zulässige Basis, mit der ich dann den Simplex starten würde.

Ja ok ich mache normal wie beim Simplex dann weiter, aber wie sieht meine erste Zeile aus die ich logischerweise mit umforme?

Ist das nun meine Hilfszielfunktion oder meine ursprüngliche Zielfunktion ?

Zitat:" Nur wirfst du die Hilfsvariablen in den ersten Schritten wieder raus "

Ja ok das mache ich ja, weil ich dann eine zulässige Basis für mein ursprüngliches Problem habe. oder ?

vielen Dank für deine Hilfe

15.01.2012, 13:22

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von MatheMathosi
Ja ok ich mache normal wie beim Simplex dann weiter, aber wie sieht meine erste Zeile aus die ich logischerweise mit umforme?

Ich habe möglicherweise ein anderes System das aufzuschreiben. Jedenfalls schreibst du in das Simplex alle Nebenbedingungen und beide Zielfunktionen (also den Koeffizientenvektor jeweils bzw. den negativen, je nach deiner Schreibweise). Zuerst ist aber nur die Hilfszielfunktion (bzw. deren Kriteriumszeile) für die Ermittlung der Pivots entscheidend.

Wenn du den Pivot bestimmt hast, machst du mit der ganzen Matrix den Simplexschritt. Danach fällt eine Hilfsvariable als Basisvariable raus und du bekommst eine neue Basisvariable.

Am Besten einfach mal ausprobieren.

Abakus smile

15.01.2012, 14:43

MatheMathosi

Auf diesen Beitrag antworten »

Also ich habe mir nochmal überlegt wie das jetzt gehen sollte.

Wir haben ja unser ursprüngliches Problem in ein neues mit künstlichen Variablen und Hilfsfunktion umformuliert.

So jetzt muss ja einfach nur der Simplex hierauf angewendet werden, um eine zulässige Basis zu finden.

D.h. ich muss den Vektor der reduzierten Kosten ausrechnen der lautet
$\begin{eqnarray*} z_{N}=c_{N}-A^{T}_{N}y \end{eqnarray*}$

wobei c der 1 Vektor ist (von unserer Hilfsfunktion). Die Basis ist ja die 4. und 5. Variable. Also ist die nichtbasis N={1,2,3}.

Der Vektor ist somit (BTRAN) $\begin{eqnarray*} y^{T}=A_{B}^{-1}c^{T}_{B}=\begin{pmatrix} 1 & 0 \\ 0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} =\begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{eqnarray*}$

Pricing $\begin{eqnarray*} z_{N}=0-\begin{pmatrix} 2 & 1 \\ 1 &1 \\ -1 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} =\begin{pmatrix} -3 \\ -2 \\ 1 \end{pmatrix} \end{eqnarray*}$

So nun mache ich die Simplex-Tablaeu Methode :
$\begin{eqnarray*} \begin{matrix} & \\ y_{1} & 4\\ y_{2} & 6 \end{matrix} \begin{vmatrix} -3 & -2 & 1 & 0 & 0 \\ 2 & 1 & -1 & 1 & 0 \\ 1 & 2 & 0 & 0 &1 \end{vmatrix} \end{eqnarray*}$

Da bekomme ich dann $\begin{eqnarray*} x_{1}=6, x_{3}=8 \end{eqnarray*}$ als Basis heraus.

Ist das so richtig ? Kann bitte noch mal jmd darüber schauen ?

15.01.2012, 15:20

MatheMathosi

Auf diesen Beitrag antworten »

So jetzt aber :

Der Vektor der reduzierten Kosten ist

$\begin{eqnarray*} \begin{pmatrix} -3 \\ -3\\ 1 \end{pmatrix} \end{eqnarray*}$

Hatte mich da verrechnet !(also nicht (-3,-2,1) Als Lösung kommt dann die Basis B={1,2} heraus mit
$\begin{eqnarray*} x_{1}=\frac{2}{3}, x_{2}=\frac{8}{3} \end{eqnarray*}$ .

Das ist auch richtig !

@Abakus vielen Dank für deine Mithilfe.

PS: Mit dieser Startbasis macht man dann den Simplex normal mit dem ursprünglichen Problem und erhält die Optimale Lösung $\begin{eqnarray*} (x_{1},x_{2})=(6,0) \end{eqnarray*}$ .

15.01.2012, 17:05

Abakus

Auf diesen Beitrag antworten »

Hier rechne einfach (-1) * (2, 1, -1) + (-1) * (1, 2, 0) = (-3, -3, 1).

Wenn du (0, 0, 0, -1, -1) bzw. (0, 0, 0, 1, 1) in die Kriteriumzeile schreibst und die beiden Einsen mit 2 Schritten rauswirfst, hast du es auch. Ich hoffe, du siehst, was ich meine.

Abakus smile

Neue Frage »

Antworten »

Zwei-Phasen-Simplex

Verwandte Themen