Ellipsoidmethode

19.01.2010, 23:33

flara

Ellipsoidmethode

HALLO,

ich folgende Aufgabe zu lösen, habe zwar den Algorithmus der Ellipsoidmethode gelesen, aber trotzdem verstehe ich nicht wie ich überhaupt anfangen soll.
Wäre nett, wenn jemand mir helfen würde; zumindest ein Einsatz geben würde.

Danke euch

Gegeben sei das Polyeder $\begin{eqnarray*} P:= \left\{ x\in \mathbb R^{2}| x_{1}+x_{2}\geq 1, x_{1},x_{2}\leq 1 \right\} \end{eqnarray*}$ . Überprüfen Sie für dieses Polyeder mit Algrithmus der Ellipsoidmethode per Hand, ob P einen zulässigen Punkt $\begin{eqnarray*} x^{*} \in \mathbb Q^{2} \end{eqnarray*}$ besitzt.
Hinweis: Verwenden Sie einen anfangsradius von $\begin{eqnarray*} R = \sqrt{2} \end{eqnarray*}$

edit(Abakus): Latex

23.01.2010, 00:47

Abakus

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode
Hallo!

Wie ist das Vorgehen in dieser Methode bzw. was wären die ersten Schritte, die du machen müsstest?

Grüße Abakus smile

24.01.2010, 22:51

flara

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode
$\begin{eqnarray*} Hallo, Die Ellipsoidmethode Input: A \in \mathbb Q^{m\timesn} und b \in \mathbb Q^{m}. Output: Ein Punkt x^{&#8727;} \in \mathbb Q^{n} mit Ax\leq b oder die Feststellung, dass die Menge \left\{x\in \mathbb R^{n}: Ax Schritt 1: Initialisierung Setze R := \sqrt{n}2^2<A>+-2n^{2} oder kleiner, wenn Vorinformation vorhanden. Setze A_{0}:= R^{2}I a_{0}:= 0 k_{0}:= 0 N := 2n ((3n+1)<A>+(2n+1)-n^{3}). \end{eqnarray*}$

Schritt 2: Abbruchkriterium
(2a) Gilt k = N , dann STOP: Ax < b hat keine Lösung.
(2b) Gilt A_{a_{k}} \leq b , dann STOP: der Punkt
x^{∗}= a_{k} ist gefunden.
(2c) Anderenfalls sei c^{T} eine Zeile von A derart, dass der Mittelpunkt a_{k} von \epsilon_{k} die entsprechende Ungleihung verletzt.

Schritt 3: Update
(3a) Setze
d := \frac{1}{\sqrt{c^{T}A__{k}c}}A_{k}c,
a_{k+1} := a_{k}−\frac{1}{n+1}d
A_{k+1} := \frac{n^{2}}{n^{2}-1}\left( A_{k}-\frac{2}{n+1}dd^{T}\right),
\epsilon_{k+1} :=\epsilon\left(A_{k+1},a_{k+1}\right) ist das neue Ellipsoid.)
(3b) Setze k ← k + 1 und gehe zu Schritt 2.[/latex]

25.01.2010, 00:32

flara

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode
Hallo und sorry für das unverständliche Post.

ich versuche mal zuerst den Datei anzuhängen, damit ihr euch das ansieht.
Mein Problem ist eigentlich: wie bekomme ich die Zielfunktion?
Hier schon mal der Datei mit dem Algorithmus und ein Beispiel attach]13139[/attach]

Nur verstehe ich nicht wie aus $\begin{eqnarray*} P:= \left\{ x\in \mathbb R^{2} | x_{1}+x_{2} \geq1, x_{1},x_{2} \leq1 \right\} \end{eqnarray*}$ ich die Zielfunktion bestimmen soll und außerdem im Vorlesung stand noch

$\begin{eqnarray*} \begin{pmatrix} -1 & 0 \\ 1 & 0 \\ -0 & -1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix}x_{1} \\ x_{2}\end{pmatrix} \leq \begin{pmatrix} \frac{-17}{20} \\ \frac{18}{20}\\ \frac{1}{5}\\ \frac{1}{5} \end{pmatrix} \end{eqnarray*}$

Wie kommt man auf die Einträge der linke Matrix? und in meinen Fall wie kann ich auch auf solche eine Ungleichung kommen?
--------------------------------------------------------------------------------------------------------------------
Was ich mir ausgedacht habe:
$\begin{eqnarray*} R= \sqrt{2} \end{eqnarray*}$ , somit zu

1.Schritt:
$\begin{eqnarray*} A_{0}=\sqrt{2}\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$ (wobei die Dimension= 2, wegen $\begin{eqnarray*} x_{1} \end{eqnarray*}$ und $\begin{eqnarray*} x_{2} \end{eqnarray*}$ )
$\begin{eqnarray*} a_{0}= \begin{pmatrix} 0 \\ 0 \end{pmatrix}, mit \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 &-1 \end{pmatrix}\begin{pmatrix}x_{1} \\ x_{2}\end{pmatrix} \leq \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \end{eqnarray*}$

2:Schritt:
$\begin{eqnarray*} c=\left( 1, 1\right)^{T} \end{eqnarray*}$

bin ich überhaupt auf den richtigen Weg?

Danke für jede Hilfe

25.01.2010, 23:58

Abakus

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode

Zitat:

Original von flara
... und außerdem im Vorlesung stand noch

$\begin{eqnarray*} \begin{pmatrix} -1 & 0 \\ 1 & 0 \\ -0 & -1 \\ 0 & 1 \end{pmatrix}\begin{pmatrix}x_{1} \\ x_{2}\end{pmatrix} \leq \begin{pmatrix} \frac{-17}{20} \\ \frac{18}{20}\\ \frac{1}{5}\\ \frac{1}{5} \end{pmatrix} \end{eqnarray*}$

Wie kommt man auf die Einträge der linke Matrix? und in meinen Fall wie kann ich auch auf solche eine Ungleichung kommen?

Das bezieht sich auf Beispiel 6.18 unter der Methode dann. Das ist was anderes als unsere Aufgabe oben.

Zitat:

Was ich mir ausgedacht habe:
$\begin{eqnarray*} R= \sqrt{2} \end{eqnarray*}$ , somit zu

Ja. Ich würde zunächst noch A und b hinschreiben:

$\begin{eqnarray*} A = \begin{pmatrix} -1 & -1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix},~b= \begin{pmatrix} -1 \\ 1 \\ 1 \end{pmatrix} \end{eqnarray*}$

Damit sollte man jetzt das N berechnen können, was sollen hier die Klammern um A bzw. b bedeuten?

Zitat:

1.Schritt:
$\begin{eqnarray*} A_{0}=\sqrt{2}\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$ (wobei die Dimension= 2, wegen $\begin{eqnarray*} x_{1} \end{eqnarray*}$ und $\begin{eqnarray*} x_{2} \end{eqnarray*}$ )
$\begin{eqnarray*} a_{0}= \begin{pmatrix} 0 \\ 0 \end{pmatrix} \end{eqnarray*}$

Die Wurzel ist hier noch quadriert, also:

$\begin{eqnarray*} A_{0} = 2 \cdot \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \end{eqnarray*}$

Das definiert jetzt mit dem $\begin{eqnarray*} a_0 \end{eqnarray*}$ als Mittelpunkt zusammen einen Kreis mit dem Radius $\begin{eqnarray*} \sqrt{2} \end{eqnarray*}$ , denke ich? In diesem Kreis liegt das gesamte hier betrachtete Simplex.

Zitat:

2:Schritt:
$\begin{eqnarray*} c=\left( 1, 1\right)^{T} \end{eqnarray*}$

bin ich überhaupt auf den richtigen Weg?

Jetzt ist die erste Ungleichung verletzt, denke ich, also $\begin{eqnarray*} c=\left( -1, -1\right)^{T} \end{eqnarray*}$ .

Weiter müsstest du jetzt das n ermitteln und herausfinden, was diese Klammern weiter oben bedeuten sollen. Dann die nächsten Schritte.

Grüße Abakus smile

26.01.2010, 12:15

flara

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode
Danke schon mal für deine Hinweise,
eine Frage hätte ich noch, und zwar warum steht die -1 in der Matrix A und b? wegen $\begin{eqnarray*} x_{1}+ x_{2} \geq 1 \end{eqnarray*}$ oder?

und was meinst du mit was sollen hier die Klammern um A bzw. b bedeuten?

Grüße

26.01.2010, 19:35

Abakus

Auf diesen Beitrag antworten »

RE: Ellipsoidmethode

Zitat:

Original von flara
Danke schon mal für deine Hinweise,
eine Frage hätte ich noch, und zwar warum steht die -1 in der Matrix A und b? wegen $\begin{eqnarray*} x_{1}+ x_{2} \geq 1 \end{eqnarray*}$ oder?

Ja, du brauchst ja eine Restriktion vom Typ " $\begin{eqnarray*} \le \end{eqnarray*}$ ", daher ist die Ungleichung mit -1 zu multiplizieren: dabei dreht sich das Größer-Gleich zu einem Kleiner-Gleich um.

Zitat:

und was meinst du mit was sollen hier die Klammern um A bzw. b bedeuten?

Um A und b stehen bei der Formel zur Berechnung von N ja Klammern. Was bedeuten die? Es kann ja nicht gemeint sein, die Matrix einzusetzen, denn N soll ja eine positive, ganze Zahl sein.

Grüße Abakus smile

26.01.2010, 20:30

flara

Auf diesen Beitrag antworten »

Ellipsoidmethode
ja stimmt du hast recht, aber es ist tatsächlich so, dass man A dann einsetzen muss.
Ich habe endlich hingekriegt.

Danke für deine Hilfe.

Flara Freude

Neue Frage »

Antworten »

Ellipsoidmethode

Verwandte Themen