Simplex Method gives multiple, unbounded solutions but Graphical Method gives unique soution 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?


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.
