Skip to content

Feasible Region

Definition

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

F={x ⁣:x satisfies all constraints}.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 xs,xt≥0x_s,x_t\ge0 keep the first quadrant. The shaded pentagon FF 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.

Drag the decision point: it is feasible exactly when it satisfies every constraint, including xs,xt≥0x_s,x_t\ge0.

Each extra constraint intersects FF 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 FF when the constraint is ≤\le or ≥\ge, and the corner points of FF, 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={x ⁣:Ax≤b, x≥0}F=\{\boldsymbol{x}\colon\boldsymbol{A}\boldsymbol{x}\le \boldsymbol{b},\ \boldsymbol{x}\ge0\}. It is an intersection of half-planes in two dimensions, or a convex polyhedron in Rn\mathbb{R}^n; an LP feasible set may be bounded, unbounded or empty.

  • x1,x2≥0x_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

Sources

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

Last updated: 20 October 2026 03:02