# Apply Simplex method using M-method

I want to solve the following linear programming problem:

$$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$

In this case we use the $M$-method.

The canonical form of the problem is the following:

$$-\max (-3y_1+y_2-2y_3) \\ 3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7$$

The matrix $A$ ($Ax=b$) is the following:

$A=\begin{bmatrix} 3 & 2 & -1 & 1 & 0 & 0 & 0\\ 0 & 5 & -1 & 0 & 1 & 0 & 0\\ 4 & -1 & 0 & 0 & 0 & -1 &0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{bmatrix}$

It doesn't contain the $4 \times 4$ identity matrix, that's why we introduce an artificial variable $y_8 \geq 0$ at the third equation and we have the new system of restrictions:

$$3y_1+2y_2-y_3 +y_4= 9 \\ 5y_2-y_3 +y_5= 1 \\ 4y_1-y_2 -y_6+y_8= 1 \\ y_1+y_2+y_3 +y_7= 3 \\ y_i \geq 0, i=1,2, \dots, 7,8$$

Now we will solve the problem with the $M-$method , i.e. we will solve the linear programming problem $\max(-3y_1+y_2-2y_3+My_8), M<<0$ under the new system of restrictions.

I tried to apply the simplex method and I got the following:

$$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_4 & 0 & 160 & 2 & 3 & 4 & 1 & 0 & 0 & 0 & 80 & L_1\\ P_5 & 0 & 180 & 3 & 2 & 3 & 0& 1 & 0 & 0 & 60 & L_2\\ P_6 & 0 & 200 & 4 & 3 & 2& 0 & 0 & 1 & 0 & 50 & L_3\\ P_7 & 0 & 120 & 1 & 2 & 1 &0 & 0 & 0 & 1 & 120 & L_4 \\ & z & 0 & -30 & -26 & -28 & 0 & 0& 0& 0 & & L_5 \end{matrix}$$

$P_1$ gets in the basis, while $P_6$ gets out of the basis.

$\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_4 & 0 & 60 & 0 & \frac{1}{2} & 3 & 1 & 0 & -\frac{1}{2} & 0 & 20 & L_1'=L_1-2L_3'\\ P_5 & 0 & 30 & 0 & -\frac{1}{4} & \frac{3}{2} & 0& 1 & -\frac{3}{4} & 0 & 20 & L_2'=L_2-3L_3'\\ P_1 & 30 & 50 & 1 & \frac{3}{4} & \frac{1}{2}& 0 & 0 & \frac{1}{4} & 0 & 100 & L_3'=\frac{L_3}{4}\\ P_7 & 0 & 120 & 1 & 2 & 1 & 0 & 0 & 0 & 1 & 120 & L_4'=L_4 \\ & z & 1500 & 0 & -\frac{7}{2} & -13 & 0 & 0&\frac{15}{2} & 0 & & L_5'=L_5+30L_3' \end{matrix}$

And then $P_3$ would get in the basis and $P_4$ would go out of the basis.

But I found that the initial tableau should be the following:

So could you explain how we apply the Simplex method in such a case?

• I think "$\max(-3y_1+y_2-2y_3+MY-8), M<<0$" should be "$\max(-3y_1+y_2-2y_3-My_8), M<<0$" – GNUSupporter 8964民主女神 地下教會 Jan 10 '16 at 10:52
• @GNUSupporter Yes, sorry. It was a typo. – Evinda Jan 10 '16 at 10:59
• How can $P_4 = 160$ in the first tableau satisfy this first constraint $3y_1+2y_2-y_3 +y_4= 9$? – GNUSupporter 8964民主女神 地下教會 Jan 10 '16 at 11:02
• @GNUSupporter I retried it and now I got this first simplex tableau:  $\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & P_8 & \theta & \\ P_4 & 0 & 9 & 3 & 2 & -1 & 1 & 0 & 0 & 0 & 0& &\\ P_5 & 0 & 1 & 0 & 5 & -1 & 0 & 1 & 0 & 0 & 0& &\\ P_8 & 0 & 1 & 4 &-1 & 0 & 0 & 0 & -1 &0 & 1& &\\ P_7 & 0& 3 & 1 & -1 & 1 & 0 & 0 & 0 & 1 &0 & &\\ & z & 9M& 3M+3 & 2M-1& 2-M & 0 & 0 & 0 & 0 &0 & & \end{matrix}$  – Evinda Jan 10 '16 at 11:29
• At my textbook, the values of $z_j-c_j$ are different from mine, namely: $M \ \ \ 4M+3 \ \ \ -M-1 \ \ \ \ 2 \ \ \ 0 \ \ \ 0 \ \ \ -M \ \ \ 0 \ \ \ 0$.  I found these values doing the operation $L_4'=ML_1+L_4$. Have I done something wrong? – Evinda Jan 10 '16 at 11:30

We treat $|M|$ as a very large constant, and $M < 0$ here. (IMHO, I don't think that assuming $M$ to be negative is a good habit. Assuming $M > 0$ to be very large and write the objective function as $\max(-3y_1+y_2-2y_3-My_8)$ is better.)

The inital matrix

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & P_8 & \theta & \\ P_4 & 0 & 9 & 3 & 2 & -1 & 1 & 0 & 0 & 0 & 0& &\\ P_5 & 0 & 1 & 0 & 5 & -1 & 0 & 1 & 0 & 0 & 0& &\\ P_8 & M & 1 & 4 &-1 & 0 & 0 & 0 & -1 &0 & 1& &\\ P_7 & 0 & 3 & 1 & -1 & 1 & 0 & 0 & 0 & 1 &0 & &\\ & z & 0 & 3 & -1 & 2 & 0 & 0 & 0 & 0 & -M & & \end{matrix}

You get the error because you multiplied the first row by $M$ and add it to the last row. In fact, it should be the $P_8$-row instead of the first row: $P_8$ is a basic variable, so the $P_8$-column should have only one non-zero entry.

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & P_8 & \theta & \\ P_4 & 0 & 9 & 3 & 2 & -1 & 1 & 0 & 0 & 0 & 0& 3 &\\ P_5 & 0 & 1 & 0 & 5 & -1 & 0 & 1 & 0 & 0 & 0& - &\\ P_8 & M & 1 & 4^* &-1 & 0 & 0 & 0 & -1 &0 & 1& \frac14^* &\\ P_7 & 0 & 3 & 1 & -1 & 1 & 0 & 0 & 0 & 1 &0 & 3 &\\ & z & M & 4M+3^* & -M-1 & 2 & 0 & 0 & -M & 0 & 0 & & \end{matrix}

Now we can delete the $P_8$-column since it will never enter into the basis again. (It doesn't hurt if you leave it here, but you'll need to calculate five more entries which are useless.)

Now, we have a BFS, and the $M$ is eliminated. We can proceed normally to get the optimal tableau.

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_4 & 0 & 33/4 & 0 & 11/4 & -1 & 1 & 0 & 3/4 & 0 & 3 & \\ P_5 & 0 & 1 & 0 & 5^* & -1 & 0 & 1 & 0 & 0 & \frac15^* & \\ P_1 & -3 & 1/4 & 1 & -1/4 & 0 & 0 & 0 & -1/4 & 0 & - & \\ P_7 & 0 & 11/4 & 0 & 5/4 & 1 & 0 & 0 & 1/4 & 1 & \frac{11}{5} & \\ & z & -3/4 & 0 & -1/4^* & 2 & 0 & 0 & 3/4 & 0 & & \end{matrix}

\begin{matrix} B & c_B & b & P_1 & P_2 & P_3 & P_4 & P_5 & P_6 & P_7 & \theta & \\ P_4 & 0 & 77/10 & 0 & 0 & -9/20 & 1 & -11/20 & 3/4 & 0 & - & \\ P_2 & 0 & 1/5 & 0 & 1 & -1/5 & 0 & 1/5 & 0 & 0 & - & \\ P_1 & -3 & 3/10 & 1 & 0 & -1/20 & 0 & 1/20 & -1/4 & 0 & - & \\ P_7 & 0 & 5/2 & 0 & 0 & 5/4 & 0 & -1/4 & 1/4 & 1 & - & \\ & z & -7/10 & 0 & 0 & 39/20 & 0 & 1/20 & 3/4 & 0 & & \end{matrix}

Therefore, the optimal solution is $\left(\frac{3}{10},\frac15,0,\frac{77}{10},0,0,\frac52,0\right)^T$ and the optimal value is $-\frac{7}{10}$.

• I see... This is the optimal solution for $\max (-3y_1+y_2-2y_3+My_8)$ under the new system of restrictions. The initial problem was to find $- \max (-3y_1+y_2-2y_3)$ without $y_8$ at the system of restrictions. How can we find now the solution for the initial problem? – Evinda Jan 10 '16 at 17:15
• @Evinda The solution is the same for both LPPs, so the optimal value for the original value is $\frac{7}{10}$ – GNUSupporter 8964民主女神 地下教會 Jan 10 '16 at 17:39