Simplexfehler < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:26 So 23.06.2013 | | Autor: | Klerk91 |
Ich will folgendes lineares Programm mit dem Simplexalgo lösen
Wir haben [mm] $(x_1,x_2,s_1,s_2,s_3)\ge [/mm] 0$ mit
[mm] $\begin{pmatrix} -2 & 1 & 1& 0&0 \\ 1 &2&0&1&0 \\ 4 &3 &0&0&1 \\ \end{pmatrix}(x_1,x_2,s_1,s_2,s_3)^T=\begin{pmatrix} 2 \\14 \\36 \end{pmatrix}$
[/mm]
und möchten minimieren: $ [mm] \text{min}_{x \in \mathbb{R}^5} [/mm] (-1,-1,0,0,0)x $
(Schlupfvariablen sind die s-Variablen)
Habe folgendes getan:
Mein Startbasisvektor ist $J=(3,4,5)$
Daher 1.) [mm] $\bar{A}_J=A^{-1}_J [/mm] A= [mm] \begin{pmatrix} 1 &0&0 \\0&1&0 \\0&0&1 \end{pmatrix}\begin{pmatrix} -2 & 1 & 1& 0&0 \\ 1 &2&0&1&0 \\ 4 &3 &0&0&1 \\ \end{pmatrix}=A$
[/mm]
und
[mm] $\bar{b}_J=A^{-1}_Jb=\begin{pmatrix} 2 \\14 \\36 \end{pmatrix}$. [/mm]
Daher [mm] $x=\begin{pmatrix}0\\0\\ 2 \\ 14 \\36 \end{pmatrix}$
[/mm]
2.) [mm] $\bar{c}^T=c^T-c^T_J\bar{A}_{J}=(-1,-1,0,0,0)-(0,0,0)\bar{A}_{J}=(-1,-1,0,0,0)$
[/mm]
3.) Man wähle also eine negative Komponente z.B. s=1, mit zugehörigem [mm] $y_k=(e_s)_k=\begin{pmatrix} 0 \\1 \end{pmatrix}$, $y_J=-\bar{A}_Je_s=\begin{pmatrix}2\\-1\\-4 \end{pmatrix}$
[/mm]
4.) Wählen wir unsere neue Basis so, dass sie immer noch positiv und damit zulässig ist: [mm] $x_new=x+9y=\begin{pmatrix} 0\\0\\2\\14\\36 \end{pmatrix} [/mm] + 9 [mm] \begin{pmatrix} 1\\0\\2\\-1\\-4 \end{pmatrix}=\begin{pmatrix} 9 \\0 \\20 \\5\\0 \end{pmatrix} [/mm] $
Die gehört also nun zu: [mm] $J_{new}=\begin{pmatrix} 3 \\1 \\5 \end{pmatrix}$(neuer [/mm] Basisvektor).
Also rechne ich die Matrixtrafo aus: $ [mm] \bar{A}_{Jnew}=\begin{pmatrix} 1 &-2&0 \\0&1&0 \\0&4&1 \end{pmatrix}^{-1}\begin{pmatrix} -2 & 1 & 1& 0&0 \\ 1 &2&0&1&0 \\ 4 &3 &0&0&1 \\ \end{pmatrix}=\begin{pmatrix} 0&5&1&2&0 \\ 1&2&0&1&0 \\ 0 &-5&0&-4&0 \\\end{pmatrix}$
[/mm]
Der Fehler taucht nun beim berechnen von [mm] $\bar{c}^T$ [/mm] bezüglich der neuen Basis auf
[mm] $\bar{c}^T=c^T-c^T_{Jnew}\bar{A}_{Jnew}=(-1,-1,0,0,0)-(0,-1,0)\bar{A}_{Jnew}=(0,1,0,1,0)$
[/mm]
Da ist alles positiv, d.h. wir wären eig. fertig, da ich aber das ganze vorher mit einem Programm getest habe, weiß ich, dass 6 und 4 die richtige lösung ist und nicht das was ich da habe. Irgendwo liegt also ein Fehler!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Di 25.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
