Feasible regions
Feasible Regions
The feasible region is the set of all points that satisfy every constraint of the problem.
In graphical linear programming, it is the overlap of all half-planes.
Definition
For constraints:
\[g_i(x)\le b_i,\qquad i=1,\ldots,m\]and sign restrictions:
\[x\ge 0\]the feasible region is:
\[S=\{x\mid g_i(x)\le b_i\text{ for all }i,\ x\ge 0\}\]For a two-variable LP, $S$ is drawn in the $x_1x_2$-plane.
Feasible Point
A point is feasible if it belongs to the feasible region.
That means it satisfies every constraint.
A point that violates even one constraint is not feasible.
Example
Consider:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[-x_1+x_2\le 3\] \[x_1,x_2\ge 0\]The point $(2,2)$ is feasible because:
\[2+2(2)=6\le 10\] \[2(2)+2=6\le 16\] \[-2+2=0\le 3\]and:
\[2\ge 0, \qquad 2\ge 0\]The point $(9,2)$ is not feasible because:
\[9+2(2)=13>10\]It violates the first constraint.
Geometry
Each inequality gives a half-plane.
The feasible region is:
\[\text{half-plane 1}\cap\text{half-plane 2}\cap\cdots\cap\text{half-plane m}\]Because half-planes are convex, their intersection is convex.
Therefore, LP feasible regions are convex.
Convex Meaning
If $x$ and $y$ are feasible, then every point on the line segment between them is feasible.
That is:
\[\alpha x+(1-\alpha)y\in S\]for every:
\[0\le \alpha\le 1\]This is why LP feasible regions have no holes or curved inward dents.
Boundary
The boundary of a feasible region is made from active constraint lines.
A constraint is active at a point if it holds as equality.
Example:
At a point satisfying:
\[x_1+2x_2=10\]the constraint:
\[x_1+2x_2\le 10\]is active.
Vertices
A vertex is a corner of the feasible region.
In two dimensions, vertices usually occur where two boundary lines intersect.
Example:
The intersection of:
\[x_1+2x_2=10\]and:
\[2x_1+x_2=16\]is:
\[\left(\frac{22}{3},\frac{4}{3}\right)\]This point is a vertex if it satisfies all other constraints.
Bounded Feasible Region
A feasible region is bounded if it does not extend infinitely.
In two dimensions, a bounded feasible region is a polygon contained inside some large circle.
A bounded feasible region can have:
- one optimal vertex
- multiple optimal points along an edge
- no unique optimum if the objective is constant on a region
But if it is nonempty, a linear objective always has a finite maximum and minimum on a bounded closed polygon.
Unbounded Feasible Region
A feasible region is unbounded if it extends infinitely in at least one direction.
This does not automatically mean the LP is unbounded.
The LP is unbounded only if the objective improves forever along an unbounded feasible direction.
Empty Feasible Region
If no point satisfies all constraints, the feasible region is empty.
Then the LP is infeasible.
Example:
\[x_1\ge 2\] \[x_1\le 1\]No point can satisfy both.
Feasible Region vs Objective
The feasible region depends only on constraints.
The objective function does not change the feasible region.
The objective function only decides which feasible point is best.
Checklist
You understand feasible regions if you can:
- test whether a point is feasible
- draw the overlap of several half-planes
- identify active constraints
- identify vertices
- distinguish bounded, unbounded, and empty feasible regions
- explain why feasibility is separate from optimality
See Also
- Feasible Sets
- Plotting Linear Inequalities
- Vertex Optimality
- Graphical Infeasibility
- Graphical Unboundedness
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.