Konvexe Mengen bei einem Linearen Programm

24.10.2009, 13:13	Sabinee	Auf diesen Beitrag antworten »
Konvexe Mengen bei einem Linearen Programm Hallo Leute , Es geht um folgende Aufgabe: Betrachten Sie ein lineares Programm (LP) in Standardform: $\begin{eqnarray} \{\min cx, \text{ s.d } Ax=b, x\geq 0\} \end{eqnarray}$ . Zeigen Sie, dass die folgenden Mengen konvex sind: (a) die Menge der zulässigen Lösungen von (LP). (b) die Menge der optimalen Lösungen von (LP). Ich bin wie folgt vorgegangen: Zu ersteinmal: Eine Menge $\begin{eqnarray} X\subseteq \mathbb R^n \end{eqnarray}$ heißt konvex genau dann, wenn für alle $\begin{eqnarray} x_1,x_2\in X \end{eqnarray}$ und für alle $\begin{eqnarray} \lambda\in [0,1] \end{eqnarray}$ gilt, dass $\begin{eqnarray} \lambda x_1+(1-\lambda)x_2\in X \end{eqnarray}$ (a) Sei $\begin{eqnarray} x,y\in X \end{eqnarray}$ , dann gilt: $\begin{eqnarray} Ax=Ay=b \end{eqnarray}$ sowie $\begin{eqnarray} x,y\geq 0 \end{eqnarray}$ . Es ist $\begin{eqnarray} \lambda x\geq 0 \end{eqnarray}$ und $\begin{eqnarray} (1-\lambda)y\geq 0 \end{eqnarray}$ da $\begin{eqnarray} \lambda \in [0,1] \end{eqnarray}$ und $\begin{eqnarray} x,y\geq 0 \end{eqnarray}$ . Weiterhin ist: $\begin{eqnarray} A(\lambda x+(1-\lambda)y)=\lambda Ax+Ay-\lambda Ay=\lambda Ay+Ay-\lambda Ay=Ay=b \end{eqnarray}$ Also ist die Menge der zulässigen Lösungen konvex. (b) Sei $\begin{eqnarray} x,y\in X \end{eqnarray}$ also aus der Menge der optimalen Lösungen. Dann gilt: $\begin{eqnarray} cx=cy=z \end{eqnarray}$ , sowie $\begin{eqnarray} Ax=Ay=b \end{eqnarray}$ und $\begin{eqnarray} x,y\geq 0 \end{eqnarray}$ 2 Bedingungen davon habe ich bereits in (a) gezeigt, bleibt noch die erste Bedingung. $\begin{eqnarray} c(\lambda x+(1-\lambda)y)=c\lambda x+cx-c\lambda y=cx+c\lambda x- c\lambda x=cx=z \end{eqnarray}$ Also ist die Menge der optimalen Lösungen von (LP) Ist das so richtig?
24.10.2009, 13:25	Elvis	Auf diesen Beitrag antworten »
RE: Konvexe Mengen bei einem Linearen Programm Weiterhin ist: $\begin{eqnarray} A(\lambda x+(1-\lambda)y)=\lambda Ax+Ay-\lambda Ay=\lambda b+b-\lambda b=b \end{eqnarray}$ Also ist die Menge der zulässigen Lösungen konvex. Den Teil (b) musst du auch noch mal ansehen, da ist auch ein winzig kleiner Rechenfehler drin. Argumentation und Beweis ist sinnvoll, nachvollziehbar und im Wesentlichen richtig. Da fehlt auch noch das Wort "konvex" im Satz "Also ...".
24.10.2009, 13:28	Sabinee	Auf diesen Beitrag antworten »
RE: Konvexe Mengen bei einem Linearen Programm Ja hab meinen Rechenfehler gefunden: $\begin{eqnarray} c(\lambda x+(1-\lambda)y)=c\lambda x+cy-c\lambda y=\lambda z+cy- \lambda z=cy=z \end{eqnarray}$ So sollte es richtig sein oder?
24.10.2009, 13:34	Elvis	Auf diesen Beitrag antworten »
exakt

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »