Simplex Method gives multiple, unbounded solutions but Graphical Method gives unique soution

Question

I'm taking an undergraduate course on Linear Programming and we were asked to solve the following problem using the Simplex Method:$$\max:~Z=3x+2y\\\text{subject to}\begin{cases}x+y\le20\\0\le x\le15\\x+3y\le45\\-3x+5y\le60\\y\text{ unrestricted in sign}\end{cases}$$The standard form of the LPP is$$\max:~Z=3x+2m-2n\\\text{subject to}\begin{cases}x+m-n+a=20\\x+b=15\\x+3m-3n+c=45\\-3x+5m-5n+d=60\\x,m,n,a,b,c,d\ge0\end{cases}$$where $y=m-n$. The optimal Simplex tableau was obtained$$\begin{matrix}&&3&2&-2&0&0&0&0\\&\text{Basis}&x&m&n&a&b&c&d&\text{RHS}\\2&m&0&1&-1&1&0&0&-1&5\\0&b&0&0&0&-3&1&0&2&15\\0&c&0&0&0&-5&0&1&8&80\\3&x&1&0&0&0&0&0&1&15\\&\text{Deviations}&0&0&\color{red}0&-2&0&0&-1&Z=55\end{matrix}$$Since all deviations are negative, the stopping criteria is fulfilled. But the deviation corresponding to non-basic $n$ is $0$, so this must be a case of multiple optimal solutions. With $n$ as the entering variable the minimum ratio test fails, which means this is also a case of unbounded solutions.

On solving the same question using Graphical method, I got a unique solution $Z=55$ at $(15,5)$. What is the problem in the Simplex Method?

Answer 1

In this problem, the non-uniqueness in the simplex method comes from the substitution $y = m-n$: a single value of $y$ can be expressed as $m-n$ in many ways.

To see that this is the only reason for non-uniqueness, we can parametrize the solutions found by the simplex method and find all the possible solutions.

The bottom row of your tableau actually corresponds to the equation $z = 55 - 2a - d$. So we know that we obtain the optimal value of $z=55$ exactly when $a=d=0$.

To make this substitution, we delete the $a$ and $d$ columns from the tableau, and get the system of equations $$ \begin{bmatrix} 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x \\ m \\ n \\ b \\ c\end{bmatrix} = \begin{bmatrix}5 \\ 15 \\ 80 \\ 15\end{bmatrix} $$ which tells us that the optimal solutions are those feasible solutions which have $m-n=5$, $b = 15$, $c = 80$, and $x=15$ (and $a=d=0$).

Since $y = m-n=5$ is fixed, the simplex method confirms that actually there's only one solution $(x,y) = (15,5)$ after we undo this substitution and return to the original formulation of the LP.

Answer 2

The simplex method will produce the correct answer: $$\max:~Z=3x+2y\\\text{subject to}\begin{cases}x+y\le20\\0\le x\le15\\x+3y\le45\\-3x+5y\le60\\y\text{ unrestricted in sign}\end{cases} \Rightarrow \begin{cases}x+y+s_1=20\\x+s_2=15\\x+3y+s_3=45\\-3x+5y+s_4=60\\y\text{ unrestricted in sign}\end{cases}\\ \begin{array}{cccccc|c} x&y&s_1&s_2&s_3&s_4&C\\ \hline 1&1&1&0&0&0&20&s_1\\ \boxed1&0&0&1&0&0&15&s_2\\ 1&3&0&0&1&0&45&s_3\\ -3&5&0&0&0&1&60&s_4\\ \hline -3&-2&0&0&0&0&0\\ \end{array} \Rightarrow \\ \begin{array}{cccccc|c} x&y&s_1&s_2&s_3&s_4&C\\ \hline 0&\boxed1&1&-1&0&0&5&s_1\\ 1&0&0&1&0&0&15&x\\ 0&3&0&-1&1&0&30&s_3\\ 0&5&0&3&0&1&105&s_4\\ \hline 0&-2&0&3&0&0&45\\ \end{array} \Rightarrow \\ \begin{array}{cccccc|c} x&y&s_1&s_2&s_3&s_4&C\\ \hline 0&1&1&-1&0&0&\color{red}5&y\\ 1&0&0&1&0&0&\color{red}{15}&x\\ 0&0&-3&2&1&0&15&s_3\\ 0&0&-5&8&0&1&80&s_4\\ \hline 0&0&2&1&0&0&\color{red}{55}\\ \end{array}$$ Thus: $z(15,5)=55$ is the maximum.

Answer 3

I´ve used a solver and get a slightly different final tableau. My initial tableau is

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline x_1&y_1&y_2&s_1&s_2&s_3&s_4&RHS \\ \hline 1&1&-1&1&0&0&0&20 \\ \hline 1&0&0&0&1&0&0&15 \\ \hline 1&3&-3&0&0&1&0&45 \\ \hline -3&5&-5&0&0&0&1&60 \\ \hline -3&-2&2&0&0&0&0&0\\ \hline\end{array}$$

The last line is the objective function. According to the simplex alogrithm we need $y=y_1-y_2$ since $y$ is not bounded. Here $y_1,y_2\geq 0$ And $s_1,s_2,s_3,s_4\geq 0$ are the slack variables. The corresponding final tableau is

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline x_1&y_1&y_2&s_1&s_2&s_3&s_4&RHS \\ \hline 0&1&\color{red}{-1}&1&-1&0&0&5 \\ \hline 1&0&0&0&1&0&0&15 \\ \hline 0&0&0&-3&2&1&0&15 \\ \hline 0&0&0&-5&8&0&1&80 \\ \hline 0&0&0&2&1&0&0&55\\ \hline \end{array}$$

Our final tableaus are equal except that the columns 5 and 7 are swapped. But the conclusion is the same. You can make a pivot operation only if the corresponding value of $a_{ij}$ is greater than $0$. But here we have $a_{13}=\color{red}{-1}$. So the simplex algorithm stops here. The optimal solution is $(x^*,y^*,s_1^*,s_2^*,s_3^*,s_4^*)=(15,5,0,0,15,80)$ since all coefficients of the objective function are greater or equal than $0$.

Remark

You start with values with reversed signs at the row for the objective function. This is valid as well. That means that the row for the objective function at the final tableau is $\begin{array}{|c|c|c|c|c|c|} \hline 0&0&0&-2&-1&0&0&-55\\ \hline \end{array}\Rightarrow z^*=55$

The criteria for stopping the simplex algorithm is that the coefficients of the objective function must be non-positive. This is the case here.

Remark 2

If you consider the inequalities the solution space looks like the yellow one. The red arrows indicates that the solution space goes further.