1
$\begingroup$

$\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

2 Answers 2

1

$\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.

  • 0
    Your basis columns(or variables) are those canonical unit vector, i.e. (1 0) (0 1) - excluding the first row. $A$nd remember you set these basic variables to zero? So I do a row operation.2012-03-04
2

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.

  • 0
    @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.)2012-02-24