Lineare Programm graphisch lösen

Neue Frage »

14.11.2009, 23:14	Sarah20	Auf diesen Beitrag antworten »
Lineare Programm graphisch lösen Lösen Sie das LP $\begin{eqnarray} \min 2x_1 + 15x_2+5x_3+6x_4 \end{eqnarray}$ s.d $\begin{eqnarray} x_1+6x_2+3x_3+x_4\geq 2 \end{eqnarray}$ $\begin{eqnarray} -2x_1+5x_2-4x_3+3x_4\leq -3 \end{eqnarray}$ $\begin{eqnarray} x_1,x_2,x_3,x_4\geq 0 \end{eqnarray}$ Ich kann ja schlecht 4-dimensional zeichnen deswegen habe ich mir gedacht ich bilde das duale Programm dazu womit ich maximierungsproblem im 2 dimensionalen hätte. Kann ich das so machen? Danke
14.11.2009, 23:35	Mystic	Auf diesen Beitrag antworten »
Klar kannst du
15.11.2009, 13:37	Sarah20	Auf diesen Beitrag antworten »
Kann dann mal jemand nachgucken ob ich das duale lineare Programm dazu richtig bestimme. $\begin{eqnarray} \max 2\pi_1 - 3\pi_2 \end{eqnarray}$ s.d $\begin{eqnarray} \pi_1-2\pi_2 \leq 2 \end{eqnarray}$ $\begin{eqnarray} 6\pi_1+5\pi_2\leq 15 \end{eqnarray}$ $\begin{eqnarray} 3\pi_1-4\pi_2\leq 5 \end{eqnarray}$ $\begin{eqnarray} \pi_1+3\pi_2\leq 6 \end{eqnarray}$ $\begin{eqnarray} \pi_1,\pi_2,\pi_3,\pi_4\geq 0 \end{eqnarray}$ Stimmt das? Ich kriege nämlich beim zeichnen was komisches raus
15.11.2009, 14:06	Mystic	Auf diesen Beitrag antworten »
Ne, da stimmt einfach nichts... Wie schaut denn bei dir der Zwischenschritt aus, wo du zuerst das Primalproblem auf die Standardform bringst?
15.11.2009, 15:05	Sarah20	Auf diesen Beitrag antworten »
Ahso ich habe es versuch sofort von der allgemeinen Form ins duale zu bringen. Also in (SF) sieht das folgendermaßen aus: $\begin{eqnarray} \min 2x_1+15x_2+5x_3+6x_4 \end{eqnarray}$ s.d $\begin{eqnarray} x_1+6x_2+3x_3+x_4-x_5=2 \end{eqnarray}$ $\begin{eqnarray} -2x_1+5x_2-4x_3+3x_4+x_6=-3 \end{eqnarray}$ $\begin{eqnarray} x_i\geq 0 \end{eqnarray}$ , $\begin{eqnarray} i=1,...,6 \end{eqnarray}$ Soo nun ins duale: $\begin{eqnarray} \max 2\pi_1-3\pi_2 \end{eqnarray}$ $\begin{eqnarray} \pi_1-2\pi_2\leq 2 \end{eqnarray}$ $\begin{eqnarray} 6\pi_1+5\pi_2\leq 15 \end{eqnarray}$ $\begin{eqnarray} 3\pi_1-4\pi_2\leq 5 \end{eqnarray}$ $\begin{eqnarray} \pi_1+3\pi_2\leq 6 \end{eqnarray}$ $\begin{eqnarray} -\pi_1\leq 0 \end{eqnarray}$ $\begin{eqnarray} \pi_2\leq 0 \end{eqnarray}$ $\begin{eqnarray} \pi_1,\pi_2 \end{eqnarray}$ beliebig So richtig?
15.11.2009, 15:23	Mystic	Auf diesen Beitrag antworten »
Hm, ich fürchte, da haben wir uns missverstranden... Die Standardform ist bei mir jene, wo nur Ungleichungen der Form $\begin{eqnarray} \le \end{eqnarray}$ vorkommen (oder auch $\begin{eqnarray} \ge \end{eqnarray}$ , das kannst dir aussuchen, wenn dir das lieber ist, musst aber dann für alle Ungleichungen dabei bleiben!), d.h., man muss alle Nebenbedingungen auf diese Form bringen... Was du hingeschrieben hast, wäre aber schon die Normalform mit den Schlupfvariablen, die man braucht, um das Simplexverfahren anwenden zu können, die aber bei der Umwandlung primal <-> dual keine Rolle spielt...
Anzeige

15.11.2009, 15:45	Sarah20	Auf diesen Beitrag antworten »
Dann auf ein neues: Ich habe es zunächst so umgeformt: $\begin{eqnarray} \min 2x_1+15x_2+5x_3+6x_4 \end{eqnarray}$ $\begin{eqnarray} x_1+6x_2+3x_3+x_4\geq 2 \end{eqnarray}$ $\begin{eqnarray} 2x_1-5x_2+4x_3-3x_3\geq 3 \end{eqnarray}$ $\begin{eqnarray} x_1,x_2,x_3,x_4\geq 0 \end{eqnarray}$ Das duale Problem dazuu sieht so aus: $\begin{eqnarray} \max 2\pi_1+3\pi_2 \end{eqnarray}$ $\begin{eqnarray} \pi_1+2\pi_2\leq 2 \end{eqnarray}$ $\begin{eqnarray} 6\pi_1-5\pi_2\leq 15 \end{eqnarray}$ $\begin{eqnarray} 3\pi_1+4\pi_2\leq 5 \end{eqnarray}$ $\begin{eqnarray} \pi_1-3\pi_2\leq 6 \end{eqnarray}$ $\begin{eqnarray} \pi_2,\pi_2\geq 0 \end{eqnarray}$ Stimmt das jetzt?
15.11.2009, 15:57	Mystic	Auf diesen Beitrag antworten »
Ja, passt jetzt so, wenn ich nichts übersehen habe ....
15.11.2009, 16:08	Sarah20	Auf diesen Beitrag antworten »
Ich habe folgende Eckpunkte wenn ich das zeichne: $\begin{eqnarray} A(1/0,5) \end{eqnarray}$ , $\begin{eqnarray} B\left(\frac{5}{3}/0\right) \end{eqnarray}$ , $\begin{eqnarray} C(0/1) \end{eqnarray}$ Das Maximum liegt dann bei $\begin{eqnarray} (\pi_1/\pi_2)=(1/0,5) \end{eqnarray}$ Richtig? Wie übertrage ich das jetzt ins primale und wie sieht die Lösung dort aus?
15.11.2009, 17:05	Mystic	Auf diesen Beitrag antworten »
Naja, ganz so einfach ist die Sache dann doch nicht... Du kannst dir den Wert des Maximums, nämlich 7/2, durch Einsetzen des Optimalen Punktes (1, 1/2) ermitteln und dieser Wert ist zugleich der Wert des Minimums für das primale Problem... Du kannst in dem Fall durch "genaues Hinschauen" sehen, dass du $\begin{eqnarray} x_1=x_3= \frac 12 \end{eqnarray}$ setzen musst, um auf diesen Wert zu kommen, was dann auch garantiert eine optimale zulässige Basislösung ist, ansonsten bleibt dir die (allerdings hier nur einphasige) Simplexmethode auf das duale Problem nicht erspart.. Da kannst dann eben diese beiden Werte unten, wo die Koeffizienten der Zielfunktion stehen, ablesen...
15.11.2009, 17:43	Sarah20	Auf diesen Beitrag antworten »
Super dankeschön für die tolle Hilfe: Eine Frage habe ich noch bei einem anderen Beispie: Es geht wieder darum das duale Problem zu bestimmen: $\begin{eqnarray} \max -2x_1+3x_2+5x_3 \end{eqnarray}$ $\begin{eqnarray} -2x_1+x_2+3x_3+x_4\geq 5 \end{eqnarray}$ $\begin{eqnarray} 2x_1+x_3=4 \end{eqnarray}$ $\begin{eqnarray} -2x_2+x_3+x_4\leq 6 \end{eqnarray}$ $\begin{eqnarray} x_1\leq 0 \end{eqnarray}$ $\begin{eqnarray} x_2,x_3\geq 0 \end{eqnarray}$ $\begin{eqnarray} x_4 \end{eqnarray}$ beliebig. Ich habe folgende Umformung gemacht: $\begin{eqnarray} -\min 2x_1-3x_2-5x_3 \end{eqnarray}$ $\begin{eqnarray} -2x_1+x_2+3x_3+x_4\geq 5 \end{eqnarray}$ $\begin{eqnarray} 2x_1+x_3=4 \end{eqnarray}$ $\begin{eqnarray} 2x_2-x_3-x_4\geq -6 \end{eqnarray}$ $\begin{eqnarray} -x_1,x_2,x_3\geq 0 \end{eqnarray}$ $\begin{eqnarray} x_4 \end{eqnarray}$ beliebig. Das duale Problem dazu sieht dann folgendermaßen aus: $\begin{eqnarray} -\max 5\pi_1+4\pi_-6\pi_3 \end{eqnarray}$ $\begin{eqnarray} 2\pi_1-2\pi_2\leq 2 \end{eqnarray}$ $\begin{eqnarray} \pi_1+2\pi_3\leq -3 \end{eqnarray}$ $\begin{eqnarray} 3\pi_1+\pi_2-\pi_3\leq -5 \end{eqnarray}$ $\begin{eqnarray} \pi_1-\pi_3=0 \end{eqnarray}$ $\begin{eqnarray} \pi_1,\pi_3\geq 0 \end{eqnarray}$ $\begin{eqnarray} \pi_2 \end{eqnarray}$ beliebig Vorallem bei der ersten Nebenbedingung bin ich mir unsicher.
15.11.2009, 18:02	Mystic	Auf diesen Beitrag antworten »
Letzte Hilfe für heute: Du musst - überall, wo $\begin{eqnarray} x_1 \end{eqnarray}$ in den NB vorkommt, das Vorzeichen des zugehörigen Koeffizienten umdrehen und anschließend in den NNB ebenfalls $\begin{eqnarray} x_1 \ge 0 \end{eqnarray}$ voraussetzen. - überall, wo in NB $\begin{eqnarray} x_4 \end{eqnarray}$ vorkommt, dieses durch $\begin{eqnarray} x_4-x_5 \end{eqnarray}$ ersetzen und zu den NNB dann noch $\begin{eqnarray} x_4,x_5 \ge 0 \end{eqnarray}$ dazunehmen - die Gleichung $\begin{eqnarray} 2x_1+x_3=4 \end{eqnarray}$ ersetztn durch die 2 Ungleichungen $\begin{eqnarray} 2x_1+x_3 \ge4,\ -2x_1-x_3 \ge -4 \end{eqnarray}$ Danach kannst dann wie gewohnt das duale Problem formulieren...
15.11.2009, 18:28	Sarah20	Auf diesen Beitrag antworten »
Wieso muss ich das machen? Das mit $\begin{eqnarray} x_1 \end{eqnarray}$ werde ich noch ausführen in den Nebenbedingungen. Alles andere was du sagst muss ich doch nicht machen. Es gilt doch: Ein LP in allgemeiner Form $\begin{eqnarray} \min cx \end{eqnarray}$ $\begin{eqnarray} A^ix=b_i \forall i\in M \end{eqnarray}$ $\begin{eqnarray} A^ix\geq b_i\forall i\in{1,...,m}\setminus M:=\overline{M} \end{eqnarray}$ $\begin{eqnarray} x_j\geq 0 \forall j\in L \end{eqnarray}$ $\begin{eqnarray} x_j \end{eqnarray}$ beliebig $\begin{eqnarray} \forall j\in \{1,...,n\}\setminus L:\overline{L} \end{eqnarray}$ hat das duale LP $\begin{eqnarray} \max b^T\pi^T \end{eqnarray}$ $\begin{eqnarray} A_j^T\pi^T\leq c_j \forall j\L \end{eqnarray}$ $\begin{eqnarray} A_j^T\pi^T=c_j \forall j\in \{1,...,n\}\setminus L:\overline{L} \end{eqnarray}$ $\begin{eqnarray} \pi_i \end{eqnarray}$ beliebig $\begin{eqnarray} \forall i\in M \end{eqnarray}$ $\begin{eqnarray} \pi_i\geq 0 \forall i\in \overline{M} \end{eqnarray}$ Deswegen verstehe ich deine anderen Umformungsschritte nicht.
15.11.2009, 19:48	Mystic	Auf diesen Beitrag antworten »
Aha, wußte nicht, dass ihr das in dieser Allgemeinheit gemacht habt, aber umso besser... Meine Umformungen braucht man aber ohnehin als Vorbereitung zum Simplexverfahren und sie sind daher i.d.R. nicht umsonst...
16.11.2009, 00:34	Sarah20	Auf diesen Beitrag antworten »
Ok soweit war ich aber noch nicht Danke für deine Hilfe

Neue Frage »

Antworten »

Lineare Programm graphisch lösen

Verwandte Themen