The Four Terminal Outcomes

The same four outcomes stated as conditions on $max\{c^{\mathsf{T}}x:x\in F\}$, with $F=\{x:Ax\le b,x\ge 0\}$.

Infeasible. $F=\mathrm{\varnothing }$. No reference to $c$ appears, which is the algebraic form of the rule that feasibility is decided by the constraints alone.

Unbounded. $F\ne \mathrm{\varnothing }$ and there exists a recession direction $d$ of $F$ with . Both conjuncts are required: a recession direction alone says the region is unbounded, and alone is meaningless without a direction the region actually admits.

Unique optimum. The optimal value $z^{\ast }$ is finite and $\{x\in F:c^{\mathsf{T}}x=z^{\ast }\}$ is a single point, necessarily an extreme point.

Multiple optima. $z^{\ast }$ is finite and the optimal set is a face of dimension at least one.

In the simplex method these appear as terminations rather than as conditions to check: no feasible starting basis signals infeasibility, and an entering column whose direction has no positive component signals unboundedness, since no ratio limits the step. A zero reduced cost on a nonbasic variable at an optimal basis signals multiple optima.

This form survives into any number of variables, which the geometric form does not.

Take the region

which is nonempty and unbounded. It contains $(0,t)$ for every $t\ge 0$. Holding it fixed, change only the objective.

Maximise $x_2$. The direction $d=(0,1)$ keeps you in $F$ forever and . The program is unbounded.

Minimise $x_1+x_2$. The objective is nonnegative on $F$ and equals $0$ at the feasible point $(0,0)$. The optimum is $0$, attained once. Unique optimum, on an unbounded region.

Maximise $x_2-x_1$. Along $(0,1)$ the objective improves without limit, so this is unbounded again, but now consider instead minimising $x_2-x_1$ subject to the same constraints plus $x_1\le 3$. The constraint $x_1-x_2\le 1$ is parallel to the objective $x_2-x_1$, so the objective is constant along that boundary and every point of it attains the minimum $-1$. Multiple optima.

And for the fourth case, add $x_1\ge 5$ to the original constraints alongside $x_1\le 3$. No point satisfies both, so $F$ becomes empty: infeasible, regardless of which objective is attached.

The region was doing very little of the work. Three of these four verdicts turned on the objective.

Not infeasible: constraints that only look contradictory. $x_1+x_2\ge 10$ with $x_1\le 2$ and $x_2\le 2$ is genuinely infeasible, since . But $x_1+x_2\ge 10$ with $x_1\le 2$ alone is perfectly feasible, take $(2,8)$. Pairwise inspection is not a feasibility test; the constraints have to be considered together.

Not unbounded: an unbounded region with a finite optimum. Minimising $x_1+x_2$ over $x_1-x_2\le 1$, $x_1,x_2\ge 0$ has optimal value $0$ at the origin, though the region runs on forever. The feasible-region unit works this case through in full; the point to carry here is that the region's unboundedness never entered the verdict.

Not multiple optima: two corners with close values. Corners valued $15.98$ and $16.01$ are not a tie, and no amount of rounding makes them one. Multiple optima require exact equality along a face, which comes from parallelism between the objective and a binding constraint.

Not a unique optimum: a single corner reported from a degenerate basis. A solver may return one point while a whole edge is optimal, because it stopped at the first optimal basis it reached. The report says what the algorithm found, not how large the optimal set is; a zero reduced cost on a nonbasic variable is the signal to look further.

The fastest way to get these classifications wrong is to decide them from the shape of the feasible region. The region is settled by the constraints; three of the four outcomes also depend on the objective.

Bounded region does not mean unique optimum. The worked example above has a bounded region, a quadrilateral, and infinitely many optima. Boundedness guarantees that a finite optimum exists and is attained. It says nothing about how many points attain it.

Unbounded region does not mean unbounded program. This is the reverse error and it is thoroughly worked through in the feasible-region unit, which shows one fixed unbounded region yielding a finite optimum under one objective and no finite optimum under another. Treat that result as settled here and carry the consequence: an unbounded region is a necessary condition for an unbounded program, never a sufficient one.

Empty region does mean infeasible, and this is the case that is a property of the region alone. Infeasibility is decided by the constraints alone, which is exactly why it is checked first and why bringing the objective into that check is wasted work at best.

So the useful summary is a division of labour. The constraints decide feasibility outright. The constraints decide which directions are available. The objective decides what happens along those directions, and whether the optimum is one point or many. A learner who classifies regions fluently and then reads outcomes off them will be right about infeasibility and unreliable about everything else.

The terminal outcome of a linear program can be read off the feasible region: an unbounded region means an unbounded program, and a bounded region means a unique optimum.