Feasible region — reading constraints as geometry
Understand, through a 2D diagram and hand calculation, how the intersection of inequalities becomes the "map of possible plans".
Describing the feasible region in words
For readers who cannot see the figure, here is the feasible region of the running example in plain language:
- Location: Only the interior of the first quadrant (
x ≥ 0andy ≥ 0). - Vertices: A convex quadrilateral with corners at
(0, 0),(8, 0),(6, 4), and(0, 7). - Boundary: The bottom and left sides are the coordinate axes; the right side is
2x + y = 16; the top side isx + 2y = 14.
The basic structure stays the same as more constraints are added: each new boundary line carves off a corner, and the feasible region remains a convex polygon.
An inequality chooses "which side of the line"
2x + y ≤ 16 means the side of the boundary line 2x + y = 16 where the expression is "at most that much". The same goes for x + 2y ≤ 14.
A single inequality splits the plane in two along its boundary line and keeps only one side. We call that one side a half-plane. The feasible region of an LP is therefore the intersection of several half-planes — the area allowed by every constraint simultaneously.
If you are not sure which side to choose, plug in the origin (0, 0). Whichever side makes the inequality true is the feasible side.
Draw each boundary line from its intercepts first
The fastest way to draw a boundary line is to find its x- and y-intercepts.
2x + y = 16 are (8, 0) and (0, 16)x + 2y = 14 are (14, 0) and (0, 7)In the actual feasible region, however, only the part that satisfies both constraints simultaneously remains.
Work it out 1
First, compute the intercepts yourself and fix the positions of the boundary lines in your head.
Find the x-intercept
On the boundary line 2x + y = 16, set y = 0. What is x?
Show hint
Substituting y = 0 gives 2x = 16, so x = 8. The x-intercept is (8, 0).
Find the y-intercept
On the boundary line x + 2y = 14, set x = 0. What is y?
Show hint
Substituting x = 0 gives 2y = 14, so y = 7. The y-intercept is (0, 7).
Feasibility check: "plug it in and see"
To decide whether a given point is feasible, substitute it into every constraint. For the point (5, 4), for example,
2×5 + 4 = 14 ≤ 165 + 2×4 = 13 ≤ 14so it is feasible. Going a step further and computing the slack (the leftover) lets you see which constraints are starting to bind.
Work it out 2
For a feasible point, compute the slack; for an infeasible point, compute how much it violates the constraint.
How much slack is there at (5, 4)?
Consider the point (x, y) = (5, 4). For the cutting stage and the finishing stage, enter the remaining hours for each.
Show hint
Cutting stage: 16 - (2×5 + 4) = 16 - 14 = 2 hours. Finishing stage: 14 - (5 + 2×4) = 14 - 13 = 1 hour.
By how much does (7, 3) violate?
At the point (x, y) = (7, 3), by how many hours does it exceed the cutting-stage constraint 2x + y ≤ 16?
Show hint
2×7 + 3 = 17, which exceeds the limit of 16 by 1 hour. This point is not feasible.
Intersections are vertex candidates
A point where two constraints meet with equality is a candidate vertex of the feasible region.
2x + y = 16x + 2y = 14Solving this 2-by-2 system gives the intersection of the two constraints.
Work it out 3
Solve for the intersection by hand — it will become a vertex candidate.
Solve the 2-by-2 system for the intersection
Solve the following system to find the intersection.
2x + y = 16x + 2y = 14Show hint
Multiply the first equation by 2 to get 4x + 2y = 32, then subtract the second to get 3x = 18, so x = 6. Substituting back gives y = 4.
Key takeaways from this chapter
- Each inequality represents a boundary line together with one of its sides.
- The feasible region is the set of points that satisfy all the constraints at once.
- The intersections of the boundary lines are the important vertex candidates when we later check for optimality.