Simplexverfahren: Dualität < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 07:08 Mo 23.02.2009 | | Autor: | xyza |
Hallo,
ich habe eine Frage zum Simplex-Algorithmus und zur Dualität:
Und zwar steht in meinem Skript:
Sei [mm] \min \left\{c^t x|Ax=b, x\leq 0 \right\} [/mm] ein lineares Programm, bei dem schon eine Basis gegeben ist, also A=(A|I). Dann ist das Duale dazu [mm] \max \left\{b^t \pi|A^t \pi \leq c, \pi\leq 0\right\} [/mm]. Die primale Lösung zu B ist [mm] (x_B , x_N)=(A_B ^{-1} b,0) [/mm]
(wobei [mm] A_B ^{-1} [/mm] die zu der Basis B gehörige invertierte Matrix ist). Die duale Lösung zur Basis B ist [mm] \pi^t=c_B ^t A_B ^{-1} [/mm]. Die primale Lösung kann also in der rechten Spalte, die duale Lösung in der Kostenzeile, abgelesen werden.
Falls B eine zulässige Basis ist gilt:
Die duale Lösung [mm] \pi [/mm]ist genau dann zulässig, wenn die primale Lösung X optimal ist.
Soviel zur Theorie. Ich habe ein Beispiel, bei dem das nciht zu stimmen scheint und wüsste gerne von euch ,was ich falsch mache:
[mm] A=\begin{pmatrix}
-1 & 1& 1&0\\
1&1&0&1
\end{pmatrix}
b=\begin{pmatrix}
1\\
1
\end{pmatrix}
c=\begin{pmatrix}
0\\
-1\\
0\\
0
\end{pmatrix}
[/mm]
Simplextableau zur Basis [mm] \left\{3,4\right\} [/mm]:
1, 0,-1,0,0,0
0,-1, 1,1,0,1
0, 1, 1,0,1,1
Simplextableau zur Basis [mm] \left\{{2,4\right\} [/mm] (durch Pivotoperationen):
1,-1,0, 1,0,1
0,-1,1, 1,0,1
0, 2,0,-1,1,0
Simplextableau zur Basis [mm] \left\{1,2\right\} [/mm] (durch Pivotoperationen):
1,0,0, 0.5,0.5,1
0,0,1, 0.5,0.5,1
0,1,0,-0.5,0.5,0
Da alle Einträge in der Kostenzeile (ganz oben) positiv sind, ist diese Lösung also optimal. Weil die Lösung zu [mm] \left\{2,4\right\} [/mm], also x=(0,1,0,0) aber den gleichen Zielfunktionswert hat, ist diese auch optimal.
Die zugehörige duale Lösung ist (1,0) (da bin ich mir jetzt nicht so sicher!!!).
Es gilt aber [mm] A^t (1,0)^t=(0,0,-1,1)^t [/mm] und das ist nicht kleinergleich [mm] c=(0,-1,0,0)^t [/mm].
Ist also (1,0) nicht die duale Lösung? Aber was ist dann die duale Lösung? Ich dachte ich müsste immer die Einträge nehmen, in deren Spalten vorher die Einheitsmatrix war, weil dort [mm] c_b ^t A_B ^(-1) I [/mm]
drinsteht und das ist ja genau meine duale Lösung, oder??
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.matheplanet.de/,
allerdings schon letzten Mittwoch und noch keine Antwort erhalten, deswegen dachte ich, versuch ichs mal hier.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:20 Di 03.03.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
