entartete Lösung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe 13:
Für A [mm] \in [/mm] R^(m×n) mit rg(A) = m, b [mm] \in R^m [/mm] und c [mm] \in R^n [/mm] betrachten wir das lineare Optimierungsproblem
(LP) min [mm] c^T*x
[/mm]
N.B. Ax = b,
x [mm] \ge [/mm] 0
Sei B eine Basis von A mit zugehörigen Indexvektoren B und N so, dass [mm] x=(x_B, x_N) [/mm] eine optimale Basislösung für (LP) ist.
Sei [mm] x=(x_B, x_N) [/mm] zusätzlich nicht entartet.
Zeigen Sie:
[mm] (c^T_N [/mm] − [mm] c^T_B*A^{-1}_B *A_N)^T [/mm] [mm] \ge [/mm] 0. |
Hallo!
Also ich hab mir zuerst Überlegt, dass ich die Annahme mache, dass [mm] (c^T_N [/mm] − [mm] c^T_B*A^{-1}_B *A_N)^T [/mm] < 0. und dass ich das dann zum Widerspruch führe.
also ich hab ja eigentlich:
c*x = [mm] c_B*A^{-1}*b \ge c_B*A^{-1}_B*b [/mm] + [mm] (c^T_N [/mm] − [mm] c^T_B*A^{-1}_B *A_N)^T *xneu_N [/mm]
weil ich weiß das [mm] x_N \ge [/mm] 0 ist und nach Annahme die Klammer also die reduizerten Kosten negativ sind ist das gesamte hinten negativ
woraus ja die Ungleichung führt.
aber das ist ja gerade ein Widerspruch zur Optimalität der Lösung x.
aber jetzt frage ich mich wo ich überhaupt einfließen lasse dass [mm] x_B [/mm] > 0 ist, also nicht entartet ist.
danke schonmal!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Do 26.11.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
