2
$\begingroup$

Consider the following linear program:

Maximize $Z = x - y$ where $-x+y\ge 1$ and $x\ge 0, y\ge 0$

Add surplus and artificial variables to the constraint: $-x+y-s+a=1$

For phase 1 maximize $W = -a = -x+y-s-1$. The starting tableau is

$$ \begin{array}{c|cccc|c} &x&y&s&a&b\\ \hline a&-1&1&-1&1&1\\ \hline W&-1&1&-1&0&1 \end{array} $$

The only positive element in in column 2, so $y$ is the entering variable. The only constraint row is row 1, $a$ is the leaving variable. Pivot around (1,2) to get

$$ \begin{array}{c|cccc|c} &x&y&s&a&b\\ \hline y&-1&1&-1&1&1\\ \hline W&0&0&0&-1&0 \end{array} $$

$W = 0$ is the maximum, phase 1 is done. Remove the artificial column and initialize the last row for phase 2, maximize $Z = x-y$:

$$ \begin{array}{c|ccc|c} &x&y&s&b\\ \hline y&-1&1&-1&1\\ \hline Z&-1&1&0&0 \end{array} $$

The only positive entry in the last row is in column 2, the only row is row 1: pivot around (1,2) to get

$$ \begin{array}{c|ccc|c} &x&y&s&b\\ \hline y&-1&1&-1&1\\ \hline Z&0&0&1&-1 \end{array} $$

Now the only positive objective entry is in column 2, but there are no positive entries in that column to pivot around! According to Wikipedia this means that the linear program is unbounded. Looking at this problem geometrically:

It is clear that the problem isn't "really" unbounded: $Z$ can at most be $-1$. I assume the Simplex algorthm breaks down because it doesn't realize that in order to increase $x$ $y$ must also be increased, keeping $Z$ at the same value. Is there a way to change the algorithm so it does not break down in this case, and simply stops at the last tableau?

$\endgroup$
  • $\begingroup$ Is $x,y\geq 0$, the non-negativity condition? $\endgroup$ – callculus Feb 25 '18 at 14:03
  • $\begingroup$ @callculus Yes, I'll edit the image to clarify. $\endgroup$ – Todd Sewell Feb 25 '18 at 14:10
  • $\begingroup$ Ok. Please edit the problem as well. Otherwise it is confusing. $\endgroup$ – callculus Feb 25 '18 at 14:12
  • $\begingroup$ @callculus Yup, done that as well. $\endgroup$ – Todd Sewell Feb 25 '18 at 14:17
  • 1
    $\begingroup$ If all coefficients (in the table) of the objective function are non-negative. $\endgroup$ – callculus Feb 25 '18 at 14:55

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.