[Optimierung] Das duale des dualen Programms ist das primale Programm

07.12.2011, 17:22	T0b1a5	Auf diesen Beitrag antworten »
[Optimierung] Das duale des dualen Programms ist das primale Programm Mahlzeit, ich hänge über einem sehr simplen Problem: Für die Daten $\begin{eqnarray} A \in \mathbb{R}^{m \times n}, b\in \mathbb{R}^m \end{eqnarray}$ und $\begin{eqnarray} c\in \mathbb{R}^n \end{eqnarray}$ sei: $\begin{eqnarray} min \end{eqnarray}$ $\begin{eqnarray} c^Tx \end{eqnarray}$ u.d.N $\begin{eqnarray} Ax=b,x\geq 0 \end{eqnarray}$ das primale lineare Programm und $\begin{eqnarray} \ \ \ \ max \end{eqnarray}$ $\begin{eqnarray} b^T y \end{eqnarray}$ u.d.N $\begin{eqnarray} A^Ty+s=c,s\geq 0 \end{eqnarray}$ das dazugehörige duale lineare Programm. Zeigen Sie: Das duale Programm des dualen Programms ist wieder das primale Programm. Idee: Zuerst schreibe ich das duale Programm in die Normalform: $\begin{eqnarray} min \end{eqnarray}$ $\begin{eqnarray} -b^T y \end{eqnarray}$ u.d.N $\begin{eqnarray} -A^Ty+s=-c,s\geq 0 \end{eqnarray}$ Und hier hört es auf Edit: In vielen Büchern lese ich was vonwegen "Transformationssatz", aber den kenne ich nicht :\
07.12.2011, 23:58	tigerbine	Auf diesen Beitrag antworten »
RE: [Optimierung] Das duale des dualen Programms ist das primale Programm Dann hört es aber zu früh auf. Denn das "Dualisieren" ist dir in der Angabe von der Bauweise schon vorgegeben. Du solltest das duale Programm so formulieren. $\begin{eqnarray} \min_{\lambda^+,\lambda^-,s}(-b,b,c)\begin{pmatrix}\lambda^+\\\lambda^-\\s\end{pmatrix} \end{eqnarray}$ unter den Nebenbedingungen $\begin{eqnarray} (-A^T,A^T,-I)\begin{pmatrix}\lambda^+\\\lambda^-\\s\end{pmatrix}=-c,\lambda^+,\lambda^-,s\geq0 \end{eqnarray}$
11.12.2011, 17:55	T0b1a5	Auf diesen Beitrag antworten »
Irgendwie verstehe ich die Begriffe primales und duales Programm noch nicht vollkommen. Werde mich erst mal damit beschäftigen und mich dann nochmal melden. Danke schon mal Edit: Aufgabe wird an den Nagel gehangen :\

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »