Graphical unboundedness
Graphical Unboundedness
A graphical LP is unbounded when the objective can improve forever while staying feasible.
An unbounded feasible region alone is not enough.
The objective must improve along an unbounded feasible direction.
Feasible Region Unbounded
A feasible region is unbounded if it extends infinitely in at least one direction.
Example:
\[x_1\ge 0, \qquad 0\le x_2\le 1\]This is an infinite horizontal strip.
It extends forever as $x_1$ increases.
Objective Unbounded
Consider:
\[\max x_1+x_2\]subject to:
\[x_1\ge 0\] \[0\le x_2\le 1\]Take feasible points:
\[(t,1),\qquad t\ge 0\]The objective value is:
\[t+1\]As $t\to\infty$:
\[t+1\to\infty\]So the problem is unbounded above.
There is no finite maximum.
Minimization Unbounded Below
Consider:
\[\min -x_1\]subject to:
\[x_1\ge 0\]As $x_1\to\infty$:
\[-x_1\to -\infty\]So the problem is unbounded below.
There is no finite minimum.
Unbounded Region but Finite Optimum
An unbounded feasible region can still have a finite optimum.
Example:
\[\min x_1+x_2\]subject to:
\[x_1\ge 0, \qquad x_2\ge 0\]The feasible region is the first quadrant, which is unbounded.
But the minimum occurs at:
\[(0,0)\]with value:
\[0\]So the feasible region is unbounded, but the problem is not unbounded.
Direction Test
Let $d$ be a feasible direction along which we can move forever.
For maximization:
If:
\[c^Td>0\]then the objective grows forever.
For minimization:
If:
\[c^Td<0\]then the objective decreases forever.
Graphical Detection
To detect unboundedness graphically:
- draw the feasible region
- identify whether it extends infinitely
- draw the objective direction
- check whether the contour line can keep moving in the improvement direction while still touching the feasible region
If yes, the problem is unbounded.
Reporting the Result
For maximization unbounded above, write:
\[z^*=+\infty\]or say:
The objective is unbounded above; no finite maximum exists.
For minimization unbounded below, write:
\[z^*=-\infty\]or say:
The objective is unbounded below; no finite minimum exists.
Infeasible vs Unbounded
An unbounded LP must have feasible points.
An infeasible LP has no feasible points.
| Status | Feasible points? | Finite optimum? |
|---|---|---|
| Infeasible | no | no |
| Unbounded | yes | no |
| Finite optimum | yes | yes |
Common Mistake
Do not say a problem is unbounded just because the feasible region is unbounded.
First check the objective direction.
Checklist
You understand graphical unboundedness if you can:
- identify unbounded feasible regions
- test whether the objective improves forever
- distinguish unbounded feasible set from unbounded objective
- report $+\infty$ for max or $-\infty$ for min
- distinguish unboundedness from infeasibility
See Also
- Feasible Regions
- Cost Vector and Direction of Improvement
- Graphical Infeasibility
- Bounded Infeasible and Unbounded Problems
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.