Lemma von Farkas aus dem starken Dualitätssatz herleiten

19.02.2008, 00:06	Chris_R	Auf diesen Beitrag antworten »
Lemma von Farkas aus dem starken Dualitätssatz herleiten Hallo! Man soll das Lemma von Farkas aus dem starken Dualitätssatz herleiten. Es gilt also: Falls $\begin{eqnarray} $M = \left\{ {x \in \mathbb{R}^n :Ax = b,x \geqslant 0} \right\} \ne \emptyset \end{eqnarray}$ und $\begin{eqnarray} N = \left\{ {x \in \mathbb{R}^m :A^T y \leqslant c} \right\} \ne \emptyset \end{eqnarray}$ so besitzen: $\begin{eqnarray} $(P)\min c^T x \ unter \ M = \left\{ {x \in \mathbb{R}^n :Ax = b,x \geqslant 0} \right\} \end{eqnarray}$ $\begin{eqnarray} (D)\max b^T y \ unter \ N = \left\{ {x \in \mathbb{R}^m :A^T y \leqslant c} \right\} \end{eqnarray}$ optimale Lösungen $\begin{eqnarray} $x^ \in M,y^* \in N \end{eqnarray}$ und $\begin{eqnarray} b^T y^* = c^T x^* \end{eqnarray}$ Damit soll gezeigt werden, dass: Für $\begin{eqnarray} $A \in \mathbb{R}^{m \times n} \end{eqnarray}$ und $\begin{eqnarray} b \in \mathbb{R}^m \end{eqnarray}$ gilt genau eine der Aussagen: i) $\begin{eqnarray} $Ax=b, x \geq 0 \end{eqnarray}$ ist lösbar durch ein $\begin{eqnarray} x \in \mathbb{R}^n \end{eqnarray}$ ii) $\begin{eqnarray} $A^Ty \leq 0 \end{eqnarray}$ ist lösbar durch ein $\begin{eqnarray} y \in \mathbb{R}^m \end{eqnarray}$ In der Musterlösung wird die Aufgabe auf folgende Äquivalenz reduziert: $\begin{eqnarray} M \ne \emptyset \Leftrightarrow \forall y \in \mathbb{R}^m \ mit \ A^T \leqslant 0 \ gilt \ b^T y \leqslant 0 \end{eqnarray}$ Bedeutet es aber nicht, dass wenn: $\begin{eqnarray} \forall\ y \in \mathbb{R}^m \ mit \ A^Ty \leq 0 \ gilt \ b^Ty \leq 0 \end{eqnarray}$ gilt, $\begin{eqnarray} Ax=b \end{eqnarray}$ lösbar ist? Aber dann hat man ja den zweiten Fall $\begin{eqnarray} A^Ty \leq 0 \end{eqnarray}$ , ist lösbar durch ein $\begin{eqnarray} y \in \mathbb{R}^m \end{eqnarray}$ aus den Augen verloren. Denn es gibt ja auch diese Alternative beim Lemma von Farkas, die in: $\begin{eqnarray} \forall\ y \in \mathbb{R}^m \ mit \ A^Ty \leq 0 \ gilt \ b^Ty \leq 0 \end{eqnarray}$ nicht berücksichtigt wirkt. Oder? Weiter geht die Lösung so: $\begin{eqnarray} Hinrichtung: \\ M \ne \emptyset \end{eqnarray}$ Dann besitzt das primale Problem $\begin{eqnarray} (P) \min c^Tx \ mit \ x \in M \ wobei \ c=0_n \end{eqnarray}$ eine Lösung ist, da $\begin{eqnarray} \inf_{x \in M} \ c^Tx = 0 \end{eqnarray}$ Warum ist denn $\begin{eqnarray} \inf c^Tx = 0 \end{eqnarray}$ ? Nach dem starken Dualitätssatz folgt dann, dass $\begin{eqnarray} \max b^Ty \ unter \ y \in N={y:A^Ty \leq c = 0} \end{eqnarray}$ Weiter gilt dann $\begin{eqnarray} \min(P)=\max(D) \end{eqnarray}$ und da $\begin{eqnarray} (D) \end{eqnarray}$ lösbar ist gibt es ein optimales $\begin{eqnarray} y^* \in \ N \ mit \ b^Ty \leq b^Ty^* = 0 \ \forall y \in N \end{eqnarray}$ Warum ist $\begin{eqnarray} b^Ty^* = 0 \end{eqnarray}$ ? $\begin{eqnarray} \Rightarrow \forall y \in \mathbb{R}^n : A^Ty \leq 0 \ folgt \ b^Ty \leq 0 \end{eqnarray*}$ Die Rückrichtung ist klar. Gruß, Chris
19.02.2008, 11:23	therisen	Auf diesen Beitrag antworten »
http://www.matheplanet.com/matheplanet/n...php?topic=98126

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »