- Foundation
- About 20 min
- 5 practice questions
Unbounded regions, multiple optimal solutions and infeasible problems
Decide whether an optimal value exists when the feasible region is unbounded, recognise multiple optimal solutions along an edge, and identify LPPs that have no feasible region.
If something looks wrong, please tell us.
The corner point method needs care in three situations: when the feasible region is unbounded, when two corners give the same best value, and when there is no feasible region at all. This lesson completes the method with the rules for each case.
Unbounded feasible regions
If the feasible region R is unbounded, a maximum or minimum of Z may not exist; but if it exists, it must still occur at a corner point (Theorem 1). So evaluate Z at the corners and let M be the largest and m the smallest value. Then:
- M is the maximum of Z if the open half-plane ax + by > M has no point in common with R. Otherwise Z has no maximum.
- m is the minimum of Z if the open half-plane ax + by < m has no point in common with R. Otherwise Z has no minimum.
Checking an unbounded region
- Evaluate Z at all corners; note M (largest) and m (smallest)
- For a minimum: draw ax + by = m and look at the side ax + by < m
- If that open half-plane misses R, m is the minimum
- If it meets R, there is no minimum (similarly for M and a maximum)
Worked example 1: the canteen problem
Minimise Z = 10x + 12y subject to 2x + y ≥ 10, x + 2y ≥ 8, x, y ≥ 0. From lesson 3 the region is unbounded with corners (0, 10), (4, 2) and (8, 0). Values: Z(0, 10) = 120, Z(4, 2) = 40 + 24 = 64, Z(8, 0) = 80. So m = 64. Now draw 10x + 12y = 64, which passes through (4, 2), (6.4, 0) and (0, 16/3). The side 10x + 12y < 64 is the side towards the origin, and it has no point in common with the feasible region (which lies on the far side of both constraint lines). So the minimum cost is ₹64, using 4 units of A and 2 units of B.
Does Z have a maximum here? M = 120 at (0, 10). But the half-plane 10x + 12y > 120 contains feasible points such as (0, 20) or (20, 20), so Z has no maximum; the cost can be made as large as we like by using more of both items.
Worked example 2: no minimum
Find the minimum of Z = x − 2y subject to x + y ≥ 2, x ≥ 0, y ≥ 0. The region is unbounded with corners (2, 0) and (0, 2). Z(2, 0) = 2 and Z(0, 2) = −4, so m = −4. The open half-plane x − 2y < −4 contains feasible points, for example (0, 5), where x + y = 5 ≥ 2 and Z = −10. So the smallest corner value is not the minimum: Z has no minimum value. It decreases without limit as y increases.
Multiple optimal solutions
If two adjacent corner points give the same optimal value, then every point on the segment joining them gives that value too. This happens when the line Z = constant is parallel to the edge between them.
Worked example 3
In the tailor problem, suppose the profit on a kurta were ₹150 instead of ₹180, so Z = 100x + 150y. At the corners: Z(0, 0) = 0, Z(30, 0) = 3000, Z(15, 10) = 1500 + 1500 = 3000, Z(0, 17.5) = 2625. The maximum, ₹3000, occurs at both (30, 0) and (15, 10), and hence at every point of the segment joining them. Notice why: Z = 50(2x + 3y), and 2x + 3y = 60 is exactly the cloth constraint along that edge. In practice the tailor would choose a point on this edge with whole-number coordinates, such as (24, 4) or (18, 8).
No feasible region
Sometimes the constraints contradict each other and no point satisfies all of them. Then the problem has no feasible region and no feasible solution, so it has no optimal value.
Worked example 4
Consider 2x + y ≥ 10, x + y ≤ 3, x ≥ 0, y ≥ 0. From x + y ≤ 3 and y ≥ 0 we get x ≤ 3 and y ≤ 3 − x. Then 2x + y ≤ 2x + 3 − x = x + 3 ≤ 6, which can never be at least 10. The half-planes do not overlap in the first quadrant: there is no feasible region.
| Situation | What the corner point method gives |
|---|---|
| Bounded region | Both maximum and minimum exist, at corners |
| Unbounded region | Use the open half-plane test; an optimum may or may not exist |
| Two corners tie for the optimum | Every point of the edge joining them is optimal |
| Contradictory constraints | No feasible region, no solution |
Key takeaways
- On an unbounded region, test the open half-plane beyond the best corner value before calling it optimal.
- Minimising a cost with positive coefficients over an unbounded region of ≥ constraints usually has a minimum but no maximum.
- Two optimal corners mean infinitely many optimal solutions along the edge between them.
- Contradictory constraints give an empty feasible region and no solution.
- The feasible region is convex and the optimum, when it exists, is at a corner.
Check your understanding
-
1. An unbounded feasible region has corners (0, 6), (2, 2) and (6, 0) and lies on the far side of x + 2y = 6 and 2x + y = 6 from the origin. What is the minimum of Z = 3x + 2y?
- 12
- 18
- 10
- It has no minimum
Show answer
Answer: C. Corner values: 12, 6 + 4 = 10, 18, so m = 10 at (2, 2). The open half-plane 3x + 2y < 10 lies on the origin side of the line through (2, 2) and contains no feasible point, so 10 is the minimum.
-
2. For the same region, what can be said about the maximum of Z = 3x + 2y?
- It is 18, at (6, 0)
- Z has no maximum value
- It is 12, at (0, 6)
- It is 10, at (2, 2)
Show answer
Answer: B. The largest corner value is 18, but the half-plane 3x + 2y > 18 contains feasible points such as (10, 10). Z can be made as large as we like, so it has no maximum.
-
3. Maximise Z = 2x + 4y subject to x + 2y ≤ 8, x + y ≤ 6, x, y ≥ 0. The corners are (0, 0), (6, 0), (4, 2) and (0, 4). Which points give the maximum?
- Only (4, 2)
- Only (0, 4)
- Exactly the two points (4, 2) and (0, 4)
- Every point of the segment joining (4, 2) and (0, 4)
Show answer
Answer: D. Z at the corners: 0, 12, 16, 16. The maximum 16 occurs at two adjacent corners, so it occurs at every point of the edge joining them (that edge lies on x + 2y = 8, and Z = 2(x + 2y)).
-
4. Which system of constraints has no feasible region?
- x + y ≤ 2, x + y ≥ 5, x ≥ 0, y ≥ 0
- x + y ≥ 2, x + y ≤ 5, x ≥ 0, y ≥ 0
- x ≤ 4, y ≥ 1, x ≥ 0
- x + 2y ≥ 4, x ≥ 0, y ≥ 0
Show answer
Answer: A. No point can have x + y at most 2 and at least 5 at the same time, so the first system is contradictory. The others all have feasible points, such as (1, 2), (0, 1) and (4, 0).
-
5. Assertion (A): If the feasible region of an LPP is unbounded, the objective function Z = ax + by may have no maximum value. Reason (R): An unbounded region extends indefinitely, so Z may increase without limit within it.
- 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. Both are true. For example, in the canteen problem the cost 10x + 12y has no maximum because the region extends indefinitely. R explains A; it is also why the open half-plane test is needed.
Sign in to keep track of the lessons you finish.