Lineare Optimierung duaSimplex < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Geben Sie die zu min [mm] c^{T}x [/mm] bezgl. Ax ≤ b, x ≥ 0 duale Aufgabe an! Welche Ungleichung gilt zwischen dualen und primalen Zielfunktionswerten |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo Leute, ich bereite mich grade auf eine Klausur mit dem Thema "lineare Optimierung" vor und komme bei dem Thema "Dualität von Aufgaben" nicht recht weiter, ich hoffe, dass ich in diesem Forenabschnitt halbwegs richtig bin.
Wie ich ein Tableau mit dem dualen-Simplex-Algorithmus löse ist mir prinzipiell klar, aber nicht recht die Theorie, die dahinter steht.
Mein Lösungsvorschlag für die Aufgabe:
max [mm] b^{T}y [/mm] bzgl. Ay ≤ c, y ≥ 0.
Auch falls meine Idee stimmt, bin ich ratlos, was die Aussage dahinter betrifft, ich habe nur ein bisschen hin- und hergetauscht.
Könnte jemand von euch versuchen, mir mit so einfachen Worten wie möglich zu erklären, was es hiermit auf sich hat?
Vielen Dank und MfG!
PS Falls Erklärungen anhand eines konkreten Beispiels leichter fallen sollten, auch hierzu soll ich die duale Aufgabe finden:
minimiere [mm] 3x_{1} [/mm] + [mm] 4x_{2} [/mm] + [mm] x_{3}
[/mm]
udN [mm] -x_{1} [/mm] - [mm] x_{2} [/mm] + [mm] x_{3} [/mm] ≤ -3
[mm] 3x_{1} [/mm] + [mm] 2x_{2} [/mm] - [mm] x_{3} [/mm] ≤ -1
[mm] x_{1}, x_{2}, x_{3} [/mm] ≥ 0
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:54 Mo 19.09.2011 | | Autor: | Stoecki |
hallo,
bovor du dualisierst solltest du immer das lp auf standardform bringen.
min [mm] c^T [/mm] x s.d. Ax [mm] \le [/mm] b, x [mm] \ge [/mm] 0 ist nicht die standardform. umgeformt hast du hier:
min [mm] c^T [/mm] x s.d. -Ax [mm] \ge-b, [/mm] x [mm] \ge [/mm] 0
ziel ist es beim dualisieren (bei einem minimierungsproblem) untere schranken zu bekommen. das versuchst du durch skalieren der matrix A zu erreichen. du erhälst dabei folgende kette:
[mm] -y^T [/mm] b [mm] \le -y^T [/mm] A x [mm] \le c^T [/mm] x mit x,y [mm] \ge [/mm] 0
wie kommt es dazu. fangen wir mit dem dualen an.
in den nebenbedingungen steht [mm] -y^T [/mm] A [mm] \le c^T
[/mm]
multipliziere mit x [mm] \ge [/mm] 0 [mm] (\ge [/mm] 0, damit das "kleinergleich sich nicht dreht) und du erhälst [mm] y^T [/mm] A x [mm] \ge c^T [/mm] x
betrachten wir die ungleichung des primalen problems: -Ax [mm] \ge [/mm] -b
multipliziere wieder mit y [mm] \ge [/mm] 0 und du hast die andere ungleichung [mm] -b^T [/mm] y [mm] \le y^T [/mm] A x.
Das ist ein anschaulicher ansatz. ein weiterer ansatz ist der von lagrange, der aus der spieltheorie stammt der eine spieler kann die x variablen setzen (hier nichtnegativ) und hat als ziel die funktion [mm] c^T [/mm] x zu minimieren. der duale spieler setzt die y variablen (z.B. auch nichtnegativ) und hat als ziel die einhaltung der nebenbedingungen zu erzwingen und kann verletzungen beliebig bestrafen. man erhält dann folgendes problem:
[mm] max_{y \ge 0} min_{x \ge 0} c^T [/mm] x + [mm] y^T [/mm] (b - Ax)
scahut man sich den term [mm] y^T [/mm] (b - Ax) an fällt auf, dass der y-spieler nur dann eine y-komponente >0 setzt, wenn eine zeile unzulässig im ursprungsproblem ist. andernfalls lohnt sich das nicht.
literatur findest du z.b. hier:
![[]](/images/popup.gif) skript_uni_koeln
|
|
|
|
