Unbounded, Infeasible, and Degenerate LPs

A linear program is unbounded if its objective can be made arbitrarily large (for maximization) or arbitrarily small (for minimization) by moving through feasible points. No finite optimum exists.

Unboundedness requires two ingredients working together:

1. A recession direction $\mathbf{d}$ along which the feasible region extends to infinity -- that is, if $\mathbf{x}$ is feasible then $\mathbf{x} + t\mathbf{d}$ remains feasible for every $t \geq 0$.
2. An improving direction: $\mathbf{c}^T \mathbf{d} > 0$ for maximization (or $\mathbf{c}^T \mathbf{d} < 0$ for minimization).

If both hold, then walking along the ray $\mathbf{x} + t\mathbf{d}$ from any feasible point increases the objective without bound.

For example, consider $\max z = x_1 + x_2$ subject to $x_1, x_2 \geq 0$ (no upper bounds). The direction $\mathbf{d} = (1, 1)$ keeps both coordinates non-negative, and $\mathbf{c}^T \mathbf{d} = 1 + 1 = 2 > 0$. So $z$ grows by $2$ per unit step and the LP is unbounded.

A bounded feasible region (a polytope) can never produce an unbounded LP -- unboundedness requires an unbounded feasible region.