Unboundedness in Simplex

Simplex detects unboundedness when an improving entering variable can increase forever without violating nonnegativity.

Test

If $\bar c_j<0$ and $u=B^{-1}A_j$ has $u_i\le0$ for all $i$, then no leaving variable exists.

Why

$x_B(\theta)=x_B-\theta u$ remains nonnegative for every $\theta\ge0$.

Objective

$c^Tx(\theta)=c^Tx+\theta\bar c_j\to-\infty$ for minimization.

Report

The problem is unbounded below; no finite minimizer exists.

Checklist

Do not declare unbounded from negative reduced cost alone; also check that no positive $u_i$ exists.

See Also

• Graphical Unboundedness
• Minimum Ratio Test

Exam checkpoint

For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.