Maximieren von Funktionen < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei die folgende Opitimierungsaufgabe:
Maximiere [mm] y_1 [/mm] unter den NB I. [mm] y_2 [/mm] - [mm] y_1 \ge [/mm] 0 II. [mm] y_1 [/mm] + [mm] \bruch{y_2}{2} \le \bruch{1}{2}
[/mm]
Von welchem "Primal"-Prohlem in Normalform ist dies das Dualproblem? |
Hi zu dieser Aufgabe habe ich eine Lösung hier, die ich nicht ganz so verstehe.
Das gegebene Problem ist von der Form (D) Max [mm] b^T [/mm] y auf [mm] N:=\{y \in \IR^m |A^Ty\le c \} [/mm] mit
[mm] b^T=(0,1) [/mm] und [mm] c=\vektor{0 \\ \bruch{1}{2}} [/mm] und [mm] A^T=\pmat{ -1 & 1 \\ \bruch{1}{2} & 1 }
[/mm]
Damit ist dann das Primale Problem in Normalform:
Minimiere [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] auf [mm] M:=\{x \in \IR^2 |\pmat{ -1 & \bruch{1}{2} \\ 1 & 1 }\vektor{x_1 \\ x_2 }= \vektor{0 \\ 1 }\}
[/mm]
So irgendwie kann ich diese Lösung nicht verstehen. Es heißt doch Max [mm] y_1. [/mm] Müsste unser [mm] b^T [/mm] dann nicht
[mm] b^T=(1,0) [/mm] heißen??? weil es gilt doch sicherlich [mm] b^T \vektor{y_1 \\ y_2 }.
[/mm]
Ok mit [mm] c=\vektor{0 \\ \bruch{1}{2}} [/mm] bin ich einverstanden. Dann mit der Matrix [mm] A^T=\pmat{ -1 & 1 \\ \bruch{1}{2} & 1 } [/mm] aber wieder nicht. Ich würde hier eher schreiben:
[mm] A^T=\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }, [/mm] denn auch hier müsste es doch wieder heißen:
[mm] A^T y=\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }\vektor{y_1 \\ y_2 }
[/mm]
Multipliziere ich aber [mm] \pmat{ -1 & 1 \\ \bruch{1}{2} & 1 }\vektor{y_1 \\ y_2 } [/mm] komme ich ja nicht auf die NB, die oben gegeben sind.
Also mein Lösungsvorschlag wäre dann für diese Aufgabe, also für das Pirmal-Problem:
Minimiere [mm] c^T [/mm] x auf [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] also
Minimiere [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] auf [mm] M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\}
[/mm]
Was könnt ihr dazu sagen, welche der beiden Lösungen ist denn jetzt hier richtig???
Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:21 Sa 03.07.2010 | | Autor: | max3000 |
> Was könnt ihr dazu sagen, welche der beiden Lösungen ist
> denn jetzt hier richtig???
Ich finde deine richtig :).
Deine Zweifel die du hier äußerst sind vollkommen berechtigt.
Im Endeffekt muss man ja nur die Vektoren ablesen und dann hat man die Lösung. Wo hast du diese Lösung her? Aus eurem Script? War euer Prof vielleicht besoffen als er das geschrieben hat? Ich glaube in der Lösung wurden [mm] y_1 [/mm] und [mm] y_2 [/mm] vertauscht. Wenn man die beide umbenennt, kommt glaube ich genau das richtige raus.
|
|
|
| |
|
Hi Max,
ja die Lösung habe ich aus der Musterlösung einer älteren Klausur. Habe mich da nur sehr gewundert, deswegen wolle ich es lieber hier nochmal posten.
Ich habe dann aber noch eine andere Frage zu dieser Aufgabe. Denn bei uns in der Übung haben wir mal so eine ähnliche Aufgabe gerechnet. Wenn ich das aber so mache, wie in der Übung, komme ich auf ein anderes Ergebnis. Ich zeig euch mal, wie wir das gemacht haben.
1) Wir machen aus der Maximierungsaufgabe eine Minimierungsaufgabe der Form Minimiere [mm] c^T [/mm] x auf [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] deswegen muss man hier das Vorzeichen wechseln. Also
Minimiere [mm] -x_1 [/mm] unter den NB I. $ [mm] x_2 [/mm] $ - $ [mm] x_1 \ge [/mm] $ 0 II. $ [mm] x_1 [/mm] $ + $ [mm] \bruch{x_2}{2} \le \bruch{1}{2} [/mm] $
2) Aus der Aufgabe bekommen wir keine Information über die Positivität von den [mm] x_i, [/mm] deswegen schreiben wir
[mm] x_1=x_1^+ [/mm] - [mm] x_1^-
[/mm]
[mm] x_2=x_2^+ [/mm] - [mm] x_2^-
[/mm]
[mm] \Rightarrow [/mm] Minimiere [mm] -x_1^+ [/mm] + [mm] x_1^- \gdw [/mm] Minimiere [mm] \vektor{-1 \\ 1 \\ 0\\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^-}
[/mm]
3) Da wir es bei den NB mit Ungleichungen zu tun haben, müssen wir auch noch Schlupfvariablen einführen. Man erhält also:
I. [mm] -x_1^+ [/mm] + [mm] x_1^- [/mm] + [mm] x_2^+ [/mm] - [mm] x_2^- [/mm] - [mm] z_1 [/mm] = 0
II. [mm] x_1^+ [/mm] - [mm] x_1^- [/mm] + [mm] \bruch{1}{2}x_2^+ [/mm] - [mm] \bruch{1}{2}x_2^- [/mm] + [mm] z_2 [/mm] = [mm] \bruch{1}{2}
[/mm]
dabei sind [mm] z_1, z_2 [/mm] natürlich größer gleich Null.
4) Damit erhalten wir jetzt:
Minimiere [mm] \vektor{-1 \\ 1 \\ 0 \\ 0\\ 0 \\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^- \\ z_1 \\ z_2} [/mm]
auf [mm] M:=\{x \in \IR^6, x\ge 0 | Ax=b \}
[/mm]
mit [mm] A=\pmat{ -1 & 1 & 1 & -1 & -1 & 0 \\ 1 & -1 & \bruch{1}{2} & -\bruch{1}{2} & 0 & 1 } [/mm] und [mm] b=\vektor{0\\\bruch{1}{2} }
[/mm]
Also genau so haben wir das bei einem anderen Beispiel in der Übung gemacht. Nur sieht das Ergebnis ja völlig anders aus wie
Minimiere $ [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] $ auf $ [mm] M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\} [/mm] $
Was könnt ihr mir dazu sagen? Stimmen beide Lösungen/ Lösungswege oder ist die zweite Lösung falsch???
Danke für Hilfe.
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:26 Sa 03.07.2010 | | Autor: | max3000 |
> 1) Wir machen aus der Maximierungsaufgabe eine
> Minimierungsaufgabe der Form Minimiere [mm]c^T[/mm] x auf [mm]M:=\{x \in \IR^n, x\ge 0 | Ax=b \},[/mm]
> deswegen muss man hier das Vorzeichen wechseln. Also
>
> Minimiere [mm]-x_1[/mm] unter den NB I. [mm]x_2[/mm] - [mm]x_1 \ge[/mm] 0 II. [mm]x_1[/mm] +
> [mm]\bruch{x_2}{2} \le \bruch{1}{2}[/mm]
>
> 2) Aus der Aufgabe bekommen wir keine Information über die
> Positivität von den [mm]x_i,[/mm] deswegen schreiben wir
>
> [mm]x_1=x_1^+[/mm] - [mm]x_1^-[/mm]
> [mm]x_2=x_2^+[/mm] - [mm]x_2^-[/mm]
>
> [mm]\Rightarrow[/mm] Minimiere [mm]-x_1^+[/mm] + [mm]x_1^- \gdw[/mm] Minimiere
> [mm]\vektor{-1 \\ 1 \\ 0\\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^-}[/mm]
>
> 3) Da wir es bei den NB mit Ungleichungen zu tun haben,
> müssen wir auch noch Schlupfvariablen einführen. Man
> erhält also:
>
> I. [mm]-x_1^+[/mm] + [mm]x_1^-[/mm] + [mm]x_2^+[/mm] - [mm]x_2^-[/mm] - [mm]z_1[/mm] = 0
>
> II. [mm]x_1^+[/mm] - [mm]x_1^-[/mm] + [mm]\bruch{1}{2}x_2^+[/mm] - [mm]\bruch{1}{2}x_2^-[/mm] +
> [mm]z_2[/mm] = [mm]\bruch{1}{2}[/mm]
>
> dabei sind [mm]z_1, z_2[/mm] natürlich größer gleich Null.
>
Hier ist ein kleiner Fehler drin.
Die Nebenbedingung I musst du ja erstmal mit -1 durchmultiplizieren damit sich das Vorzeichen umdreht, also kommt raus:
[mm] x_1-x_2\le0
[/mm]
damit das in der gewünschten Form ist.
Dann die Zerlegung der freien Variablen und Schlupfvariablen eingefügt ergibt:
[mm] x_1^+-x_1^--x_2^++x_2^-+z_1=0
[/mm]
Versuch lieber damit nochmal die komplette Aufgabe durchzurechnen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:27 Sa 03.07.2010 | | Autor: | max3000 |
Oh sorry ich seh grad das ist ja das selbe wie du schon hast nur alle Vorzeichen sind umgedreht. Dann ist dein Schritt doch richtig.
Sonst sehe ich auf anhieb keinen Fehler. Tut mir leid.
Ich schau es mir nochmal genau an
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:30 Sa 03.07.2010 | | Autor: | max3000 |
In deiner Aufgabe sind doch [mm] x_1 [/mm] und [mm] x_2 [/mm] freie (nicht vorzeichenbeschränkte) Variablen. In der Lösung die du postest soll aber [mm] x_1,x_2\ge0 [/mm] sein. Sicher dass das die selbe Aufgabenstellung gewesen ist?
|
|
|
| |
|
Also unsere Aufgabe aus der Übung hieß damals:
Bringe das folgende Optimierungsproblem auf Normalform.
Max [mm] 2x_1 [/mm] + [mm] x_2 [/mm] unter den NB.
I. [mm] x_1 [/mm] + [mm] x_2 \le [/mm] 10
II. [mm] x_1 \ge [/mm] 3
III. [mm] 4x^2 \ge x_1 [/mm] + [mm] x_2
[/mm]
[mm] x_2 \ge [/mm] 0
So und bei dieser Aufgabe sind wir so vorgegangen, wie ich das an dem anderen Beispiel auch probiert habe. In diesem Beispiel war es aber auch noch so, dass ja [mm] x_1 [/mm] und [mm] x_2 \ge [/mm] 0 gegeben sind. Unser Hiwi meinte aber, wenn dies nicht bekannt ist, muss man $ [mm] x_1=x_1^+ [/mm] $ - $ [mm] x_1^- [/mm] $ einführen.
Jetzt weiß ich aber nicht, was richtig und was falsch ist :-/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:22 So 04.07.2010 | | Autor: | max3000 |
Hey.
Also das -1 multiplizieren musst du nicht machen.
Ich hab es halt erst in die Form [mm] ...\le0 [/mm] gebracht und habe dann die Schlupfvariable dazuaddiert, ihr habt es so gelassen und die Schlupfvariable subtrahiert. Kommt ja aufs selbe raus von daher ist das egal.
Die eigentlichen Algorithmen mit denen du dann die Lösung ausrechnest, benutzen ja immer Variablen [mm] \ge0. [/mm] Wenn du aber freie Variablen gegeben hast musst du die Zerlegen in x^+ und x^- von daher ist die Aussage eures Übungsleiters schon richtig.
Leider seh ich mitlerweile auch nicht mehr ganz durch um welche Aufgabe dir es jetzt genau geht. Kannst du bitte nur noch einmal die eigentliche Aufgabe posten/kopieren?
Grüße
Max
|
|
|
| |
|
Hi Max,
ok ich poste jetzt nochmal mein komplettes Problem.
Wir hatten ja folgende Aufgabe:
> Gegeben sei die folgende Opitimierungsaufgabe:
> Maximiere $ [mm] y_1 [/mm] $ unter den NB I. $ [mm] y_2 [/mm] $ - $ [mm] y_1 \ge [/mm] $ 0 II. $ [mm] y_1 [/mm] $ + $ [mm] \bruch{y_2}{2} \le \bruch{1}{2} [/mm] $
> Von welchem "Primal"-Prohlem in Normalform ist dies das Dualproblem?
So, dazu habe ich ja eine Musterlösung gehabt. Die zwar etwas falsch war, aber abgeändert kamen wir dann auf folgendes Ergebnis:
> Das gegebene Problem ist von der Form (D) Max $ [mm] b^T [/mm] $ y auf $ [mm] N:=\{y \in \IR^m |A^Ty\le c \} [/mm] $ mit
> [mm] b^T=(1,0), c=\vektor{0 \\ \bruch{1}{2}} [/mm] und [mm] A^T=\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }
[/mm]
Und damit lautet das Primal-Problem:
Minimiere $ [mm] c^T [/mm] $ x auf $ [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] $ also
Minimiere $ [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] $ auf $ [mm] M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\} [/mm] $
Wie gesagt, das war der Lösungweg von der Musterlösung.
Jetzt war es jedoch so, dass wir bei uns in der Übung mal eine ähnlich Aufgabe gerechnet haben. Wenn ich diese Aufgabe aber jetzt, nach dem Muster rechne, wie wir das in der Übung gemacht haben, dann komme ich auf folgendes:
> 1) Wir machen aus der Maximierungsaufgabe eine Minimierungsaufgabe der Form Minimiere $ [mm] c^T [/mm] $ x auf $ [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] $ deswegen muss man hier das Vorzeichen wechseln. Also
> Minimiere $ [mm] -x_1 [/mm] $ unter den NB I. $ [mm] x_2 [/mm] $ - $ [mm] x_1 \ge [/mm] $ 0 II. $ [mm] x_1 [/mm] $ + $ [mm] \bruch{x_2}{2} \le \bruch{1}{2} [/mm] $
> 2) Aus der Aufgabe bekommen wir keine Information über die Positivität von den $ [mm] x_i, [/mm] $ deswegen schreiben wir
> $ [mm] x_1=x_1^+ [/mm] $ - $ [mm] x_1^- [/mm] $
> $ [mm] x_2=x_2^+ [/mm] $ - $ [mm] x_2^- [/mm] $
> $ [mm] \Rightarrow [/mm] $ Minimiere $ [mm] -x_1^+ [/mm] $ + $ [mm] x_1^- \gdw [/mm] $ Minimiere $ [mm] \vektor{-1 \\ 1 \\ 0\\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^-} [/mm] $
> 3) Da wir es bei den NB mit Ungleichungen zu tun haben, müssen wir auch noch Schlupfvariablen einführen. Man erhält also:
> I. $ [mm] -x_1^+ [/mm] $ + $ [mm] x_1^- [/mm] $ + $ [mm] x_2^+ [/mm] $ - $ [mm] x_2^- [/mm] $ - $ [mm] z_1 [/mm] $ = 0
> II. $ [mm] x_1^+ [/mm] $ - $ [mm] x_1^- [/mm] $ + $ [mm] \bruch{1}{2}x_2^+ [/mm] $ - $ [mm] \bruch{1}{2}x_2^- [/mm] $ + $ [mm] z_2 [/mm] $ = $ [mm] \bruch{1}{2} [/mm] $
> dabei sind $ [mm] z_1, z_2 [/mm] $ natürlich größer gleich Null.
> 4) Damit erhalten wir jetzt:
> Minimiere $ [mm] \vektor{-1 \\ 1 \\ 0 \\ 0\\ 0 \\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^- \\ z_1 \\ z_2} [/mm] $
> auf $ [mm] M:=\{x \in \IR^6, x\ge 0 | Ax=b \} [/mm] $
> mit $ [mm] A=\pmat{ -1 & 1 & 1 & -1 & -1 & 0 \\ 1 & -1 & \bruch{1}{2} & -\bruch{1}{2} & 0 & 1 } [/mm] $ und $ [mm] b=\vektor{0\\\bruch{1}{2} } [/mm] $
Was mich jetzt aber irritiert ist, dass wir ja jetzt zwei verschiedene Ergebnisse erhalten. Einmal das nach der Musterlösung, und das nach dem Muster aus der Übung.
Meine Frage ist, welcher Lösungsweg ist richtig? Oder sind beide richtig? Wenn irgendwo was falsch ist, wo steckt der Fehler??
Hoffe du kannst mir bei diesen Fragen helfen.
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:34 So 04.07.2010 | | Autor: | max3000 |
> Hi Max,
>
> ok ich poste jetzt nochmal mein komplettes Problem.
>
> Wir hatten ja folgende Aufgabe:
>
> > Gegeben sei die folgende Opitimierungsaufgabe:
>
> > Maximiere [mm]y_1[/mm] unter den NB I. [mm]y_2[/mm] - [mm]y_1 \ge[/mm] 0 II. [mm]y_1[/mm] +
> [mm]\bruch{y_2}{2} \le \bruch{1}{2}[/mm]
>
> > Von welchem "Primal"-Prohlem in Normalform ist dies das
> Dualproblem?
>
> So, dazu habe ich ja eine Musterlösung gehabt. Die zwar
> etwas falsch war, aber abgeändert kamen wir dann auf
> folgendes Ergebnis:
>
> > Das gegebene Problem ist von der Form (D) Max [mm]b^T[/mm] y auf
> [mm]N:=\{y \in \IR^m |A^Ty\le c \}[/mm] mit
>
> > [mm]b^T=(1,0), c=\vektor{0 \\ \bruch{1}{2}}[/mm] und [mm]A^T=\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }[/mm]
Das ist nicht ganz richtig.
Du hast die Nebenbedingung [mm] -y_1+y_2\ge0 [/mm] und auf Normalform gebracht lautet die dann:
[mm] y_1-y_2\le0 [/mm] und damit ist deine matrix
[mm] A^T=\pmat{1 & -1 \\ 1 & 1/2}
[/mm]
> Und damit lautet das Primal-Problem:
>
> Minimiere [mm]c^T[/mm] x auf [mm]M:=\{x \in \IR^n, x\ge 0 | Ax=b \},[/mm]
> also
>
> Minimiere [mm](0,\bruch{1}{2})\vektor{x_1 \\ x_2}[/mm] auf [mm]M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ -1 & 1 \\ 1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\}[/mm]
>
Beachte hier noch dass du als Nebenbedingung die Koeffizientenmatrix A und nicht [mm] A^T [/mm] hast, also musst du die, die wir oben ausgerechnet haben noch transponieren.
>
> Wie gesagt, das war der Lösungweg von der Musterlösung.
>
> Jetzt war es jedoch so, dass wir bei uns in der Übung mal
> eine ähnlich Aufgabe gerechnet haben. Wenn ich diese
> Aufgabe aber jetzt, nach dem Muster rechne, wie wir das in
> der Übung gemacht haben, dann komme ich auf folgendes:
>
> > 1) Wir machen aus der Maximierungsaufgabe eine
> Minimierungsaufgabe der Form Minimiere [mm]c^T[/mm] x auf [mm]M:=\{x \in \IR^n, x\ge 0 | Ax=b \},[/mm]
> deswegen muss man hier das Vorzeichen wechseln. Also
>
> > Minimiere [mm]-x_1[/mm] unter den NB I. [mm]x_2[/mm] - [mm]x_1 \ge[/mm] 0 II. [mm]x_1[/mm] +
> [mm]\bruch{x_2}{2} \le \bruch{1}{2}[/mm]
>
> > 2) Aus der Aufgabe bekommen wir keine Information über die
> Positivität von den [mm]x_i,[/mm] deswegen schreiben wir
>
> > [mm]x_1=x_1^+[/mm] - [mm]x_1^-[/mm]
> > [mm]x_2=x_2^+[/mm] - [mm]x_2^-[/mm]
>
> > [mm]\Rightarrow[/mm] Minimiere [mm]-x_1^+[/mm] + [mm]x_1^- \gdw[/mm] Minimiere
> [mm]\vektor{-1 \\ 1 \\ 0\\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^-}[/mm]
>
> > 3) Da wir es bei den NB mit Ungleichungen zu tun haben,
> müssen wir auch noch Schlupfvariablen einführen. Man
> erhält also:
>
> > I. [mm]-x_1^+[/mm] + [mm]x_1^-[/mm] + [mm]x_2^+[/mm] - [mm]x_2^-[/mm] - [mm]z_1[/mm] = 0
>
> > II. [mm]x_1^+[/mm] - [mm]x_1^-[/mm] + [mm]\bruch{1}{2}x_2^+[/mm] - [mm]\bruch{1}{2}x_2^-[/mm] +
> [mm]z_2[/mm] = [mm]\bruch{1}{2}[/mm]
>
> > dabei sind [mm]z_1, z_2[/mm] natürlich größer gleich Null.
>
> > 4) Damit erhalten wir jetzt:
>
> > Minimiere [mm]\vektor{-1 \\ 1 \\ 0 \\ 0\\ 0 \\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^- \\ z_1 \\ z_2}[/mm]
>
> > auf [mm]M:=\{x \in \IR^6, x\ge 0 | Ax=b \}[/mm]
>
> > mit [mm]A=\pmat{ -1 & 1 & 1 & -1 & -1 & 0 \\ 1 & -1 & \bruch{1}{2} & -\bruch{1}{2} & 0 & 1 }[/mm]
> und [mm]b=\vektor{0\\\bruch{1}{2} }[/mm]
>
>
> Was mich jetzt aber irritiert ist, dass wir ja jetzt zwei
> verschiedene Ergebnisse erhalten. Einmal das nach der
> Musterlösung, und das nach dem Muster aus der Übung.
>
> Meine Frage ist, welcher Lösungsweg ist richtig? Oder sind
> beide richtig? Wenn irgendwo was falsch ist, wo steckt der
> Fehler??
Also ich würde sagen beide sind richtig.
Das sind 2 unterschiedliche Aufgaben.
In der Aufgabe ganz oben suchst du halt das primale Problem. Und es gilt ja, dass Variablen, die im primalen Problem Vorzeichenbeschränkt sind, sind beim dualen frei.
Die zweite Aufgabe hat ja eigentlich nix mit Dualität zu tun. Hier musst du ja nur umformen bis du das auf Normalform gebracht hast. Und dann könntest du das ganze eventuell noch in die duale Form überführen.
Also ich sehe gerade dass du oben bei dem Übergang zum primalen Problem vergessen hast zu sagen, dass [mm] y_i\ge0 [/mm] sind.
Also wie gesagt: ich denke dass das 2 komplett verschiedene Sachen sind. !. Übergang vom dualen zum primalen Problem und 2. die Umforumng in ein Problem in Normalform.
> Hoffe du kannst mir bei diesen Fragen helfen.
>
> Grüße
|
|
|
| |
|
HI Max nochmal,
> Also wie gesagt: ich denke dass das 2 komplett verschiedene Sachen sind. !. Übergang vom dualen zum primalen Problem und 2. die Umforumng in ein Problem in Normalform.
Ich glaube, dann habe ich zur Zeit einen kleinen Denkfehler. Denn ich dachte, dass das Primale Problem, was in der ersten Lösung angegeben wird (also nicht die Variante aus der Übung). Ich schreibe es lieber nochmal auf:
> Minimiere $ [mm] c^T [/mm] $ x auf $ [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] $
> also
> Minimiere $ [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] $ auf $ [mm] M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ 1 & 1 \\ -1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\} [/mm] $
Ich dachte das ist das selbe wie das, was wir auch in der Übung gemacht haben.
Denn in beiden Lösungen haben wir ja die Aufgabe auf die Form Minimiere [mm] c^T [/mm] x auf [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}
[/mm]
gebracht.
Wo steckt denn jetzt der Unterschied zwischen den beiden Minimierungsproblemen, die wir herausbekommen haben?
Also zwischen
> Minimiere $ [mm] c^T [/mm] $ x auf $ [mm] M:=\{x \in \IR^n, x\ge 0 | Ax=b \}, [/mm] $
> also
> Minimiere $ [mm] (0,\bruch{1}{2})\vektor{x_1 \\ x_2} [/mm] $ auf $ [mm] M:=\{x \in \IR^2 , x_1, x_2 \ge 0|\pmat{ 1 & 1 \\ -1 & \bruch{1}{2} }\vektor{x_1 \\ x_2 }= \vektor{1 \\ 0 }\} [/mm] $
und
> Minimiere $ [mm] \vektor{-1 \\ 1 \\ 0 \\ 0\\ 0 \\ 0}^T \vektor{x_1^+ \\ x_1^- \\ x_2^+ \\ x_2^- \\ z_1 \\ z_2} [/mm] $
> auf $ [mm] M:=\{x \in \IR^6, x\ge 0 | Ax=b \} [/mm] $
> mit $ [mm] A=\pmat{ -1 & 1 & 1 & -1 & -1 & 0 \\ 1 & -1 & \bruch{1}{2} & -\bruch{1}{2} & 0 & 1 } [/mm] $
> und $ [mm] b=\vektor{0\\\bruch{1}{2} } [/mm] $
Die sind doch jetzt beide in Normalform, oder nicht?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:21 Mo 12.07.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Also bei uns in der Übung haben wir damals die NB NICHT mit (-1) multipliziert. heißt das, wir haben dort einen Fehler gemacht??
Und muss ich nur die I. NB mit (-1) multiplizieren oder auch die II.??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:35 So 04.07.2010 | | Autor: | max3000 |
Nein du hast das schon richtig gemacht. Wenn du [mm] \ge0 [/mm] dastehen hast, musst du die Schlupfvariable abziehen, so wie du es gemacht hast. Wenn [mm] \le0 [/mm] dasteht (das würde es nachdem du mit -1 multiplizierst) addierst du die Schlupfvariable eben nur dazu.
|
|
|
|
