Detecting Unboundedness During Simplex

Recognizing when a simplex tableau reveals an unbounded linear program: if the entering column contains no strictly positive entry, no leaving variable exists and the objective can be improved without limit.

Step 1 of 157%

Tutorial

The Unboundedness Criterion

Some linear programs allow the objective to be increased without limit while remaining feasible. We call such an LP unbounded, and it has no optimal solution. The simplex method detects this through a single test on the tableau.

At each iteration of the simplex method on a maximization problem:

Pick the entering variable: the column with the most negative entry in the $z$ -row.
Run the ratio test: among rows with a positive entry $a_{ij}$ in the pivot column, compute $b_i / a_{ij}$ and pick the minimum to determine the leaving variable.

Unboundedness rule. If the pivot column contains no positive entries -- every $a_{ij}$ is zero or negative -- then no leaving variable can be selected and the LP is unbounded.

For example, consider the tableau

\begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & -2 & 1 & 1 & 0 & 4 \\ s_2 & -1 & 3 & 0 & 1 & 6 \\ \hline z & -5 & -2 & 0 & 0 & 0 \end{array}

The most negative entry in the $z$ -row is $-5$ , so $x_1$ enters. The $x_1$ column entries are $-2$ and $-1$ -- both nonpositive. No pivot is possible, so the LP is unbounded.