Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Satz vom komplementären Schlupf

Satz vom komplementären Schlupf

Universität / Fachhochschule

Tags: Komplementärer Schlupf, Lineare Optimierung, Schlupfvariable

Lapislazuli aktiv_icon

16:56 Uhr, 15.07.2012

Hallo,

beschäftige mich gerade mit Linearer Optimierung und Dualisierungen. Dabei ist eine Unklarheit bzgl des Satzes vom komplementären Schlupf aufgetreten.

Gegeben war erstmal folgendes LP:

max - x_{1} - x_{3}

s . t : x_{1} + 2 x_{2} \leq 5

x_{2} + 2 x_{3} = 6

x_{1}, x_{2}, x_{3} \geq 0

Das sollte man zuallererst dualisieren. Habe folgendes Duales Programm aufgestellt: (falls da was falsch ist, würde ich mich über eine begründete verbesserung freuen, habe nämlich noch nie was dualisiert ;-))

min 5 y_{1} + 6 y_{2} - 6 y_{3}

s . t : y_{1} \geq - 1

2 y_{1} + y_{2} - y_{3} \geq 6

2 y_{2} - 2 y_{3} \geq - 6

y_{1}, y_{2}, y_{3} \geq 0

Jetzt das eigtl Problem: "Zeigen Sie mit Hilfe des Satzes vom komplementären Schlupf, dass x"=

(0, \frac{5}{2}, \frac{7}{4})

eine Optimallösung von LP ist."

Wir hatten in der Vorlesung einmal den schwachen Satz vom komplementären Schlupf und den starken Satz vom komplementären Schlupf...

Laut Schwachen gilt:

Zwei zulässige Lösungen x", y" sind beide optimal, genau dann wenn

\sum_{i}^{m}

aij*yi" = ci oder xj*

= 0 \forall j

und

\sum_{j}^{n}

aij*xj" = bi oder yi"

= 0 \forall i

Da wüsste ich schon gerne, was mir das eigtl sagt...Habe im Netz so Aussagen gefunden, dass eine Variable "Schlupf hat oder Null ist" oder, dass "eine Bedingung straff ist", aber was bedeutet das in ganz simpel gesagt?

Dann hatten wir noch den starken Satz vom kompl. Schlupf, der besagt in unserer Version:

Wenn duales und primäres Programm zulässige Lösungen besitzen, dann gibt es auch opt Lösungen mit

\sum_{i}^{m}

aij*yi" = cj

\Leftrightarrow

> 0 (j = 1 ... n)

und

\sum_{j}^{n}

aij*xj" = bi

\Leftrightarrow

= 0 (i = 1 ... m)

Was kann ich damit jetzt machen und wie zeige ich, dass mein gegebenes x" optimale Lösung von LP sein muss?

(Ich denke, ich habe einfach wirklich noch nicht ganz verstanden, was diese beiden Sätze eigtl aussagen...)

Vielen Dank erstmal für das Lesen dieser Aufgabe und vielen Dank für alle (gerne ausführlicheren ) Erklärungen!

Lg

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

ARTMath100 aktiv_icon

12:01 Uhr, 16.07.2012

Bei der Dualisierung scheint mir was nicht zu stimmen:

Transformiere (P) in

$\max - x_{1} - x_{3}$

unter

$(\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & 2 \\ 0 & - 1 & - 2 \end{matrix}) \cdot (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) \leq (\begin{matrix} 5 \\ 6 \\ - 6 \end{matrix})$

$x_{1}, x_{2}, x_{3} \geq 0$

dann ist (D)

$\min 5 y_{1} + 6 y_{2} - 6 y_{3}$

unter

$(\begin{matrix} 1 & 0 & 0 \\ 2 & 1 & - 1 \\ 0 & 2 & - 2 \end{matrix}) \cdot (\begin{matrix} y_{1} \\ y_{2} \\ y_{3} \end{matrix}) \geq (\begin{matrix} - 1 \\ 0 \\ - 1 \end{matrix})$

$y_{1}, y_{2}, y_{3} \geq 0$

Siehe Anhang

ARTMath100 aktiv_icon

13:17 Uhr, 16.07.2012

Nun zum komplementären Schlupf. Die anschaulichste Formulierung ist wohl diese:

(P)

max $c^{T} \cdot x$

$A \cdot x \leq b$

(D)

min $b^{T} \cdot y$

$A^{T} \cdot y = c$

$y \geq 0$

Sind jetzt x* und y* Optimallösungen der beiden Programme, dann gilt:

die den positiven Einträgen von y* entsprechenden Ungleichung in(P) müssen durch x* mit Gleicheit befriedigt werden (d.h. diese Restriktionen sind straff)

Wir bringen also das geg. Programm in folgende Form:

(P) max $- x_{1} - x_{3}$ unter

$(\begin{matrix} 1 & 2 & 0 \\ 0 & 1 & 2 \\ 0 & - 1 & - 2 \\ - 1 & 0 & 0 \\ 0 & - 1 & 0 \\ 0 & 0 & - 1 \end{matrix}) \cdot (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} 5 \\ 6 \\ - 6 \\ 0 \\ 0 \\ 0 \end{matrix})$

Das ergibt

(D) min $5 y_{1} + 6 y_{2} - 6 y_{3}$ unter

$(\begin{matrix} 1 & 0 & 0 & - 1 & 0 & 0 \\ 2 & 1 & - 1 & 0 & - 1 & 0 \\ 0 & 2 & - 2 & 0 & 0 & - 1 \end{matrix}) \cdot (\begin{matrix} {\begin{matrix} y \end{matrix}}_{1} \\ {\begin{matrix} y \end{matrix}}_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \end{matrix}) = (\begin{matrix} - 1 \\ 0 \\ - 1 \end{matrix})$

$y_{1}, ..., y_{6} \geq 0$

Löse das duale Problem:

zum Vergleich:

$y_{1} = \frac{1}{4}, y_{2} = 0, y_{3} = \frac{1}{2}, y_{4} = 2, y_{5} = 0, y_{6} = 0,$

Jetzt müssen die Ungleichungen (1),(3),(4) des primalen Systems durch

$(\begin{matrix} 0 \\ \frac{5}{2} \\ \frac{7}{4} \end{matrix})$

mit Gleichheit erfüllt werden, das ist offensichtlich der Fall, also optimale Lösung.

Lapislazuli aktiv_icon

17:08 Uhr, 19.07.2012

Okay, alles klar. Ist ja sehr logisch, wie Mathe dann letztendlich doch immer wieder ist.

Vielen Dank für die Hilfe!

8mileproof aktiv_icon

16:01 Uhr, 11.08.2013

hallo,

hab zufälligerweise dieselbe aufgabe und eine Frage zu dem Thema:

Wie würde ich jetzt oben das duale Problem lösen? Verwende ich da den Simplex-alg. oder reicht Gauß-Alg. aus?

hab mit Gauß versucht, da ich überall gleichheitszeichen hatte, aber kam nicht auf dasselbe ergebnis.
nun versuche ich es mit simplex...aber irgendwie habe ich da auch verschiedene ergebnisse....

kann mir da jmd. vtl. weiterhelfen?

1108101

1017490

	Status: nicht eingeloggt	Noch nicht registriert?