| |
| Autor |
 Funktionsweise des Simplex-Algorithmus |
|
Pter87
Aktiv 
Dabei seit: 09.11.2018
Mitteilungen: 430
 |  Themenstart: 2022-02-05
|
Hallo,
ich wollte euch mal fragen, ob ich den Simplex-Algorithmus intuitiv richtig verstanden habe.
Ich hab das bisher so verstanden, dass der Simplex-Algorithmus ,den entsprechenden Polyeder betrachtend, im Grunde von Ecke zu Ecke läuft, was Sinn macht, da ja die Extrema unter anderem auch in den Ecken angenommen werden und es deswegen ausreicht diese zu untersuchen.
In jedem Simplex-Schritt tauscht man eine Nichtbasis-Variable mit einer Basisvariable so, dass das LGS weiterhin eine zulässige Lösung besitzt und die Kostenfunktion dabei möglichst minimiert wird. Man beginnt also bei dem Ausgangdictionary und manipuliert das LGS auf eine ganz bestimmte Art und Weise.
Bis hier hin ist das aber (für mich) eher einfach nur algebraische Manipulation gewesen, wo ich so direkt keine Verbindung zur Anschauung ("Wir besuchen Ecken des Polyeders...") sehen konnte.
Wenn ich mich jetzt nicht irre, dann beschreiben doch genau die Nichtbasisvariablen die entsprechenden Hyperebenen, deren Schnitt das derzeitige Extrema ist, habe ich recht? Man kann sich ja einfach die aktuelle zulässige Lösung anschauen und genau die Nichtbasisvariablen beschreiben ja im Ausgangsdictionary doch n Hyperebenen, wenn unsere Matrix n Spalten und m Zeilen hat. Im Grunde betrachtet der Simplex-Algorithmus also in jedem Schritt durch einen Basisvariable <-> Nichtbasisvariable Tausch eine andere Kombinationen von n verschiedenen Hyperebenen aus m+n vielen.
Stimmt das so ungefähr?
|
 Profil
|
Goswin
Senior 
Dabei seit: 18.09.2008
Mitteilungen: 1794
Wohnort: Chile, Ulm
 | Beitrag No.1, eingetragen 2022-02-05
|
\quoteon(2022-02-05 21:40 - Pter87 im Themenstart)
Ich hab das bisher so verstanden, dass der Simplex-Algorithmus den entsprechenden Polyeder betrachtend, im Grunde von Ecke zu Ecke [durch]läuft.
\quoteoff
Ja, aber nicht immer verschiedene Ecken. Wenn sich mehr als \(n\) Hyperebenen an einem Eckpunkt schneiden, kann es sein, dass der Algorithmus mehrere Iterationen lang an derselben Ecke bleibt.
\quoteon(2022-02-05 21:40 - Pter87 im Themenstart)
Wenn ich mich jetzt nicht irre, dann beschreiben doch genau die Nichtbasisvariablen die entsprechenden Hyperebenen, deren Schnitt das derzeitige Extrema ist.
\quoteoff
Stimmt. \(x_j\!=\!0\) ist die Hyperebene der unabhängigen Variablen \(x_j\).
|
Profil
|
Pter87
Aktiv
Dabei seit: 09.11.2018
Mitteilungen: 430
| Beitrag No.2, vom Themenstarter, eingetragen 2022-02-06
|
Hey,
ich wollte das nur nochmal genauer hinschreiben. Wenn ich also z.B. folgendes
$
\begin{align*}
\mathbf{max}\quad & 6x_1 + 4x_2 + x_3\\
\mathbf{s.t.}\quad & - 3x_1 - 5x_2 - 2x_3 +6 = s_1\\
& - x_1 - 10x_2 - 5x_3 + 2 = s_2\\
& - 4x_1 - 6x_2 + 4x_3 + 4 = s_3\\
& x_1,x_2,x_3,s_1,s_2,s_3 \geq 0
\end{align*}
$
Ausgangsdictionary habe, dann beschreibt ja jede Nichtbasisvariable(nach dem x-ten Simplex-Schritt) eine Hyperebene. $x_1,x_2,x_3$ würden "triviale" Seitenflächen beschreiben und $s_1,s_2,s_3$ die Spezielleren. Zum Beispiel $x_1 = 0,s_1 = 0,s_2 = 0$ würden eindeutig das Extremum beschreiben, wenn die Hyperebenen linear unabhängig wären, was wir einfach mal annehmen.
\quoteon(2022-02-05 23:50 - Goswin in Beitrag No. 1)
Ja, aber nicht immer verschiedene Ecken. Wenn sich mehr als \(n\) Hyperebenen an einem Eckpunkt schneiden, kann es sein, dass der Algorithmus mehrere Iterationen lang an derselben Ecke bleibt.
\quoteoff
Stimmt, das habe ich vergessen.
Wie genau kann man sich eigentlich denn Polyeder mit den Schlupfvariablen vorstellen? Ist der "Gleichheitspolyeder" nicht einfach nur der kanonische Polyeder eingebettet in einen höherdimensionalen Raum? Im obigen Beispiel hat man ja im Grunde einen Polyeder im $\mathbb{R}^3$, aber durch die Schlupfvariablen ist man dann im $\mathbb{R}^6$. Natürlich gibt es da keine Anschauung mehr, aber ist es im Grunde das was dann passiert?
|
Profil
|
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1794
Wohnort: Chile, Ulm
| Beitrag No.3, eingetragen 2022-02-06
|
\quoteon(2022-02-06 01:35 - Pter87 in Beitrag No. 2)
$
\begin{align*}
\mathbf{max}\quad & 6x_1 + 4x_2 + x_3\\
\mathbf{s.t.}\quad & - 3x_1 - 5x_2 - 2x_3 +6 = s_1\\
& - x_1 - 10x_2 - 5x_3 + 2 = s_2\\
& - 4x_1 - 6x_2 + 4x_3 + 4 = s_3\\
& x_1,x_2,x_3,s_1,s_2,s_3 \geq 0
\end{align*}
$
[...]
$x_1,x_2,x_3$ würden "triviale" Seitenflächen beschreiben und $s_1,s_2,s_3$ die Spezielleren.
\quoteoff
Aus Sicht des Algorithmus (nicht der des Anwenders) besteht in \(\mathbb{R}^6\) überhaupt kein Unterschied zwischen "trivialen" und "speziellen" Seitenflächen, und für das Verständnis ist es kompliziert und irreführend, deren Variablen mit verschiedenen Buchstaben zu versehen: statt \(s_1,s_2,s_3\) besser \(x_4,x_5,x_6\).
\quoteon(2022-02-06 01:35 - Pter87 in Beitrag No. 2)
Ist der "Gleichheitspolyeder" nicht einfach nur der kanonische Polyeder eingebettet in einen höherdimensionalen Raum? Im obigen Beispiel hat man ja im Grunde einen Polyeder im $\mathbb{R}^3$, aber durch die Schlupfvariablen ist man dann im $\mathbb{R}^6$.
\quoteoff
Topologisch (welche Ecken benachbart sind) ist der Polyeder derselbe; metrisch (was die Entfernungen der Ecken zueinander anbetrifft) wird er je nach Metrik verzerrt. Aber das wird er ja sowieso in jedem einzelnen Iterationsschritt, schau dir einmal diese Bilder an!
|
Profil
|
| Pter87 hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
