# Linear program solved with Simplex out of given bound

I believe to be missing something important in the Simplex algorithm because it goes beyond the given objective.

Let be the following linear programming program:

\begin{cases} \max Z(x,y,z)=&x&+y&+z&\\ & x& & &\le 10\\ &-3x&-\frac{1}{4}y&+z&\le 4\\ &&y& &\le 20\\ && & z&\le 40\\ & & &x,y,z&\ge0 \end{cases}

I wanted to solve it with the matrix method knowing that the given optimal value is $69$.

I don't know how to find the origin starting point, and I would be glad if you can provide me a method, but I had:

\begin{cases} e_1=10\\ e_2=4\\ e_3=20\\ e_4=40 \end{cases}

given as a starting point. I don't know what to do with it.

At the beginning $y$ enters the basis and $e_2$ goes out.

$$\begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 0 &10\\ -12 & 1 & 4 & 0 & 4 & 0 & 0 & 16\\ 12 & 0 & -4 & 0 & -4 & 1 & 0 & 4\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 40\\ 13 & 0 & 5 & 0 & -4 & 0 & 0 & -16\\ \end{pmatrix} \begin{pmatrix} e_1\\y\\e_3\\e_4 \end{pmatrix}$$

$x$ enters the basis and $e_3$ goes out.

\begin{cases} L_2=L_2+12L_1\\ L_3=L_3-12L_1\\ L_5=L_5-13L_1 \end{cases}

$$\begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 0 &10\\ 0 & 1 & 4 & 12 & 4 & 0 & 0 & 136\\ 12 & 0 & -4 & 0 & -4 & 1 & 0 & -116\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 40\\ 0 & 0 & 5 & -13 & -4 & 0 & 0 & -146\\ \end{pmatrix} \begin{pmatrix} e_1\\y\\x\\e_4 \end{pmatrix}$$

Yet, here, there is something wrong: I'm already maximizing at a level of $146$ when the given maximum is only $69$.

What did I missed in applying the Simplex algorithm matricial method?

The scilab operation to obtain $69$ are

M=PIVOTGJ(M,1,1)
M=PIVOTGJ(M,2,3)
M=PIVOTGJ(M,3,2)


and the given optimal solution is $x=10, y=10, z=39, e_4=1$

• i think your solution is not feasible, so the max value of $146$ is ok -- it can be more if it does not satisfy the constraints. – gt6989b Mar 6 '16 at 13:20
• The given optimal solution is correct. – Claude Leibovici Mar 6 '16 at 13:27
• @ClaudeLeibovici Thanks for checking, therefore where did I went wrong? – ThePassenger Mar 6 '16 at 14:57
• No idea ! It has been almost 50 years I did not use the simplex method. Sorry for that ! By the way, where are you located in France ? – Claude Leibovici Mar 6 '16 at 15:02
• @ClaudeLeibovici Never mind! Paris Dauphine University! – ThePassenger Mar 6 '16 at 15:10