Dualität bei Simplex Algorithm < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:11 So 16.03.2008 | | Autor: | Jennifer |
| Aufgabe | Lineares Programm
min 5x_11+4,5x_12+3x_13+4,5x_21+3,5x_22+4X_23
unter den Nebenbedingungen
x_11+x_21 [mm] \ge [/mm] 70
x_12+x_22 [mm] \ge [/mm] 80
x_13+x_23 [mm] \ge [/mm] 50
x_11+x_12+x_13 [mm] \le [/mm] 110
x_21+x_22+x_23 [mm] \le [/mm] 90
x_11, x_12, x_13, x_21, x_22, x_23 [mm] \ge [/mm] 0 |
Hallo,
ich muss das folgende Programm in das duale Programm max umwandeln und habe noch nicht genau eine Ahnung, wie man das anstellt. Die richtige Lösung dazu habe ich schon, und mir ist schonmal klar, dass
max [mm] 70y_1+80y_2+50y_3-110y_4-90y_5 [/mm] gilt
die Nebenbedingungen sind dann
[mm] y_1-y_4 \le [/mm] 5
[mm] y_2-y_4 \le [/mm] 4,5
[mm] y_3-y_4 \le [/mm] 3
[mm] y_1-y_5 \le [/mm] 4,5
[mm] y_2-y_5 \le [/mm] 3,5
[mm] y_3-y_5 \le [/mm] 4
[mm] y_1,y_2,y_3,y_4,y_5 \ge [/mm] 0
Jetzt machen für mich zwar die Werte 5,4,,5 usw. Sinn, aber ich habe keine Ahnung, wie ich auch z.B. auf [mm] y_1-y_4 [/mm] komme und auch die Gleichheitszeichen verstehe ich nicht ganz. Wenn sie einfach mit -1 multipliziert werden würden müssten sie sich ja alle jeweisl umdrehen, aber das scheint hier ja nicht der Fall zu sein ;(
Wäre schön, wenn mir jemand helfen könnte.
Gruß
Jenny
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:53 So 16.03.2008 | | Autor: | barsch |
Hi Jenny,
man muss sich erst einmal zurecht finden bei den ganzen Indizes  (Sollte ich die Schlacht gegen die Indizes irgendwo mal verloren haben ![[sorry]](/images/smileys/sorry.gif "[sorry]") , kann passieren - Also kritisch lesen  )
Du kannst - wie du sicher weißt - dieses Problem auch mit einer Matrix und Vektoren darstellen.
Dein primales Problem hat momentan die Form (Vorsicht: Habe Indizes verändert!):
min [mm] 5x_1+4,5x_2+3x_3+4,5x_4+3,5x_5+4x_6
[/mm]
unter den Nebenbedingungen
[mm] x_1 +x_4 [/mm] $ [mm] \ge [/mm] $ 70
[mm] x_2+x_5 [/mm] $ [mm] \ge [/mm] $ 80
[mm] x_3+x_6 [/mm] $ [mm] \ge [/mm] $ 50
[mm] x_1+x_2+x_3 [/mm] $ [mm] \le [/mm] $ 110
[mm] x_3+x_4+x_6 [/mm] $ [mm] \le [/mm] $ 90
[mm] x_1, x_2, x_3, x_4, x_5, x_6 [/mm] $ [mm] \ge [/mm] $ 0
Du kannst noch folgendes machen, damit du überall den [mm] \ge-Operator [/mm] hast:
min [mm] 5x_1+4,5x_2+3x_3+4,5x_4+3,5x_5+4x_6
[/mm]
unter den Nebenbedingungen
[mm] x_1 +x_4 [/mm] $ [mm] \ge [/mm] $ 70
[mm] x_2+x_5 [/mm] $ [mm] \ge [/mm] $ 80
[mm] x_3+x_6 [/mm] $ [mm] \ge [/mm] $ 50
[mm] \red{-x_1-x_2-x_3\ge{-110}}
[/mm]
[mm] \red{-x_3-x_4-x_6\ge{-90}}
[/mm]
[mm] x_1, x_2, x_3, x_4, x_5, x_6 [/mm] $ [mm] \ge [/mm] $ 0
Du hast demnach die allgemeine Form:
min [mm] c^T*x
[/mm]
s.t. [mm] A*x\ge{b}
[/mm]
[mm] x\ge{0}
[/mm]
Jetzt musst du dieses Problem auf die Form bekommen:
min [mm] c^T*x
[/mm]
s.t. [mm] A*x\red{=}{b}
[/mm]
[mm] x\ge{0}
[/mm]
Dann kannst du das primale Problem ganz einfach ins Duale umwandeln.
Das duale Problem sieht dann so aus:
max [mm] b^T*y
[/mm]
s.t. [mm] A^T*y\le{c}
[/mm]
Der erste (und vielleicht schwierigste) Schritt:
Wie bekommst du [mm] A*x\ge{b} [/mm] auf die Form [mm] A*x\red{=}{b}?
[/mm]
Du musst neue Variablen einführen:
min $ [mm] 5x_1+4,5x_2+3x_3+4,5x_4+3,5x_5+4x_6+0*x_7+0*x_8+0*x_9+0*x_{10}+0*x_{11} [/mm] $
unter den Nebenbedingungen
[mm] x_1 +x_4-x_7=70
[/mm]
[mm] x_2+x_5 -x_8=80
[/mm]
[mm] x_3+x_6-x_9 [/mm] =50
[mm] x_1+x_2+x_3-x_{10}=-110
[/mm]
[mm] x_3+x_4+x_6-x_{11}=-90
[/mm]
mit [mm] x_1,x_2,...,x_{11}\ge{0}
[/mm]
Ich hoffe, du weißt, was mit c und b (beides Vektoren) und A (Matrix) gemeint ist.
[mm] c^T=(5;4,5;3;4,5;3,5;4;0;0;0;0;0) [/mm] und b ist
[mm] b=\vektor{70 \\ 80 \\ 50 \\ 110 \\ 90}
[/mm]
Die Matrix A ist zu groß, als dass ich sie hier noch hinschreiben kann.
Ich hoffe, es hilft dir weiter.
MfG barsch
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:17 Mi 19.03.2008 | | Autor: | Jennifer |
Vielen Dank :) Hat super gepasst bis auf einen kleinen Vorzeichenfehler. Aber bei den risen Matrizen ist das schon verständlich ;)
lg
jenny
|
|
|
|
