- Foundation
- About 16 min
- 5 practice questions
The corner-point method for bounded regions
Solve a linear programming problem whose feasible region is bounded: list its corner points, evaluate the objective at each and pick the largest or smallest value.
If something looks wrong, please tell us.
Once the feasible region is drawn, there are infinitely many feasible plans. Checking them one by one is impossible. A remarkable fact rescues us: for a linear objective, the best plan is always found at a corner of the region. So instead of infinitely many points we test only a handful. This lesson states that fact and uses it to solve complete problems.
Why the corners are enough
Take Z = 500x + 300y. The points where Z equals a fixed number, say 3000, form a straight line, and lines for different values of Z are all parallel. As the value of Z increases, the line slides parallel to itself away from the origin. The largest value of Z on the region is reached when the sliding line is about to leave the region, and a straight line leaves a polygon at a corner (or along a whole edge). The same holds for the smallest value.
Corner point theorem: if the feasible region is bounded and not empty, Z = px + qy has a maximum and a minimum on it, and each occurs at a corner point of the region.
The corner-point method
- Formulate the problem and draw the feasible region.
- Find every corner point: solve boundary lines in pairs and keep only feasible intersections.
- Evaluate Z at each corner, preferably in a table.
- The largest value is the maximum and the smallest is the minimum. State the point(s) where it occurs and answer in the words of the problem.
Worked example 1: the carpenter's best plan
From the previous lesson: maximise Z = 500x + 300y subject to 3x + y ≤ 30, x + 2y ≤ 20, x ≥ 0, y ≥ 0. The two lines meet where x = 20 − 2y, so 3(20 − 2y) + y = 30, giving 60 − 5y = 30, y = 6 and x = 8. The intercept (10, 0) of the carpentry line and the intercept (0, 10) of the polishing line are feasible; the other intercepts (0, 30) and (20, 0) are not.
| Corner | Z = 500x + 300y |
|---|---|
| (0, 0) | 0 |
| (10, 0) | 5000 |
| (8, 6) | 4000 + 1800 = 5800 |
| (0, 10) | 3000 |
The maximum profit is ₹5800, made by producing 8 tables and 6 chairs a week. Notice that the best plan uses both resources fully: 3 × 8 + 6 = 30 carpentry hours and 8 + 12 = 20 polishing hours.
Worked example 2: maximum and minimum on one region
Find the maximum and minimum of Z = 3x + 2y subject to x + y ≥ 4, x + 2y ≤ 12, x ≤ 6, x ≥ 0, y ≥ 0. The origin breaks x + y ≥ 4, so the region does not contain it. Intersections that pass every test: (4, 0), (6, 0), (6, 3) from x = 6 and x + 2y = 12, (0, 6) and (0, 4). The intersection of x + y = 4 with x + 2y = 12 is (−4, 8), and with x = 6 it is (6, −2); both break non-negativity and are rejected.
| Corner | Z = 3x + 2y |
|---|---|
| (4, 0) | 12 |
| (6, 0) | 18 |
| (6, 3) | 24 |
| (0, 6) | 12 |
| (0, 4) | 8 |
Maximum 24 at (6, 3), minimum 8 at (0, 4). A common slip is to write the minimum as 0, as if the origin were always available.
Worked example 3: the investment
Maximise Z = 0.08x + 0.10y subject to x + y ≤ 50, x ≥ 10, y ≤ 30, x ≥ 0, y ≥ 0 (in thousands of rupees). The corners are (10, 0), (50, 0), (20, 30) where y = 30 meets x + y = 50, and (10, 30). The values of Z are 0.8, 4, 1.6 + 3 = 4.6 and 0.8 + 3 = 3.8. The best return is 4.6 thousand, that is ₹4,600 a year, by putting ₹20,000 in A and ₹30,000 in B: put as much as allowed into the better scheme and the rest into the other.
Slips to avoid
- Including an intersection that breaks another constraint, such as (20, 0) in example 1.
- Forgetting corners on the axes, or assuming the origin is always a corner.
- Stopping after the first corner that "looks" best: evaluate them all, because neighbouring values can be close (25 and 26 are only 1 apart in the check below).
Key takeaways: on a bounded feasible region the optimum of a linear objective is at a corner. List the feasible corners, tabulate Z, pick the largest or smallest, and translate the answer back into the story.
Check your understanding
-
1. What is the maximum of Z = 4x + 3y subject to x + y ≤ 8, 2x + y ≤ 12, x ≥ 0, y ≥ 0?
- 24
- 28
- 32
- 36
Show answer
Answer: B. The lines x + y = 8 and 2x + y = 12 meet at x = 4, y = 4. Corners: (0, 0), (6, 0), (4, 4), (0, 8). Z = 0, 24, 28, 24. The maximum is 28 at (4, 4). 32 comes from the infeasible point (8, 0), which breaks 2x + y ≤ 12.
-
2. A bounded feasible region has corners (0, 2), (4, 0), (5, 3) and (1, 5). What is the minimum of Z = 2x − y on it?
- −3
- −2
- 0
- 7
Show answer
Answer: A. Evaluate at each corner: (0, 2) gives −2, (4, 0) gives 8, (5, 3) gives 7, (1, 5) gives 2 − 5 = −3. The smallest is −3, at (1, 5). The origin is not a corner here, so 0 is not a candidate.
-
3. What is the minimum of Z = x + 3y subject to x + y ≥ 2, x ≤ 4, y ≤ 3, x ≥ 0, y ≥ 0?
- 0
- 6
- 2
- 4
Show answer
Answer: C. The origin breaks x + y ≥ 2, so it is not feasible and 0 is not possible. Corners: (2, 0), (4, 0), (4, 3), (0, 3), (0, 2), giving Z = 2, 4, 13, 9, 6. The minimum is 2 at (2, 0).
-
4. If the feasible region of an LPP is bounded (and not empty), then the maximum of Z = px + qy:
- may not exist
- always occurs at the origin
- occurs only at the centre of the region
- exists and occurs at a corner point
Show answer
Answer: D. The corner point theorem: on a bounded feasible region a linear objective has both a maximum and a minimum, and each is attained at a corner point (possibly at two adjacent corners and the edge between them). The origin is a corner only if it is feasible.
-
5. What is the maximum of Z = 5x + 2y subject to x + 2y ≤ 10, 3x + y ≤ 15, x ≥ 0, y ≥ 0?
- 26
- 25
- 10
- 30
Show answer
Answer: A. Solve x + 2y = 10 and 3x + y = 15: x = 10 − 2y, so 30 − 6y + y = 15, y = 3 and x = 4. Corners (0, 0), (5, 0), (4, 3), (0, 5) give Z = 0, 25, 26, 10. The maximum is 26 at (4, 3), just above the 25 at (5, 0), so check every corner.
Sign in to keep track of the lessons you finish.