Basisinverse Simplexalgorithmus

08.02.2011, 16:31	SA89	Auf diesen Beitrag antworten »
Basisinverse Simplexalgorithmus Hi, kann mir jemand sagen, wie man bei Vorliegen des optimalen Endtableus die Basisinverse ablesen kann? Angenommen wenn zusätzlich noch eine Hilfsvariable eingeführt worden ist und es eine 3x3 Basis gibt, und 3 Schlupfvariable plus die Hilfsvariable, was ist dann die Basis? Kann man die Basisinverse einfach so ablesen, oder muss man die jeweiligen möglichen Basisinversen mit der Basis multiplizieren, um herauszufinden, was die Basisinverse ist?
09.02.2011, 11:44	Reksilat	Auf diesen Beitrag antworten »
RE: Basisinverse Simplexalgorithmus Hallo, Direkt ablesen wirst Du sie aus dem reduzierten Tableau nicht können, Du kannst aber das erweiterte Tableau immer mitberechnen. Ich beziehe mich auf die Bezeichnungen aus http://de.wikipedia.org/wiki/Simplex-Ver...#Simplextableau Nehmen wir mal das Problem $\begin{eqnarray} Ax\leq b \end{eqnarray}$ , $\begin{eqnarray} x\geq 0 \end{eqnarray}$ , $\begin{eqnarray} c^Tx\to \max \end{eqnarray}$ Die Spalten von $\begin{eqnarray} A \end{eqnarray}$ sind zu Beginn alles Nichtbasisspalten, die Basisvariablen sind die Schlupfvariablen, und im Tableau steht das $\begin{eqnarray} A \end{eqnarray}$ . Am Ende steht im Tableau $\begin{eqnarray} A_B^{-1}\cdot A \end{eqnarray}$ , wobei $\begin{eqnarray} A_B \end{eqnarray}$ die Basisspalten von $\begin{eqnarray} A \end{eqnarray}$ bezeichnet. Daraus kann man $\begin{eqnarray} A_B^{-1} \end{eqnarray}$ natürlich nicht ablesen, da man dafür eine Rechtsinverse von $\begin{eqnarray} A \end{eqnarray}$ benötigen würde, die ja gemeinhin nicht existieren muss. Aber Du kannst am Anfang noch Spalten für die Schlupfvariablen hinzufügen. Dort steht dann, wie bei Wiki, die Einheitsmatrix. Die berechnest Du die ganze Zeit wie gewohnt mit, allerdings wird in diesen Spalten kein Austausch stattfinden. Im Endtableau steht dann dort $\begin{eqnarray} A_B^{-1}I \end{eqnarray}$ und Du kannst die Basisinverse ablesen. Gruß, Reksilat.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »