The Feasible Region of a Linear Program

Before asking what the best plan is, ask whether any plan survives the restrictions at all. And if plans survive, whether they run on forever in some direction.

This matters before any solution method runs. An infeasible program has nothing to optimize, and an unbounded region is the situation in which an objective may have no finite best value. Knowing which case you are in tells you what to expect from a solver, and what a surprising answer means.

This unit assumes you can read a linear constraint and recognize which side of a line it allows.

Think of starting with the whole plane and applying constraints one at a time.

Each inequality draws a straight line and discards everything on one side of it. What remains after all the cuts is the feasible region: the points that survived every constraint.

Three consequences follow from the cuts being straight:

• The region has flat sides and straight edges. It never curves and never has a dent, because no straight cut can produce one.
• The region can be empty. If two constraints discard opposite halves with no overlap, nothing survives.
• The region can extend forever. Cuts limit directions, but a finite set of cuts need not close off every direction.

This is an informal picture. The definition that follows is what actually settles any particular case.

For a linear program with constraints $a_i^{\mathsf{T}}x\le b_i$ for $i=1,\dots ,m$, the feasible region is

Each single inequality $a_i^{\mathsf{T}}x\le b_i$ defines a half-space. $F$ is the intersection of all $m$ of them, together with any sign restrictions, which are themselves half-spaces such as $x_j\ge 0$.

A set of this form is a convex polyhedron. Convex means: if $x$ and $y$ both satisfy every constraint, so does every point on the segment between them. For $\lambda \in [0,1]$,

Three cases are possible, and they are determined by the constraints alone:

• $F$ is empty: no point satisfies every constraint. The program is infeasible.
• $F$ is bounded: $F$ is non-empty and fits inside some finite ball.
• $F$ is unbounded: $F$ is non-empty and extends without limit in at least one direction.

The objective function plays no part in this classification.

Each case is settled by checking the constraints, not by looking at the drawing above.

Bounded. $x_1+x_2\le 4$, $x_1\ge 0$, $x_2\ge 0$. Every feasible point has $0\le x_1\le 4$ and $0\le x_2\le 4$, because each variable is nonnegative and their sum is at most $4$. The region fits inside a finite ball, so it is bounded, and it is the triangle with corners $(0,0)$, $(4,0)$ and $(0,4)$.

Unbounded. $x_1-x_2\le 1$, $x_1\ge 0$, $x_2\ge 0$. The point $(0,t)$ satisfies all three for every $t\ge 0$, since $0-t=-t\le 1$. As $t$ may be arbitrarily large, no ball contains the region.

Empty. $x_1+x_2\le 1$, $x_1+x_2\ge 3$, $x_1\ge 0$, $x_2\ge 0$. The first two require $x_1+x_2$ to be at most $1$ and at least $3$ at once. No number is both, so no point is feasible.

Bounded, unbounded and empty are the three possibilities, and which one holds is a property of the constraints alone.

These two properties are often merged, but they answer different questions. The region is determined by the constraints; whether a best value exists also depends on the objective and the direction you optimize in.

Take the same unbounded region throughout:

A finite optimum exists. Minimise $x_1+x_2$. The objective is nonnegative on the region and equals $0$ at $(0,0)$, which is feasible. The minimum is $0$, attained, despite the region being unbounded.

No finite optimum exists. Maximise $x_2$ over the same region. The points $(0,t)$ are feasible for every $t\ge 0$, so the objective grows without limit. The program is unbounded.

The region did not change between these two cases. What changed was the objective.

The reliable order is: classify the region from the constraints first, then ask separately whether the objective attains a finite best value on it. An unbounded region is a necessary condition for an unbounded objective value, never a sufficient one.