Nachweis einer Optimallösung durch KKT-Bedingungen

30.12.2015, 19:56	mathmath123	Auf diesen Beitrag antworten »
Nachweis einer Optimallösung durch KKT-Bedingungen Meine Frage: Hallo, ich habe folgende Aufgabe bekommen: Gegeben sei das lineare Problem max x1 + 2 x2 + x3 + 4 x4 s.d. (P) -1 <= 2 x1 + x2 + 2 x3 - 2 x4 <= 2 1 <= - 2 x2 + x3 + 3 x4 <= 5 0 <= x1 <= 2 1 <= x2 <= 5 -3 <= x3 <= 4 2 <= x4 <= 3 (1) Zeigen Sie mithilfe der KKT-Bedingungen, dass x?= (0 , 24/5 , 8/5 , 3)^T Optimallösung von (P) ist. Nehmen Sie Nichtnegativitätsbedingungen dabei nicht explizit als eigene Variable auf. (2) Geben Sie zwei unterschiedliche Optimallösungen (nicht notwendigerweise Basislösungen) des zu (P) dualen Problems an. Hinweis: Was ändert sich zu Teil (1), wenn Sie die Nichtnegativitätsbedingung doch als duale Variable aufnehmen? Meine Problem ist jetzt, dass ich nicht verstehe, wie die KKT-Bedingungen aufzustellen sind und wie ich dadurch zeige, dass x* eine Optimallösung ist. Meine Ideen: Ich habe bereits versucht zunächst das duale Problem (D) aufzustellen, indem ich das Primale auf die Form max c^T x s.d. Ax<= b x1 >= 0 gebracht habe und anhand der Vorlesung das duale Problem min ( 2, 5, 1, -1, 2, 5, -1, 4, 3, 3, -2) u s.d. $\begin{eqnarray} \begin{pmatrix} 2 & 1 & 2 & -2 \\ 0 & -2 & 1 & 3 \\ -2 & -1 & -2 & 2 \\ 0 & 2 & -1 & -3 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 \end{pmatrix}^T u <= \begin{pmatrix} 1 \\ 2 \\ 1 \\ 4 \end{pmatrix} \end{eqnarray*}$ Wie bildet man nun die KKT-Bedingungen? Vielen Dank schon mal im Vorraus LaTeX-Tags eingefügt. Steffen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »