Beweis Komplementäre-Schlupf-Theorem

Neue Frage »

02.06.2009, 06:15	Martin100180	Auf diesen Beitrag antworten »
Beweis Komplementäre-Schlupf-Theorem Hallo! Ich arbeite mich gerade in das Thema Komplementäre Schlupf Theorem ein und habe zwei optimale Tableau, bei denen zu beweisen giilt, dass bei den gefunden Lösungen das Komplementäre-Schlupf-Theorem gilt. Einen Ansatz habe ich schon erstellt. Da es meine erste Auseinandersetzung mit dem Thema ist wäre es toll, wenn ihn jemand bestätigen oder ergänzen könnte. Danke! Martin
02.06.2009, 10:26	Martin100180	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Bei c und d handelt es sich jeweils um (D) und (P).
02.06.2009, 10:56	Reksilat	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Hi Martin, Kannst Du nicht mal die komplette Aufgabenstellung posten? Bei Deinem Primalproblem sind ja z.B. keine Schlupfvariablen vorhanden, d.h. es handelt sich um ein Problem der Form $\begin{eqnarray} Ax=b \end{eqnarray}$ . Dass $\begin{eqnarray} b-Ax_0=0 \end{eqnarray}$ ist, ist dadurch doch trivial. Also ich kann mit Deinen Ausführungen nicht wirklich was anfangen, zumal ich nur die Aussage $\begin{eqnarray} u^T(Ax-b)=0 \end{eqnarray}$ kenne. Gruß, Reksilat.
02.06.2009, 11:07	Martin100180	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Hallo! Guter Einwand! LOP (P) max x0 = 20x1 + 20x2 + 31x3 + 11x4 + 12x5 u. d. N. x1 + x3 + x4 + 2x5 <= 21 x2 + 2x3 + x4 + x5 <= 12 xi >= 0 daraus ergibt sich: LOP (D) min 21u1 + 12u2 u. d. N. u1 >= 20 u2 >= 20 u1 + u2 >= 31 u1 + u2 >= 11 2u1 + u2 >0 12 u1, u2 >= 0
02.06.2009, 14:27	Reksilat	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Gut, jetzt blicke ich schon etwas besser durch. Also zuerst muss ich sagen, dass ich den Satz nur als $\begin{eqnarray} u_0^T(Ax_0-b)=0 \end{eqnarray}$ und $\begin{eqnarray} x_0^T(A^Tu_0-c)=0 \end{eqnarray}$ kenne. Da hier $\begin{eqnarray} Ax=b \end{eqnarray}$ gilt, ist die Verifizierung des ersten Teils des Satzes somit trivial. Für den zweiten Teil fehlt bei Dir aber noch etwas, da man ja immer die komplette Matrix verwenden muss. Es ist $\begin{eqnarray} u_0^T=(20,20) \end{eqnarray}$ , $\begin{eqnarray} A=\begin{pmatrix}1&0&1&1&2\\0&1&2&1&1\end{pmatrix} \end{eqnarray}$ und $\begin{eqnarray} c^T=(20,20,31,11,12) \end{eqnarray}$ und somit: $\begin{eqnarray} u_0^TA-c^T=(0,0,29,29,48)\neq 0 \end{eqnarray}$ Allerdings wird $\begin{eqnarray} x_0^T(A^Tu_0-c)=0 \end{eqnarray}$
02.06.2009, 14:39	Martin100180	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Ok. Das kann ich nachvollziehen. Aber wie kommst du auf die Werte 31, 11 und 12?
Anzeige

02.06.2009, 14:44	Reksilat	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Das ist der Vektor $\begin{eqnarray} c \end{eqnarray}$ aus der Zielfunktion $\begin{eqnarray} c^Tx=20x_1+20x_2+31x_3+11x_4+12x_5\to \max \end{eqnarray}$
02.06.2009, 19:20	Martin100180	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Ich habe den Hinweis gefunden, dass Schlupfvariable nicht mit in die Matrix aufgenommen werden. Dann sollte die Rechnung so aussehen. Kann das jemand bestätigen?
02.06.2009, 20:31	Reksilat	Auf diesen Beitrag antworten »
RE: Beweis Komplementäre-Schlupf-Theorem Die Schlupfvariablen sind aber nur $\begin{eqnarray} x_6 \end{eqnarray}$ und $\begin{eqnarray} x_7 \end{eqnarray}$ . Die anderen sind Nichtbasisvariablen.

Neue Frage »

Antworten »

Beweis Komplementäre-Schlupf-Theorem

Verwandte Themen