2
$\begingroup$

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?

Graphical Method

$\endgroup$
  • $\begingroup$ Any solution for $y$ yields infinitely many solutions for $m, n$. $\endgroup$ – Robert Shore Aug 31 '19 at 5:48
  • $\begingroup$ @RobertShore Okay, but how do you infer that the optimal solution for $y$ is unique? In other words how do we know $m-n$ will be fixed for all optimal solutions? What if some other optimal solution had $y=7$? $\endgroup$ – Shubham Johri Aug 31 '19 at 6:08
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for! Thank you! $\endgroup$ – Shubham Johri Aug 31 '19 at 18:55
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Doesn't the application of the Simplex Method entail that all variables are non-negative? $\endgroup$ – Shubham Johri Aug 31 '19 at 18:00
  • $\begingroup$ Conventionally, yes. In theory, you can still kind of make the simplex method work when $y$ is unrestricted. To do this, begin by bringing $y$ into the basis (even if this decreases $z$). Once $y$ is basic, just make sure it never leaves the basis, even if it becomes negative. It's a bit tricky to think through and isn't really worth it, which is why we replace $y$ by $m-n$. $\endgroup$ – Misha Lavrov Aug 31 '19 at 18:18
  • 1
    $\begingroup$ @ShubhamJohri, you are right, I considered $y\ge 0$, because if $y\le 0$, the pivot column will still be $x$ column, while the $y$ coefficient in the last row will be $+2$, hence we get the optimal solution $z(15,0)=45$ right away, which is less than the case $y\ge 0$. $\endgroup$ – farruhota Aug 31 '19 at 18:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.