Lineares Programm in Standardform

17.10.2009, 14:57	Sandra20	Auf diesen Beitrag antworten »
Lineares Programm in Standardform Hallo ich hoffe ihr könnt mir weiterhelfen. Die Aufgabe lautet: Schreiben Sie die folgenden Problemformulierungen als Lineares Programms in Standardform: $\begin{eqnarray} \max 2x_1-x_2+3x_3 \end{eqnarray}$ s.d $\begin{eqnarray} 4x_1+x_2=2 \end{eqnarray}$ $\begin{eqnarray} x_2-3x_3\geq 1 \end{eqnarray}$ $\begin{eqnarray} 5x_1+x_3\leq 3 \end{eqnarray}$ $\begin{eqnarray} x_1,x_2,x_4,x_5\geq 0 \end{eqnarray}$ $\begin{eqnarray} x_3\in \mathbb R \end{eqnarray}$ Also mein Lineares Programm in Standardform sieht so aus: Es ist $\begin{eqnarray} -\min -2x_1+x_2-3x_3 \end{eqnarray}$ $\begin{eqnarray} x_2-3x_3-x_4= 1 \end{eqnarray}$ $\begin{eqnarray} 5x_1+x_3+x_5= 3 \end{eqnarray}$ $\begin{eqnarray} x_1,x_2,x_4,x_5\geq 0 \end{eqnarray}$ $\begin{eqnarray} x_3\in \mathbb R \end{eqnarray}$ Mein Kostenvektor ist $\begin{eqnarray} c=(-2,1,-3,0,0) \end{eqnarray}$ Meine Matrix lautet: $\begin{eqnarray} A=\begin{pmatrix} 4 & 2 & 0 & 0 & 0 \\ 0 & 1 & -3 & -1 & 0 \\ 5 & 0 & 1 & 0 & 1 \end{pmatrix} \end{eqnarray}$ und $\begin{eqnarray} b=\begin{pmatrix} 2 \\ 1 \\ 3 \end{pmatrix} \end{eqnarray}$ Ist das richtig? Nun das nächste Programm: $\begin{eqnarray} \min 4x_1+3x_2-5x_3 \end{eqnarray}$ s.d $\begin{eqnarray} \|2x_1+x_2\|\leq 3 \end{eqnarray}$ $\begin{eqnarray} x_2\geq 4 \end{eqnarray}$ $\begin{eqnarray} x_2-3x_3+1=2 \end{eqnarray}$ $\begin{eqnarray} x_i\in \mathbb R, i=1,2,3 \end{eqnarray}$ Mein Problem liegt dadrin wie ich die Ungleichung mit dem Betrag zu einer Gleichung mache. Kann mir da jemand einen Tipp geben? Danke
17.10.2009, 15:26	tigerbine	Auf diesen Beitrag antworten »
RE: Lineares Programm in Standardform Programm weiß ich gerade nicht. Würde die Ungleichung wie folgt auflösen. Betrachte ich x2 als Scharparameter, dann ergibt sich $\begin{eqnarray} f_{x_2}(x_1):=\|2x_1+x_2\| = \begin{cases} +2x_1 + x_2, & x_1 \geq -\frac{x_2}{2} \\- 2x_1 - x_2, & x_1 < -\frac{x_2}{2} \end{cases} \end{eqnarray}$ Dann ergeben sich die 2 weiteren Forderungen: $\begin{eqnarray} +2x_1 + x_2 \leq 3 \end{eqnarray}$ $\begin{eqnarray} -2x_1 -x_2 \leq 3 \end{eqnarray}$ Insgesamt $\begin{eqnarray} -\frac{x_2}{2} \leq x_1 \leq \frac{3-x_2}{2} \end{eqnarray}$ $\begin{eqnarray} \frac{-3-x_2}{2} \leq x_1 \leq \frac{-x_2}{2} \end{eqnarray}$ Also ich denke nicht, dass das eine NB gibt, sondern 4. Mehr Ideen habe ich im Moment nicht.
17.10.2009, 16:32	Reksilat	Auf diesen Beitrag antworten »
RE: Lineares Programm in Standardform @tb: Hast Du dann zum Beispiel $\begin{eqnarray} -\frac{x_2}{2}\leq x_1 \end{eqnarray}$ UND $\begin{eqnarray} x_1\leq -\frac{x_2}{2} \end{eqnarray}$ als Nebenbedingungen? Wieso nicht einfach: $\begin{eqnarray} 2x_1+x_2\leq 3 \end{eqnarray}$ und $\begin{eqnarray} 2x_1+x_2\geq -3 \end{eqnarray}$ Gruß, Reksilat.
17.10.2009, 16:50	tigerbine	Auf diesen Beitrag antworten »
RE: Lineares Programm in Standardform Warum einfach wenn es auch kompliziert geht? Schöne zweite Halbzeit.
17.10.2009, 18:38	Sandra20	Auf diesen Beitrag antworten »
RE: Lineares Programm in Standardform Also sind es nur die von Reksilat genannten beiden Bedingungen? Dann sehe das Lineare Programm in Standardform so aus: $\begin{eqnarray} \min 4x_1+3x_2-5x_3 \end{eqnarray}$ $\begin{eqnarray} 2x_1+x_2+x_3=3 \end{eqnarray}$ $\begin{eqnarray} 2x_1+x_2-x_4=-3 \end{eqnarray}$ $\begin{eqnarray} x_2-x_5=4 \end{eqnarray}$ $\begin{eqnarray} x_2-3x_3=1 \end{eqnarray}$ Somit: $\begin{eqnarray} c=(4,3,-5,0,0) \end{eqnarray}$ und $\begin{eqnarray} A=\begin{pmatrix} 2 & 1 & 1 & 0 & 0 \\ 2 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 & -1 \\ 0 & 1 & -3 & 0 & 0 \end{pmatrix} \end{eqnarray}$ und $\begin{eqnarray} b=\begin{pmatrix} 3 \\ -3 \\ 4 \\ 1 \end{pmatrix} \end{eqnarray}$
17.10.2009, 18:59	Reksilat	Auf diesen Beitrag antworten »
RE: Lineares Programm in Standardform Hi Sandra, Bei Dir taucht $\begin{eqnarray} x_3 \end{eqnarray}$ doppelt auf, in der Zeile " $\begin{eqnarray} 2x_1+x_2+x_3=3 \end{eqnarray}$ " sollte die Schlupfvariable anders heißen. Außerdem fehlen die Nichtnegativitätsbedingungen der Schlupfvariablen. Auch für die Variablen $\begin{eqnarray} x_1,x_2,x_3 \end{eqnarray}$ (bzw. in Deinem ersten Programm die Variable $\begin{eqnarray} x_3 \end{eqnarray}$ ) gibt es bisher noch keine Nichtnegativitätsbedingungen, welche aber für ein Programm in Standardform unabdingbar sind. Versuche, wenn nötig, die Variablen jeweils durch zwei nichtnegative Hilfsvariablen darzustellen. Gruß, Reksilat. @tb: Es war ein recht erfreulicher Nachmittag.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »