- Foundation
- About 18 min
- 5 practice questions
The feasible region and its corner points
Graph the constraints of an LPP, identify the feasible region, feasible and infeasible solutions, tell bounded from unbounded regions, and find the corner points by solving pairs of boundary lines.
If something looks wrong, please tell us.
Every constraint of an LPP in two variables describes a half-plane. The points that satisfy all the constraints together form the feasible region. The answer to the problem lies in this region, and in fact at one of its corners. This lesson shows how to draw the region and find its corners.
Graphing one constraint
To graph ax + by ≤ c: (1) draw the boundary line ax + by = c through its intercepts (c/a, 0) and (0, c/b); (2) test a point not on the line, usually the origin. If (0, 0) satisfies the inequality, shade the side containing the origin; otherwise shade the other side. The boundary line is included because the inequality is ≤ (or ≥). The constraints x ≥ 0 and y ≥ 0 restrict us to the first quadrant.
Definitions
- Feasible region (solution region): the common region determined by all the constraints, including x ≥ 0 and y ≥ 0. The rest of the plane is the infeasible region.
- Feasible solution: any point inside or on the boundary of the feasible region.
- Infeasible solution: any point outside the feasible region.
- Optimal (feasible) solution: a feasible point that gives the optimal value of the objective function.
- Corner point (vertex): a point of the feasible region where two boundary lines intersect.
- Bounded region: one that can be enclosed in a circle. Otherwise the region is unbounded: it extends indefinitely in some direction.
Worked example 1: the tailor problem
Draw the feasible region for 2x + 3y ≤ 60, x + 2y ≤ 35, x ≥ 0, y ≥ 0. Line 2x + 3y = 60 meets the axes at (30, 0) and (0, 20); the origin satisfies 0 ≤ 60, so shade towards the origin. Line x + 2y = 35 meets the axes at (35, 0) and (0, 17.5); again shade towards the origin. The feasible region is the quadrilateral bounded by the axes and both lines. Its corner points are O(0, 0), A(30, 0) (where 2x + 3y = 60 meets the x-axis; note (35, 0) is outside the cloth constraint), C(0, 17.5) (where x + 2y = 35 meets the y-axis), and B, the intersection of the two lines.
Finding B. Solve 2x + 3y = 60 and x + 2y = 35. From the second, x = 35 − 2y. Substitute: 2(35 − 2y) + 3y = 60, so 70 − y = 60, y = 10, and x = 15. So B = (15, 10). The region OABC is bounded.
| Point | 2x + 3y ≤ 60? | x + 2y ≤ 35? | Feasible? |
|---|---|---|---|
| (10, 10) | 50 ✓ | 30 ✓ | Yes |
| (15, 10) | 60 ✓ | 35 ✓ | Yes (a corner) |
| (20, 10) | 70 ✗ | 40 ✗ | No |
| (0, 18) | 54 ✓ | 36 ✗ | No |
Worked example 2: an unbounded region
Draw the region for 2x + y ≥ 10, x + 2y ≥ 8, x ≥ 0, y ≥ 0 (the canteen problem). Line 2x + y = 10 passes through (5, 0) and (0, 10); the origin gives 0 ≥ 10, false, so shade away from the origin. Line x + 2y = 8 passes through (8, 0) and (0, 4); again shade away from the origin. The feasible region lies above and to the right of both lines and stretches without end: it is unbounded. Its corner points are (0, 10) on the y-axis, (8, 0) on the x-axis, and the intersection of the lines: from 2x + y = 10 and x + 2y = 8, doubling the second gives 2x + 4y = 16; subtracting the first gives 3y = 6, y = 2, x = 4. Corner (4, 2).
Finding the feasible region and its corners
- Draw each boundary line using its intercepts
- Shade the correct side of each (test the origin)
- Take the common region in the first quadrant
- Mark corners; solve pairs of line equations for their coordinates
- Note whether the region is bounded or unbounded
Bounded and unbounded feasible regions
-
Bounded
- Fits inside some circle
- A closed polygon
- Typical of ≤ constraints
- Example: the tailor problem
-
Unbounded
- Extends indefinitely
- Not closed on one side
- Typical of ≥ constraints
- Example: the canteen problem
A useful general fact: the feasible region of an LPP is always a convex region. Each constraint gives a half-plane, which is convex (the segment joining two of its points stays inside), and the intersection of convex sets is convex.
Key takeaways
- Each linear constraint is a half-plane; test the origin to choose the side.
- The feasible region is the common part, inside the first quadrant.
- Corner points are intersections of boundary lines that satisfy all constraints.
- Bounded regions fit in a circle; unbounded regions extend indefinitely.
- The feasible region is always convex.
Check your understanding
-
1. Which point lies in the feasible region of x + y ≤ 6, 2x + y ≤ 8, x ≥ 0, y ≥ 0?
- (3, 3)
- (5, 0)
- (1, 4)
- (0, 7)
Show answer
Answer: C. For (1, 4): 1 + 4 = 5 ≤ 6 and 2 + 4 = 6 ≤ 8, so it is feasible. (3, 3) gives 2x + y = 9 > 8; (5, 0) gives 10 > 8; (0, 7) gives x + y = 7 > 6.
-
2. Where do the boundary lines x + y = 6 and 2x + y = 8 intersect?
- (2, 4)
- (4, 2)
- (3, 3)
- (1, 5)
Show answer
Answer: A. Subtract the first from the second: x = 2. Then y = 6 − 2 = 4. Check: 2(2) + 4 = 8.
-
3. A feasible region is said to be bounded if
- it has exactly four corner points
- it lies in the first quadrant
- it contains the origin
- it can be enclosed within a circle
Show answer
Answer: D. By definition a feasible region is bounded if some circle encloses it; otherwise it extends indefinitely and is unbounded. Lying in the first quadrant is true of every LPP region and does not make it bounded.
-
4. Which system has an unbounded feasible region?
- x + y ≤ 4, x ≥ 0, y ≥ 0
- x + y ≥ 4, x ≥ 0, y ≥ 0
- x ≤ 3, y ≤ 2, x ≥ 0, y ≥ 0
- 2x + y ≤ 6, x + 2y ≤ 6, x ≥ 0, y ≥ 0
Show answer
Answer: B. x + y ≥ 4 in the first quadrant is everything on or above the line x + y = 4, which extends indefinitely. The other three regions are closed polygons.
-
5. Assertion (A): The feasible region of a linear programming problem is always a convex region. Reason (R): It is the intersection of half-planes, and each half-plane is convex.
- Both A and R are true, and R is the correct explanation of A
- Both A and R are true, but R is not the correct explanation of A
- A is true, but R is false
- A is false, but R is true
Show answer
Answer: A. If two points lie in every half-plane, the segment joining them also lies in every half-plane, because each is convex. So the intersection, the feasible region, is convex. R explains A.
Sign in to keep track of the lessons you finish.