Lesson 7 of 9 · 8 min
Unbounded feasible regions
NCERT §12.2.2, Example 4
To buy ingredients, the club can order two kinds of pack. It needs enough sugar and butter, at the least cost. What if the plans never run out?
The lesson in notes
In short
On an unbounded region the largest or smallest corner value might not be a true maximum or minimum, because Z can keep changing as the region runs on.
The test for M (the largest corner value): if no feasible point lies in the open half plane ax + by > M, then M is the maximum. If some feasible point does, Z has no maximum.
The test for m (the smallest corner value): if no feasible point lies in the open half plane ax + by < m, then m is the minimum. If some feasible point does, Z has no minimum.
Example: minimise Z = −50x + 20y with 2x − y ≥ −5, 3x + y ≥ 3, 2x − 3y ≤ 12, x, y ≥ 0. The region is unbounded with corners (0, 5), (0, 3), (1, 0), (6, 0), where Z = 100, 60, −50, −300.
The smallest corner value is −300, but the half plane −50x + 20y < −300, that is −5x + 2y < −30, does meet the region: the feasible point (12, 5) gives Z = −500. So Z has no minimum.
In the same example the largest corner value 100 at (0, 5) is the maximum: every feasible point has y ≤ 2x + 5, so Z ≤ −50x + 20(2x + 5) = 100 − 10x ≤ 100.
Open half plane means the boundary line itself is left out (strict inequality).