Ellipsoidmethode < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben das durch das Ungleichungssystem
2x+y+2z [mm] \le [/mm] 100
x+y+z [mm] \ge [/mm] 10
x,y,z [mm] \ge [/mm] 0
gegebene Polyeder P. Ihnen steht ein Computer zur Verfügung, der die Ellipsoidmethode beherrscht. Als einzige Eingabe benötigt der Rechner ein zulässiges Startellipsoid [mm] E_0:= [/mm] B(0,r). Bestimmen Sie einen Radius r so, dass die Ellipsoidmethode einen Punkt x [mm] \in [/mm] P mittels des Startellipsoids [mm] E_0 [/mm] findet und schätzen sie die dafür benötigte Anzahl der Iterationen der Ellipsoidmethode ab. |
Hallo zusammen,
beschäftige mich grade mit dieser aufgabe aber ich hab noch echte Probleme mit dieser Ellipsoidmethode.
Also zunächst hab ich ja folgendes Ungleichungssystem:
2x+y+2z [mm] \le [/mm] 100
x+y+z [mm] \ge [/mm] 10
x,y,z [mm] \ge [/mm] 0
dies hab ich dann umgeschrieben, damit ich die form Ax [mm] \le [/mm] b erhalte
2x+y+2z [mm] \le [/mm] 100
-(x+y+z) [mm] \le [/mm] 10
x,y,z [mm] \ge [/mm] 0
daraus erhalte ich ja jetzt mein Polyeder P mit P=P(A,b)
A:= [mm] \pmat{ 2 & 1 & 2 \\ -1 & -1 & -1 } [/mm] b:= [mm] \vektor{100 \\ -10}
[/mm]
aber wie kann ich jetzt einen Radius bestimmen?
kann mir da jemand einen tipp geben?
danke schonmal!
gruß,
kekschen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:52 Sa 18.06.2011 | | Autor: | meili |
Hallo kekschen,
> Gegeben das durch das Ungleichungssystem
> 2x+y+2z [mm]\le[/mm] 100
> x+y+z [mm]\ge[/mm] 10
> x,y,z [mm]\ge[/mm] 0
> gegebene Polyeder P. Ihnen steht ein Computer zur
> Verfügung, der die Ellipsoidmethode beherrscht. Als
> einzige Eingabe benötigt der Rechner ein zulässiges
> Startellipsoid [mm]E_0:=[/mm] B(0,r). Bestimmen Sie einen Radius r
> so, dass die Ellipsoidmethode einen Punkt x [mm]\in[/mm] P mittels
> des Startellipsoids [mm]E_0[/mm] findet und schätzen sie die dafür
> benötigte Anzahl der Iterationen der Ellipsoidmethode ab.
> Hallo zusammen,
>
> beschäftige mich grade mit dieser aufgabe aber ich hab
> noch echte Probleme mit dieser Ellipsoidmethode.
>
> Also zunächst hab ich ja folgendes Ungleichungssystem:
> 2x+y+2z [mm]\le[/mm] 100
> x+y+z [mm]\ge[/mm] 10
> x,y,z [mm]\ge[/mm] 0
> dies hab ich dann umgeschrieben, damit ich die form Ax [mm]\le[/mm]
> b erhalte
>
> 2x+y+2z [mm]\le[/mm] 100
> -(x+y+z) [mm]\le[/mm] -10
> x,y,z [mm]\ge[/mm] 0
>
> daraus erhalte ich ja jetzt mein Polyeder P mit P=P(A,b)
> A:= [mm]\pmat{ 2 & 1 & 2 \\ -1 & -1 & -1 }[/mm] b:= [mm]\vektor{100 \\ -10}[/mm]
>
> aber wie kann ich jetzt einen Radius bestimmen?
> kann mir da jemand einen tipp geben?
> danke schonmal!
Mit r = 100 ist $P [mm] \subset [/mm] B(0, 100)$, da $z = (0, 0, 0)$ (Mittelpunkt von
$B(0, 100)$). EDIT: $z [mm] \in [/mm] P$ (wegen $A * z [mm] \le [/mm] b$) reicht ein Iterationsschritt.
Die Anzahl der Iterationsschritte ist weiterhin offen.
Tut mir sehr leid, die Bedingung x+y+z [mm] $\le$ [/mm] 10 habe ich nicht richtig berücksichtigt.
Danke für die Fehlermeldung!
>
> gruß,
> kekschen
Gruß
meili
|
|
|
| |
|
| Status: |
(Korrektur) fundamentaler Fehler  | | Datum: | 21:54 So 19.06.2011 | | Autor: | reginalex |
Der Mittelpunkt erfüllt hier aber nicht die Bedingung x+y+z [mm] \ge [/mm] 10.
Ein Iterationsschritt wird also nicht reichen...
Ich wüsste die Lösung auch gerne, aber die hier kann ja nicht richtig sein.
Gruß
Alex
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:18 Mo 20.06.2011 | | Autor: | meili |
Die Anzahl der Iterationsschritte ist weiterhin offen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Do 23.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
