0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – gt6989b Mar 6 '16 at 13:20
  • $\begingroup$ The given optimal solution is correct. $\endgroup$ – Claude Leibovici Mar 6 '16 at 13:27
  • $\begingroup$ @ClaudeLeibovici Thanks for checking, therefore where did I went wrong? $\endgroup$ – ThePassenger Mar 6 '16 at 14:57
  • $\begingroup$ 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 ? $\endgroup$ – Claude Leibovici Mar 6 '16 at 15:02
  • $\begingroup$ @ClaudeLeibovici Never mind! Paris Dauphine University! $\endgroup$ – ThePassenger Mar 6 '16 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.