Lagrange-Relaxierung von LPs

18.03.2011, 11:47	plizzz	Auf diesen Beitrag antworten »
Lagrange-Relaxierung von LPs Hallo, ich habe folgendes LP gegeben: $\begin{eqnarray} min\{c^Tx: Ax=a, Bx= b, x\geq 0\} \end{eqnarray}$ Nun bilde ich folgende Lagrange Relaxierung: $\begin{eqnarray} LR(\lambda) = min\{c^Tx - \lambda ^T (Ax-a): Bx= b, x\geq 0\} \end{eqnarray}$ Nun wissen wir, dass gilt: $\begin{eqnarray} max\{LR(\lambda)\} = min\{c^Tx: Ax=a, Bx= b, x\geq 0\} \end{eqnarray}$ Angenommen, ich habe ein optimales $\begin{eqnarray} \lambda^ \end{eqnarray*}$ gefunden. Kann ich dann daraus irgendwie "einfach" eine Optimallösung für das Ausgangsproblem berechnen? Schließlich ist doch nur ausgesagt, dass die Zielfunktionswerte gleich sind, aber es ist doch lange nicht so, dass eine Optimallösung der Lagrange-Relaxierung zulässig für das ursprüngliche Problem ist. Wäre cool, wenn jemand etwas dazu wüsste. Vielen Dank und freundliche Grüße, plizzz

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »