Lineare Optimierung - Dualproblem

03.12.2013, 22:21

Bucksi

Lineare Optimierung - Dualproblem

Guten Tag

Ich habe die Aufgabe, das Dualproblem für folgendes lineares Optimierungsproblem zu berechnen. Ich bin mir bei der Umformulierung von min/max-Problem unsicher.
max $\begin{eqnarray*} c^tx \end{eqnarray*}$
Ax=b
(ohne weitere Vorzeichenbedingunge)

Ich habe also standardisiert:
Schritt 1:
$\begin{eqnarray*} max. c^tx^+ - c^tx^- \end{eqnarray*}$
$\begin{eqnarray*} Ax = b \end{eqnarray*}$

Schritt 2:
$\begin{eqnarray*} <b>-</b> min c^tx^+ - c^tx^- \end{eqnarray*}$ i
$\begin{eqnarray*} Ax = b \end{eqnarray*}$

Daraus dann das Dualproblem gebildet:
Schritt 3:
$\begin{eqnarray*} - max b^tu \end{eqnarray*}$
$\begin{eqnarray*} A^tu \end{eqnarray*}$ <= -c
$\begin{eqnarray*} -A^tu \end{eqnarray*}$ <= c

Schritt 4:
$\begin{eqnarray*} - max. b^tu \end{eqnarray*}$
$\begin{eqnarray*} A^tu <= c \end{eqnarray*}$

Schritt 5:
$\begin{eqnarray*} min. -b^tu \end{eqnarray*}$
$\begin{eqnarray*} A^tu <= c \end{eqnarray*}$

Ich bin mir beim Vorgehen ab Schritt 3 nicht mehr sicher. Stimmt es wie ich -max und so umwandle? Bleibt das Minus bis zum Ende bestehen? Wenn nicht, wo ist der Fehler? Ich wäre sehr froh, wenn jemand kurz darüber schauen könnte; mein Dozent stellt sich bzgl. Fragen im Moment etwas quer.

Besten Dank schon im Voraus!

Beste Grüsse
Bucks

07.12.2013, 16:34

Elvis

Auf diesen Beitrag antworten »

siehe hier: http://de.wikipedia.org/wiki/Lineare_Optimierung

(wieso kann ich so viel besser googeln und bei wikipedia nachsehen als jede/jeder Andere ?)

08.12.2013, 21:02

Bucksi

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
siehe hier:

(wieso kann ich so viel besser googeln und bei wikipedia nachsehen als jede/jeder Andere ?)

Vielleicht hätte ich es etwas klarer machen müssen: Bei meinem Problem ist die für die symmetrische Form benötigte Nichtnegativitätsbeschränkung nicht gegegeben. Den normalen Fall kenne ich natürlich und ich habe ihn auch bei Wikipedia wiedergefunden... ;-)

08.12.2013, 21:36

Math1986

Auf diesen Beitrag antworten »

Buchsi, fällt dir eigendlich mal auf, dass deine Latex-Ausführungen komplett unleserlich sind? unglücklich

Also man hat ein primales LP der Form
$\begin{eqnarray*} \max c^T\cdot x, A\cdot x=b \end{eqnarray*}$

Grundsätzlich gilt, dass aus Gleichungen dabei nicht-vorzeichenbeschränkte Variablen (und aus Ungleichungen vorzeichenbeschränkte Variablen) werden.

Aus nicht-vorzeichenbeschränkten Variablen werden also Gleichungen und umgekehrt.

Man erhält so das duale Problem
$\begin{eqnarray*} \min b^T\cdot y, A^T\cdot y=c \end{eqnarray*}$

Bei dir müsste von Schritt 3 auf Schritt 4 aus den zwei Ungleichungen eine Gleichung werden, wenn ich das so richtig sehe.
Von Schritt 4 auf Schritt 5 muss bei dir auch aus dem max ein min werden.

Neue Frage »

Antworten »

Lineare Optimierung - Dualproblem

Verwandte Themen