Äquivalenz zwischen Extrempunkt und zulässige Basislösung bei LP's

24.10.2009, 13:45	Sabinee	Auf diesen Beitrag antworten »
Äquivalenz zwischen Extrempunkt und zulässige Basislösung bei LP's Die Aufgabe lautet: Betrachten Sie ein lineares Programm (LP) in Standardform: $\begin{eqnarray} \{\min cx, \text{ s.d. } Ax=b,x\geq 0\} \end{eqnarray}$ . Zeigen Sie, dass folgende Aussagen äquivalent sind: (a) $\begin{eqnarray} \tilde x \end{eqnarray}$ ist zulässige Basislösung von $\begin{eqnarray} (LP) \end{eqnarray}$ (b) $\begin{eqnarray} \tilde x \end{eqnarray}$ ist Extrempunkt von $\begin{eqnarray} P:=\{x\in \mathbb R^n: Ax=b, x\geq 0\} \end{eqnarray}$ Hinweis: Benutzen Sie für ihren Beweis eine der beiden folgenden Definitionen eines Extrempunktes: Defintion 1. Ein Punkt $\begin{eqnarray} x\in P \end{eqnarray}$ heißt Extrempunkt von $\begin{eqnarray} P \end{eqnarray}$ genau dann, wenn er auf $\begin{eqnarray} n \end{eqnarray}$ linear unabhängigen das Polyeder beschreibenden Hyperebenen liegt. Definition 2. Ein Punkt $\begin{eqnarray} x\in P \end{eqnarray}$ heißt Extrempunkt von $\begin{eqnarray} P \end{eqnarray}$ genau dann, wenn aus $\begin{eqnarray} x=\lambda x_1+(1-\lambda)x_2 \end{eqnarray}$ mit $\begin{eqnarray} x_1,x_2\in P \end{eqnarray}$ und $\begin{eqnarray} \lambda\in (0,1) \end{eqnarray}$ folgt, dass $\begin{eqnarray} x=x_1=x_2 \end{eqnarray}$ ist. Hier bräuchte ich einen Ansatz und komme nicht so recht weiter. Lieben dank
24.10.2009, 13:52	Elvis	Auf diesen Beitrag antworten »
Du brauchst eine Definition für "zulässige Basislösung". Dann kannst du zeigen, dass diese Definition zu einer der beiden "Extrempunkt"-Definitionen äquivalent ist.
24.10.2009, 14:01	Sabinee	Auf diesen Beitrag antworten »
Also wir haben zulässige Basislösung folgendermaßen definiert: Wir haben die Gleichung $\begin{eqnarray} Ax=b \end{eqnarray}$ so umgeschrieben: $\begin{eqnarray} A_Bx_B+A_Nx_N=b \end{eqnarray}$ wobei $\begin{eqnarray} x_B \end{eqnarray}$ die Basisvariablen und $\begin{eqnarray} x_N \end{eqnarray}$ die Nichtbasisvariablen sind. Die Basislösung ist die Lösung von $\begin{eqnarray} Ax=b \end{eqnarray}$ mit $\begin{eqnarray} x_N=0 \end{eqnarray}$ und folglich $\begin{eqnarray} x_B=A_B^{-1}b. \end{eqnarray}$ Diese Basislösung heißt zulässig, falls $\begin{eqnarray} x_B\geq 0 \end{eqnarray}$ . Wenn ich nun die Hinrichtung zeigen möchte, dann habe ich als Voraussetzung: $\begin{eqnarray} \tilde x=A_B^{-1}b \end{eqnarray}$ mit $\begin{eqnarray} \tilde x\geq 0 \end{eqnarray}$ Jetzt weiß ich nicht welche Definition ich anwenden soll um zu zeigen dass auch $\begin{eqnarray} \tilde x \end{eqnarray}$ ein Extrempunkt ist.
25.10.2009, 10:08	Elvis	Auf diesen Beitrag antworten »
Tut mir leid, ich weiß auch nicht, wie wir hiermit weiterkommen. Basislösungen werden beim Simplex-Algorithmus verwendet, um in endlich vieln Iterationen eine optimale Lösung zu berechnen. Dass Basislösungen den Ecken des Polyeders entsprechen, kann ich leider auch nicht beweisen. Kann hier bitte mal jemand helfen ?
28.10.2009, 18:01	Elvis	Auf diesen Beitrag antworten »
Hallo, Sabinee, es gibt neue Hoffnung. Ich habe deine Aufgabe einem Kollegen mitgeteilt, Mathematiker mit noch mehr LP-Background als ich. Wir sind uns einig, dass wir "wissen", dass Basislösungen dasselbe sind wie die Ecken des Polyeders. Nur der Beweis fehlt noch, sollte aber über die Konvexkombination möglich sein. Der Kollege ist zuversichtlich, morgen einen Beweis liefern zu können; ich melde mich morgen um 18:00 h wieder.
29.10.2009, 20:03	Elvis	Auf diesen Beitrag antworten »
Tut mir leid, zu früh gefreut. Wir kriegen's (noch) nicht überzeugend hin.
Anzeige

29.10.2009, 21:08	Mystic	Auf diesen Beitrag antworten »
Man argumentiert da ungefähr so: Angenommen, $\begin{eqnarray} x \end{eqnarray}$ ist eine zulässige Basislösung, aber kein Extrempunkt nach der 2. Definition. Dann gäbe es zwei verschiedene Punkte $\begin{eqnarray} x^{(1)},x^{(2)} \end{eqnarray}$ im zulässigen Bereich des LOPs, sodass $\begin{eqnarray} \exists \lambda \in (0,1): x=\lambda x^{(1)}+(1-\lambda)x^{(2)} \end{eqnarray}$ Aus einem Komponentenvergleich für Nichtbasisvariable folgt dann $\begin{eqnarray} \lambda x_N^{(1)}+(1-\lambda)x_N^{(2)} =x_N =0 \Rightarrow x_N^{(1)}=x_N^{(2)}=0 \end{eqnarray}$ und damit weiter $\begin{eqnarray} A_Bx_B^{(1)}=A_Bx_B^{(2)}=0 \Rightarrow A_B(x_B^{(1)}-x_B^{(2)})=0 \text{ mit } x_B^{(1)}-x_B^{(2)} \neq 0 \end{eqnarray}$ d.h., die Spaltenvektoren von $\begin{eqnarray} A_B \end{eqnarray}$ bilden entgegen der Annahme keine Basis, Widerspruch! Ist umgekehrt $\begin{eqnarray} x \end{eqnarray}$ zwar eine zulässige Lösung, aber für die vorgegebene Wahl der Basisvariablen keine zulässige Basislösung, so kann dass nur darin liegen, dass die Spaltenvektoren der Matrix $\begin{eqnarray} A_B \end{eqnarray}$ nicht linear unabhängig sind, d. h., wir könnten könnten einen Vektor $\begin{eqnarray} y_B \neq 0 \end{eqnarray}$ finden, sodass $\begin{eqnarray} A_By_B=0 \end{eqnarray}$ ist. Für ein hinreichend kleines $\begin{eqnarray} \delta >0 \end{eqnarray}$ wären aber dann $\begin{eqnarray} x_B^{(1)} =x_B+\delta y_b, \quad x_B^{(2)} =x_B-\delta y_b \end{eqnarray}$ immer noch zulässige Lösungen, aber $\begin{eqnarray} x_B \end{eqnarray}$ läge genau in der Mitte ihrer Verbindungsstrecke, d.h., $\begin{eqnarray} x_B \end{eqnarray}$ wäre kein Extrempunkt!
31.10.2009, 15:00	Sabinee	Auf diesen Beitrag antworten »
Dankeschön Ich habs so ähnlich gemacht

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »