- Foundation
- About 15 min
- 5 practice questions
Systems of inequalities and the feasible region
Combine several inequalities into one common region, find its corner points by solving pairs of boundary lines, and recognise bounded, unbounded and empty regions.
If something looks wrong, please tell us.
A real problem never has just one limit. A workshop has limited carpentry hours and limited polishing hours, and it cannot make a negative number of tables. Each limit is a half-plane, and a plan is acceptable only if it obeys all of them at once. The set of acceptable plans is the heart of every linear programming problem, so in this lesson we learn to find it and to locate its corners.
The common region
A point satisfies a system of inequalities when it satisfies every one of them. Graphically, the solution set is the overlap of all the half-planes. In linear programming this overlap is called the feasible region, and each point in it is a feasible solution. A point outside it breaks at least one condition and is infeasible. The feasible region of linear inequalities always has straight edges and no dents: it is a convex polygon or a convex region that runs off to infinity.
Corner points
A corner point (vertex) of the feasible region is a point where two boundary lines meet and every other inequality is satisfied. To find corners, solve the boundary equations two at a time, then test each intersection in all the inequalities. Intersections that break a condition lie outside the region and are thrown away; this is the most common mistake in the whole topic.
Worked example 1: a bounded region
Find the feasible region and corners of x + y ≤ 6, x + 2y ≤ 8, x ≥ 0, y ≥ 0. The line x + y = 6 has intercepts (6, 0) and (0, 6); the line x + 2y = 8 has intercepts (8, 0) and (0, 4). The origin satisfies both, so the region lies on the origin side of each line, inside the first quadrant. The two lines meet where (x + 2y) − (x + y) = 8 − 6, so y = 2 and x = 4.
| Intersection of | Point | Check the other constraints | Corner? |
|---|---|---|---|
| x = 0 and y = 0 | (0, 0) | 0 ≤ 6, 0 ≤ 8 | yes |
| x + y = 6 and y = 0 | (6, 0) | x + 2y = 6 ≤ 8 | yes |
| x + 2y = 8 and y = 0 | (8, 0) | x + y = 8, not ≤ 6 | no |
| x + 2y = 8 and x = 0 | (0, 4) | x + y = 4 ≤ 6 | yes |
| x + y = 6 and x = 0 | (0, 6) | x + 2y = 12, not ≤ 8 | no |
| x + y = 6 and x + 2y = 8 | (4, 2) | x ≥ 0, y ≥ 0 | yes |
The feasible region is the quadrilateral with corners (0, 0), (6, 0), (4, 2) and (0, 4). It is bounded: it fits inside a circle.
Worked example 2: an unbounded region
Consider x + y ≥ 4, x + 3y ≥ 6, x ≥ 0, y ≥ 0. Intercepts: (4, 0) and (0, 4) for the first line, (6, 0) and (0, 2) for the second. The origin fails both inequalities, so the region lies on the far side of both lines. The lines meet where 2y = 2, so y = 1 and x = 3. Testing: (0, 4) gives 0 + 12 = 12 ≥ 6, so it is a corner; (6, 0) gives 6 ≥ 4, so it is a corner; (4, 0) and (0, 2) fail one condition each. The corners are (0, 4), (3, 1) and (6, 0), and the region stretches without end upwards and to the right. It is unbounded.
Worked example 3: an empty region
Consider x + 2y ≤ 4, 2x + 3y ≥ 12, x ≥ 0, y ≥ 0. The first three conditions give the triangle with corners (0, 0), (4, 0) and (0, 2). At those corners 2x + 3y equals 0, 8 and 6, all less than 12, and since the triangle has no dents, every point of it has 2x + 3y less than 12. So no point satisfies all four conditions: the feasible region is empty, and the problem is called infeasible.
| Type of region | What it looks like | Example from this lesson |
|---|---|---|
| Bounded | a closed polygon | x + y ≤ 6, x + 2y ≤ 8, x, y ≥ 0 |
| Unbounded | runs off to infinity in some direction | x + y ≥ 4, x + 3y ≥ 6, x, y ≥ 0 |
| Empty | no point obeys every condition | x + 2y ≤ 4, 2x + 3y ≥ 12, x, y ≥ 0 |
A corner point is an intersection of two boundary lines that satisfies every constraint. Find all intersections, then reject any that break a constraint.
Key takeaways: the feasible region is the overlap of all the half-planes. Its corners come from solving boundary lines in pairs and keeping only the points that obey every inequality. A region can be bounded, unbounded or empty, and you should always say which before going further.
Check your understanding
-
1. What are the corner points of the region x + y ≤ 5, x ≤ 3, x ≥ 0, y ≥ 0?
- (0, 0), (5, 0), (3, 2), (0, 5)
- (0, 0), (3, 0), (3, 2), (0, 5)
- (0, 0), (3, 0), (0, 5)
- (0, 0), (3, 0), (3, 5), (0, 5)
Show answer
Answer: B. The line x = 3 meets x + y = 5 at (3, 2). (5, 0) is not a corner because it breaks x ≤ 3, and (3, 5) breaks x + y ≤ 5. The region is the quadrilateral (0, 0), (3, 0), (3, 2), (0, 5).
-
2. Where do the lines 2x + y = 10 and x + y = 7 meet?
- (4, 3)
- (2, 6)
- (5, 2)
- (3, 4)
Show answer
Answer: D. Subtract the second equation from the first: x = 3. Then y = 7 − 3 = 4. Check: 2 × 3 + 4 = 10. (4, 3) gives 2 × 4 + 3 = 11, so it is not on the first line.
-
3. Which point is NOT in the feasible region of 2x + y ≤ 8, x + y ≤ 5, x ≥ 0, y ≥ 0?
- (3, 2)
- (1, 4)
- (4, 1)
- (2, 2)
Show answer
Answer: C. (4, 1) gives 2 × 4 + 1 = 9, which is more than 8, so it breaks the first constraint. (3, 2) gives 8 and 5, (1, 4) gives 6 and 5, (2, 2) gives 6 and 4, all allowed (points on a boundary are allowed).
-
4. The region x + y ≥ 3, x ≥ 0, y ≥ 0 is:
- unbounded
- a bounded triangle
- empty
- a single point
Show answer
Answer: A. The region is the part of the first quadrant on or beyond the line through (3, 0) and (0, 3). Points such as (100, 0) or (0, 100) belong to it, so it cannot be enclosed in a circle: it is unbounded. It has two corners, (3, 0) and (0, 3).
-
5. Together with x ≥ 0 and y ≥ 0, which pair of inequalities has NO feasible point?
- x + y ≤ 3 and x ≥ 1
- x + y ≥ 3 and x ≤ 1
- x ≤ 2 and y ≥ 5
- x + y ≤ 3 and x + y ≥ 4
Show answer
Answer: D. x + y cannot be at most 3 and at least 4 at the same time, so that region is empty. The others have points: (1, 0) for x + y ≤ 3 with x ≥ 1, (0, 3) for x + y ≥ 3 with x ≤ 1, and (0, 5) for x ≤ 2 with y ≥ 5.
Sign in to keep track of the lessons you finish.