Feasible Region¶

Definition¶

The feasible region is the set of all feasible solutions of a model:

F=\{\boldsymbol{x}\colon\boldsymbol{x}\text{ satisfies all constraints}\}.

For a two-variable LP it is obtained by intersecting the allowed half-planes and equality lines, including variable-domain restrictions.

Interpretation¶

The feasible region collects every decision that the constraints allow, before the objective is considered. The objective only chooses among these points; it cannot add new ones.

A shaded pentagon of points satisfying three constraint lines and the nonnegativity conditions, with a point outside it that violates all three constraints.

In the figure, each of the three constraints keeps the points on one side of its line, and $x_s,x_t\ge0$ keep the first quadrant. The shaded pentagon $F$ is what remains when all five conditions hold at once: the intersection of the allowed sides. The grey point outside breaks more than one condition, although breaking a single one would already exclude it.

Each extra constraint intersects $F$ with one more allowed side, so it can keep or shrink the region but never enlarge it; this is why a relaxation, which removes constraints, has a feasible region at least as large. Points on a boundary line belong to $F$ when the constraint is $\le$ or $\ge$ , and the corner points of $F$ , where boundary lines meet, are where the graphical method finds optima.

The region need not be a bounded shape like this pentagon. The requirements of the diet problem leave an unbounded region, and if the constraints contradict each other the region is the empty set: the model has no feasible solution at all.

Key Results¶

Removing a constraint cannot shrink the feasible region.
An empty feasible region means the model is infeasible.
An unbounded feasible region does not by itself imply an unbounded objective value.

Examples¶

For the illustrated upper-bound model, $F=\{\boldsymbol{x}\colon\boldsymbol{A}\boldsymbol{x}\le \boldsymbol{b},\ \boldsymbol{x}\ge0\}$ $0}$ . It is an intersection of half-planes in two dimensions, or a convex polyhedron in $\mathbb{R}^n$ ; an LP feasible set may be bounded, unbounded or empty.

$x_1,x_2\ge0$ restrict the region to the first quadrant.
The diet requirements define the intersection of calorie, vitamin, and feed-share half-planes.

Prerequisites¶

Feasible Solution

Sources¶

OR Modelling · Week 1

Aliases: feasible set, Feasible solution space, feasible space Symbols: real numbers

Last updated: 20 October 2026 03:02