Duales Problem < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben ist das lineare Programm P mit
Minimiere f(x):= [mm] 6x_{1} [/mm] + [mm] 3x_{3}
[/mm]
unter den Nebenbedingungen:
[mm] 2x_{1} [/mm] - [mm] x_{2} [/mm] + [mm] x_{3} [/mm] =-1
[mm] x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] 2x_{3}=2
[/mm]
[mm] x_{1}, x_{2}, x_{3} \ge [/mm] 0
a) Stellen sie das duale Problem dazu auf und bestimmen sie dessen Lösung y* mit Hilfe einer Zeichnung. |
Hallo
ich habe ein problem mit der obrigen Aufgabe und zwar habe ich bereits die Lösungen der Aufgabe kann damit jedoch leider nicht viel anfangen.
das duale Problem lautet:
Maximiere [mm] f_{D}(y)=-1y_{1}+2y_{2}
[/mm]
unter den Nebindungen
[mm] 2y_{1}+y_{2} \le [/mm] 6
[mm] -1y_{1} +y_{2} \le [/mm] 0
[mm] y_{1} +2y_{2} \le [/mm] 3
[mm] y_{1},y_{2} \ge [/mm] 0
mit hilfe einer Zeichnung habe ich raus gefunden, dass das Maximum bei dem P (3/0) liegt [mm] f_{D}(y) [/mm] also somit -3 ist.
Nun wurde in der Lösung y* wie folgt berechnet:
[mm] \pmat{ -1 & 1 \\ 1 & 2 } \vektor{y_{1} \\ y_{2}}=\vektor{0 \\ 3} [/mm] und daraus folgt [mm] y\*=\vektor{1 \\ 1}
[/mm]
Meine Frage nun wie kommt man auf die Rechnung das verstehe ich leider nicht ganz.
Kann mir da bitte jemand helfen?
LG Schmetterfee
|
|
| |
|
> Gegeben ist das lineare Programm P mit
> Minimiere f(x):= [mm]6x_{1}[/mm] + [mm]3x_{3}[/mm]
> unter den Nebenbedingungen:
> [mm]2x_{1}[/mm] - [mm]x_{2}[/mm] + [mm]x_{3}[/mm] =-1
> [mm]x_{1}[/mm] + [mm]x_{2}[/mm] + [mm]2x_{3}=2[/mm]
> [mm]x_{1}, x_{2}, x_{3} \ge[/mm] 0
>
> a) Stellen sie das duale Problem dazu auf und bestimmen sie
> dessen Lösung y* mit Hilfe einer Zeichnung.
> Hallo
Hallo,
>
> ich habe ein problem mit der obrigen Aufgabe und zwar habe
> ich bereits die Lösungen der Aufgabe kann damit jedoch
> leider nicht viel anfangen.
>
> das duale Problem lautet:
> Maximiere [mm]f_{D}(y)=-1y_{1}+2y_{2}[/mm]
> unter den Nebindungen
> [mm]2y_{1}+y_{2} \le[/mm] 6
> [mm]-1y_{1} +y_{2} \le[/mm] 0
> [mm]y_{1} +2y_{2} \le[/mm] 3
> [mm]y_{1},y_{2} \ge[/mm] 0
>
> mit hilfe einer Zeichnung habe ich raus gefunden, dass das
> Maximum bei dem P (3/0) liegt [mm]f_{D}(y)[/mm] also somit -3 ist.
> Nun wurde in der Lösung y* wie folgt berechnet:
> [mm]\pmat{ -1 & 1 \\ 1 & 2 } \vektor{y_{1} \\ y_{2}}=\vektor{0 \\ 3}[/mm]
> und daraus folgt [mm]y\*=\vektor{1 \\ 1}[/mm]
> Meine Frage nun wie
> kommt man auf die Rechnung das verstehe ich leider nicht
> ganz.
>
Dies sind die beiden Ungleichungen, die in der Ecke, in der das Max angenommen wird, als Gleichung erfüllt sind.
Dann hast du einfach ein Gleichungssystem mit 2 Gleichungen und 2 Unbekannten. Damit kann y* berechnet werden (Gauß o.ä.).
Gruß Patrick
> Kann mir da bitte jemand helfen?
>
> LG Schmetterfee
|
|
|
| |
|
> > Gegeben ist das lineare Programm P mit
> > Minimiere f(x):= [mm]6x_{1}[/mm] + [mm]3x_{3}[/mm]
> > unter den Nebenbedingungen:
> > [mm]2x_{1}[/mm] - [mm]x_{2}[/mm] + [mm]x_{3}[/mm] =-1
> > [mm]x_{1}[/mm] + [mm]x_{2}[/mm] + [mm]2x_{3}=2[/mm]
> > [mm]x_{1}, x_{2}, x_{3} \ge[/mm] 0
> >
> > a) Stellen sie das duale Problem dazu auf und bestimmen sie
> > dessen Lösung y* mit Hilfe einer Zeichnung.
> > Hallo
>
> Hallo,
>
> >
> > ich habe ein problem mit der obrigen Aufgabe und zwar habe
> > ich bereits die Lösungen der Aufgabe kann damit jedoch
> > leider nicht viel anfangen.
> >
> > das duale Problem lautet:
> > Maximiere [mm]f_{D}(y)=-1y_{1}+2y_{2}[/mm]
> > unter den Nebindungen
> > [mm]2y_{1}+y_{2} \le[/mm] 6
> > [mm]-1y_{1} +y_{2} \le[/mm] 0
> > [mm]y_{1} +2y_{2} \le[/mm] 3
> > [mm]y_{1},y_{2} \ge[/mm] 0
> >
> > mit hilfe einer Zeichnung habe ich raus gefunden, dass das
> > Maximum bei dem P (3/0) liegt [mm]f_{D}(y)[/mm] also somit -3 ist.
> > Nun wurde in der Lösung y* wie folgt berechnet:
> > [mm]\pmat{ -1 & 1 \\ 1 & 2 } \vektor{y_{1} \\ y_{2}}=\vektor{0 \\ 3}[/mm]
> > und daraus folgt [mm]y\*=\vektor{1 \\ 1}[/mm]
> > Meine Frage nun
> wie
> > kommt man auf die Rechnung das verstehe ich leider nicht
> > ganz.
> >
>
> Dies sind die beiden Ungleichungen, die in der Ecke, in der
> das Max angenommen wird, als Gleichung erfüllt sind.
> Dann hast du einfach ein Gleichungssystem mit 2 Gleichungen
> und 2 Unbekannten. Damit kann y* berechnet werden (Gauß
> o.ä.).
>
> Gruß Patrick
>
Danke für deine Antwort...das habe ich in meiner Zeichnung auch gesehen aber die Ungleichung 1 ist doch auch erfüllt...warum wurde denn mit dieser nicht gerechnet?..oder ist das egal welche ich nehme?
LG Schmetterfee
> > Kann mir da bitte jemand helfen?
> >
> > LG Schmetterfee
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:09 Mo 27.09.2010 | | Autor: | Sigma |
Hallo Schmetterfee,
nein es ist nicht egal welche Ungleichungen du nimmst. Dann wäre die Lösung einer linearen Optimierungsaufgabe ja einfach. Ich nehme irgendwelche Nebenbedingungen und schaue ob diese erfüllt sind. Klar kann es möglich sein eine zulässige Anfangslösung finden.Es kann aber auch passieren, das man komplett daneben liegt.(unzulässige Lösung) Die Idee des SimplexAlgorithmus sucht aber die Ecken des konvexen Polyeders ab und sucht dort die Optimallösung. Deine Lösung P(3,0) liegt zwar an einer der Ecken des Konvexen Polyeders. Aber leider ist sie nicht die Optimallösung. Verschiebe die Zielfunktion parallel zu X Achse und du wirst die richtige Lösung finden. Und zeichne dir zuvor die konvexe Menge des Lösungsraums.
mfg sigma
|
|
|
| |
|
> Hallo Schmetterfee,
>
> nein es ist nicht egal welche Ungleichungen du nimmst. Dann
> wäre die Lösung einer linearen Optimierungsaufgabe ja
> einfach. Ich nehme irgendwelche Nebenbedingungen und schaue
> ob diese erfüllt sind. Klar kann es möglich sein eine
> zulässige Anfangslösung finden.Es kann aber auch
> passieren, das man komplett daneben liegt.(unzulässige
> Lösung) Die Idee des SimplexAlgorithmus sucht aber die
> Ecken des konvexen Polyeders ab und sucht dort die
> Optimallösung. Deine Lösung P(3,0) liegt zwar an einer
> der Ecken des Konvexen Polyeders. Aber leider ist sie nicht
> die Optimallösung. Verschiebe die Zielfunktion parallel zu
> X Achse und du wirst die richtige Lösung finden. Und
> zeichne dir zuvor die konvexe Menge des Lösungsraums.
>
> mfg sigma
Hallo
danke schön..dein hinweis hat meinen Fehler erkennbar gemacht. Die 2. Nebenbedingung war in meiner Zeichnung nicht richtig eingezeichnet und lieferte somit nur den P (0/3)...
Ich habe nur noch eine inhaltliche Frage und zwar habe ich mir aufgeschrieben, dass f(y)=-3 ist aber das muss doch ein Schreibfehler sein denn wenn ich den Punkt (1/1) einsetze erhalte ich ja das ergebnis f(y)=3 auf -3 würde ich ja nur kommen wenn ich das Minimierungsproblem lösen würde. würden sich dadurch auch die Nebenbedingungen ändern oder würden die äquivalent bleiben und nur die zielfunktion würde ihre Vorzeichen ändern?
Oder steht da einfach -3 weil bei dualen problemen ja überlicherweise das Minimierungsproblem untersucht wird?
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Fr 01.10.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
