Dualisieren von LP's

03.12.2012, 15:31

Theend9219

Dualisieren von LP's

Optimierungsproblem dualisieren

$\begin{eqnarray*} max 5x_{1}+3x_{2}-2x_{3}-6x_{4}+2x_{5} \end{eqnarray*}$

subject to:

$\begin{eqnarray*} x_{1} -2x_{2}+2x_{3} +7x_{5}=2 \end{eqnarray*}$

$\begin{eqnarray*} -x_{1}-7x_{3}+3x_{4} \geq -4 \end{eqnarray*}$

$\begin{eqnarray*} +4x_{2}-5x_{4}=-7 \end{eqnarray*}$

$\begin{eqnarray*} 3x_{1}-3x_{2}+2x_{3}-4x_{5}\leq 5 \end{eqnarray*}$

Ich habe das erstmal als Matrix geschrieben

$\begin{eqnarray*} A: \begin{pmatrix} 1 & -2 & 2 & 0 & 7 \\ -1 & 0 & -7 & +3 &0 \\ 0 & -4 & 0 & -5 & 0\\ 3 & -3 & 2 & 0 & -4 \end{pmatrix} \end{eqnarray*}$
Und wie geh ich nun vor?

03.12.2012, 16:07

Math1986

Auf diesen Beitrag antworten »

RE: Dualisieren von LP's
Das so als Matrix zu schreiben ist falsch, solange du als Restriktion sowohl Gleichungen als auch Ungleichungen hast.
Bring die Restriktionen n des LPs auf die Form A*x=b (beachte die Gleichheit, du hast auch Ungleichheiten gegeben). Du wirst also Schlupfvariablen einführen müssen.

03.12.2012, 16:17

Theend9219

Auf diesen Beitrag antworten »

RE: Dualisieren von LP's

Zitat:

Original von Theend9219
Optimierungsproblem dualisieren

$\begin{eqnarray*} max 5x_{1}+3x_{2}-2x_{3}-6x_{4}+2x_{5} \end{eqnarray*}$

subject to:

$\begin{eqnarray*} x_{1} -2x_{2}+2x_{3} +7x_{5}=2 \end{eqnarray*}$

$\begin{eqnarray*} -x_{1}-7x_{3}+3x_{4} \geq -4 \end{eqnarray*}$

$\begin{eqnarray*} +4x_{2}-5x_{4}=-7 \end{eqnarray*}$

$\begin{eqnarray*} 3x_{1}-3x_{2}+2x_{3}-4x_{5}\leq 5 \end{eqnarray*}$

Ich habe das erstmal als Matrix geschrieben

$\begin{eqnarray*} A: \begin{pmatrix} 1 & -2 & 2 & 0 & 7 \\ -1 & 0 & -7 & +3 &0 \\ 0 & -4 & 0 & -5 & 0\\ 3 & -3 & 2 & 0 & -4 \end{pmatrix} \end{eqnarray*}$
Und wie geh ich nun vor?

Das heißt also
$\begin{eqnarray*} max 5x_{1}+3x_{2}-2x_{3}-6x_{4}+2x_{5} \end{eqnarray*}$

subject to:

$\begin{eqnarray*} x_{1} -2x_{2}+2x_{3} +7x_{5}=2 \end{eqnarray*}$

$\begin{eqnarray*} x_{1}+7x_{3}-3x_{4}+y_{1} = 4 \end{eqnarray*}$

$\begin{eqnarray*} +4x_{2}-5x_{4}=-7 \end{eqnarray*}$

$\begin{eqnarray*} 3x_{1}-3x_{2}+2x_{3}-4x_{5} +y_{2} =5 \end{eqnarray*}$
? mit jeweils den Schlupfvariablen $\begin{eqnarray*} y_{1}, y_{2} \geq 0 \end{eqnarray*}$

03.12.2012, 16:20

Math1986

Auf diesen Beitrag antworten »

RE: Dualisieren von LP's
Ja, nun als Matrixgleichung schreiben und dualisieren.

PS: Ich gehe mal davon aus, dass die x auch allesamt nicht-negativ sind?

03.12.2012, 16:33

Theend9219

Auf diesen Beitrag antworten »

RE: Dualisieren von LP's
Also es steht da $\begin{eqnarray*} x_{1},x_{3} \in R_{+}, x_{2} \in R_{-}, x_{4},x_{5} \in R \end{eqnarray*}$
was denkst du nun?

04.12.2012, 10:41

Mystic

Auf diesen Beitrag antworten »

RE: Dualisieren von LP's

Zitat:

Original von Theend9219
Also es steht da $\begin{eqnarray*} x_{1},x_{3} \in R_{+}, x_{2} \in R_{-}, x_{4},x_{5} \in R \end{eqnarray*}$
was denkst du nun?

Ist ja toll, dass du mit dieser überaus wichtigen Information erst jetzt herausrückst... geschockt

Damit musst du nämlich dann

$\begin{eqnarray*} x_2=-x_2', \ x_4=x_4'-x_4'', \ x_5=x_5'-x_5'' \end{eqnarray*}$

mit nichtnegativen gestrichelten Variablen setzen und es ist dann eine komplett andere Aufgabe daraus geworden...

Neue Frage »

Antworten »

Dualisieren von LP's

Verwandte Themen