- Foundation
- About 18 min
- 5 practice questions
The corner point method for bounded regions
Use the fundamental theorems of linear programming to solve LPPs with bounded feasible regions by evaluating the objective function at the corner points.
If something looks wrong, please tell us.
A feasible region contains infinitely many points, so we cannot test them all. Two theorems, stated here without proof as in the textbook, reduce the search to a handful of points: the corners. This gives the corner point method.
The two theorems
- Theorem 1. Let R be the feasible region (a convex polygon) of an LPP and Z = ax + by the objective function. When Z has an optimal value (maximum or minimum), subject to linear constraints, this optimal value must occur at a corner point (vertex) of R.
- Theorem 2. If R is bounded, then Z has both a maximum and a minimum value on R, and each of these occurs at a corner point of R.
Why corners? Z = ax + by is linear, so along any straight segment it changes steadily in one direction (or stays constant). Its largest and smallest values on a segment are therefore at the ends. Pushing this idea from edges to the whole polygon leads to the corners.
Bounded feasible region: evaluate Z at every corner point. The largest value is the maximum and the smallest is the minimum.
The corner point method (bounded region)
- Draw the feasible region
- Find the coordinates of all corner points
- Evaluate Z = ax + by at each corner
- Largest value M = maximum; smallest value m = minimum
Worked examples
Worked example 1: the tailor problem solved
Maximise Z = 100x + 180y subject to 2x + 3y ≤ 60, x + 2y ≤ 35, x, y ≥ 0. From the previous lesson the region is bounded with corners (0, 0), (30, 0), (15, 10) and (0, 17.5).
| Corner point | Value of Z (₹) |
|---|---|
| (0, 0) | 0 |
| (30, 0) | 3000 |
| (15, 10) | 3300 (maximum) |
| (0, 17.5) | 3150 |
The maximum profit is ₹3300, obtained by making 15 shirts and 10 kurtas. This confirms the guess in lesson 1 and proves that no other plan does better. (Here the best corner has whole-number coordinates, as a real production plan needs.)
Worked example 2: maximum and minimum together
Find the maximum and minimum of Z = 3x + 5y subject to x + 2y ≥ 4, x + y ≤ 6, x ≤ 4, x ≥ 0, y ≥ 0. The region lies above the line x + 2y = 4, below x + y = 6 and to the left of x = 4, in the first quadrant. Its corners are: (4, 0) where x + 2y = 4 meets the x-axis; (4, 2) where x = 4 meets x + y = 6; (0, 6) where x + y = 6 meets the y-axis; and (0, 2) where x + 2y = 4 meets the y-axis. The region is bounded.
| Corner point | Value of Z |
|---|---|
| (4, 0) | 12 |
| (4, 2) | 22 |
| (0, 6) | 30 (maximum) |
| (0, 2) | 10 (minimum) |
So the maximum is 30 at (0, 6) and the minimum is 10 at (0, 2). Note that the origin is not a corner here: it does not satisfy x + 2y ≥ 4.
Worked example 3: a quick one
Maximise Z = 2x + 5y subject to x + y ≤ 5, y ≤ 3, x, y ≥ 0. Corners: (0, 0); (5, 0); (2, 3), where y = 3 meets x + y = 5; (0, 3). Values: 0, 10, 4 + 15 = 19, 15. Maximum 19 at (2, 3).
Points to watch
- List every corner, including those on the axes and those where a constraint other than an axis cuts the region.
- Check each corner satisfies all constraints; an intersection point outside the region is not a corner.
- Show the table of Z values; it is the proof of your answer.
- State both the optimal value and where it occurs (the values of x and y).
Key takeaways
- Theorem 1: an optimal value, when it exists, occurs at a corner point.
- Theorem 2: on a bounded region, Z has both a maximum and a minimum, at corners.
- Corner point method: find corners, tabulate Z, read off the largest and smallest values.
- The origin is a corner only when it satisfies every constraint.
Check your understanding
-
1. The corners of a bounded feasible region are (0, 0), (4, 0), (2, 4) and (0, 6). What is the maximum of Z = 3x + 2y?
- 12
- 14
- 16
- 18
Show answer
Answer: B. Z at the corners: 0, 12, 6 + 8 = 14, 12. The largest is 14, at (2, 4).
-
2. According to the fundamental theorem for a bounded feasible region R, the objective function Z = ax + by
- has a maximum but may not have a minimum on R
- has its optimal values only at interior points of R
- has both a maximum and a minimum on R, each at a corner point
- may have neither a maximum nor a minimum on R
Show answer
Answer: C. Theorem 2 says that if R is bounded, Z has both a maximum and a minimum on R and each occurs at a corner point.
-
3. The corners of a feasible region are (0, 2), (4, 0), (4, 2) and (0, 6). What is the minimum of Z = x + 3y?
- 6
- 10
- 18
- 4
Show answer
Answer: D. Z at the corners: 0 + 6 = 6, 4 + 0 = 4, 4 + 6 = 10, 0 + 18 = 18. The smallest is 4, at (4, 0).
-
4. Maximise Z = 2x + 5y subject to x + y ≤ 5, y ≤ 3, x ≥ 0, y ≥ 0. What is the maximum value?
- 19
- 15
- 10
- 25
Show answer
Answer: A. Corners: (0, 0), (5, 0), (2, 3), (0, 3). Values: 0, 10, 4 + 15 = 19, 15. The maximum is 19 at (2, 3). (25 would need y = 5, which breaks y ≤ 3.)
-
5. Assertion (A): For an LPP with a bounded feasible region, the maximum of Z can occur at a point inside the region without occurring at any corner point. Reason (R): Z = ax + by is linear, so on any segment it takes its largest and smallest values at the ends of the segment.
- 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: D. R is true. Because of it, an optimal value is always attained at a corner point (Theorems 1 and 2), so A is false. An interior point can share the optimal value only when a whole edge is optimal, and then the corners at its ends are optimal too.
Sign in to keep track of the lessons you finish.