2

Given the following tableau for a max LP

\begin{array}{|c|c|c|c|} \hline & \text{z} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & \text{RHS} \\ \hline \text{z} & 1 & c_1 & 0 & c_3 & 0 & 0 & 0 & 13\\ \hline x_2 & 0 & -4 & 1 & a_1 & 0 & a_2 & 0 & \text{b}\\ \hline x_4 & 0 & -1 & 0 & -5 & 1 & -1 & 0 & 3\\ \hline x_6 & 0 & a_3 & 0 & 3 & 0 & -4 & 1 & 2\\ \hline \end{array}

I trying to understand how this tableau works.

First of all, the tableau corresponds to the basic solution given by

$ {\bf x} = (0,b,0,3,0,6)$ Meaning that this is feasible, a BFS, only if $b \geq 0$ for which otherwise $(b\lt0)$ would be infeasible. If I want it to be degenerate, then $ b \gt 0$.

What condition do we have to impose on the unknowns for the problem to be unbounded?

Now, if the current solution is feasible but the objective function can be improved by replacing $x_6$ as basic variable by $x_3$, what condition show we impose on the unknowns?

try:

First of all, we need $b \geq 0$ for feasibility. If we want $x_3$ to leave the basis, we pivot on the column given by the vector $(c_3, a_1, -5, 3)^T$. For the ratio test, we need to find $\min \{c_3/a_1, -5/3, 2/4\}$ meaning that $a_1 \neq 0$ for which otherwise cannot perform the min ratio test, and $c_3$ can be anything. Is this correct?

Jessie
  • 1,463
Mikey Spivak
  • 871

1 Answers1

2

You should not include negative numbers in the ratio test ($-5/3$), because creating a pivot in the corresponding row would give a negative variable in the basis. Before you can start the pivot test for the column $x_3$, you first have to check if $c_3 < 0$. My ratio test is a bit different than yours: $\min\{b/a_1, 2/3\}$ if $a_1 > 0$, and just $2/3$ if $a_1 \leq 0$. In both cases, the ratio is finite, so after pivoting, $z$ is still finite.

More interesting is the column for $x_1$. If $c_1 < 0$ but $a_3 \leq 0$, you should add $x_1$ to the basis, but there is no term to be included in the ratio test. That means that the constraints do not limit $x_1$. Since $c_1 < 0$, the objective value can be made arbitrarily large.

LinAlg
  • 19,822