# Solving LP from tableau

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4& x5 \\ -4& 2 & 0& -2 & 0& 3\\ 3 & 1 & 0 & -1& 1 & 3\\ 2 &0& 1 & 0& 0.5 & 2\\ \end{array}$$

When I learned about solving LP represented by the tableau in class, I thought I need to select the column that has negative value at the top. According to that, x3 is the only column that has -2 value. However, it's subsequent values -1 in row 1 and 0 in row 2 are neither positive, which I need it to pivot the row.

Am I missing something here?

The top row with z =-4, x1=2, x3=-2 is the cost function

-

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4& x5 \\ -4& 2 & 0& -2 & 0& 3\\ 3 & 1 & 0 & -1& 1 & 3\\ 2 &0& 1 & 0& 0.5 & 2\\ \end{array}$$

To begin with a bfs

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4 & x5 \\ -10& 0 & 0 & 0 & -2 & -3 \\ 3 & 1 & 0 & -1 & 1 & 3 \\ 2 & 0 & 1 & 0 &0.5 & 2 \\ \end{array}$$

Suppose we pick column4, then row 2 is most profitable

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4 & x5 \\ -2 & 0 & 4 & 0 & 0 & 5 \\ -1 & 1 & -2 & -1 & 0 & -1\\ 4 & 0 & 2 & 0 &1 & 4 \\ \end{array}$$

Now all cost are positive and we are done. Optimal value of z is -2.

=====

Did you miss your objective functions? And you need to find a basis(basic feasible solution) first.

-
The top row is the objective function. – John Feb 24 '12 at 15:58
OK. I edited my post. – FiniteA Feb 25 '12 at 0:51
+1: FiniteA is correct. I missed the need for finding a basic feasible solution first in my (now-deleted) answer. – Mike Spivey Feb 26 '12 at 3:34
What pivot did you choose to get bfs? How should I determine which pivot to choose? – John Feb 27 '12 at 4:25
Your basis columns(or variables) are those canonical unit vector, i.e. (1 0) (0 1) - excluding the first row. And remember you set these basic variables to zero? So I do a row operation. – FiniteA Mar 4 '12 at 8:58

Added: FiniteA's answer is the right one for this problem (the OP needs to put the problem in standard form, with a basic feasible solution, first, and then the difficulty goes away). I'm going to leave my answer up, though, for those who want to see what it means in general when there is no leaving variable.

Original answer: You've determined that $x3$ is the entering variable, and you're looking for a variable to leave the basis. The $-1$ in column $x3$, row $x1$, means that each unit increase in the value of $x3$ causes $x1$ to increase by one unit. The $0$ in column $x3$, row $x1$, means that each unit increase in the value of $x3$ has no effect on the value of $x2$. So letting $x3$ enter the basis doesn't force $x1$ or $x2$ ever to be negative (and thus infeasible). Therefore, you can increase $x3$ indefinitely without causing the current solution to go infeasible. Since each unit increase in the value of $x3$ causes the objective function value to drop by $2$ units, you can make the objective function go to $-\infty$ by continually increasing $x3$. In other words, your problem is unbounded.

In general, the inability to find a leaving variable, as here, means that the problem is unbounded.

-
how one can show the degeneracy in tableau method? As I remember the left-hand side should be 0, is this true? – com Feb 24 '12 at 17:00
@com: If one of the left-hand side values is $0$, then yes, the current solution exhibits degeneracy. You can also catch degeneracy in the previous iteration if there is a tie for the leaving basic variable. (The tie is what produces the $0$ on the left-hand side.) – Mike Spivey Feb 24 '12 at 17:04