• Foundation
  • About 17 min
  • 5 practice questions

Unbounded regions, infeasible problems and multiple optima

Decide whether an optimum exists on an unbounded region using the open half-plane test, recognise problems with no feasible point, and spot when a whole edge of the region is optimal.

If something looks wrong, please tell us.

The corner-point method of the previous lesson came with a condition: the region must be bounded. Diet and cost problems usually have ≥ constraints, and their feasible regions run off to infinity. This lesson shows how to finish such problems correctly, and how to recognise the two other special outcomes: no feasible solution at all, and infinitely many best solutions.

Unbounded regions: corner values are only candidates

On an unbounded region, a maximum or a minimum may fail to exist, because Z can keep growing (or falling) as you move off to infinity. The corners still give the only possible optimum, but you must test it. Suppose the smallest corner value is m. Draw the line px + qy = m and look at the open half-plane px + qy < m. If that half-plane has no point in common with the feasible region, m is the minimum; otherwise there is no minimum. For a maximum, use the largest corner value M and the half-plane px + qy > M.

Unbounded region: let M and m be the largest and smallest corner values of Z. M is the maximum only if px + qy > M has no point in the region; m is the minimum only if px + qy < m has no point in the region.

Worked example 1: the diet problem solved

Minimise Z = 40x + 30y subject to 3x + y ≥ 9, x + 2y ≥ 8, x ≥ 0, y ≥ 0. The lines meet where y = 9 − 3x and x + 2(9 − 3x) = 8, so −5x = −10, x = 2 and y = 3. The corners are (0, 9), (2, 3) and (8, 0), with Z = 270, 170 and 320. The candidate minimum is 170. Test 40x + 30y < 170, that is 4x + 3y < 17. Here a neat check works: 4x + 3y = (3x + y) + (x + 2y), and in the region this is at least 9 + 8 = 17. So no feasible point has 4x + 3y < 17, and the minimum cost is ₹170, with 2 packets of P and 3 packets of Q. The same region has no maximum cost, for instance (10, 0) is feasible and costs ₹400, which is more than every corner value, and the cost keeps rising further out.

Worked example 2: a minimum that does not exist

On the region x + y ≥ 4, x + 3y ≥ 6, x ≥ 0, y ≥ 0 (corners (0, 4), (3, 1), (6, 0)), find the minimum of Z = x − 2y. Corner values: −8, 1, 6, so the candidate is −8. Test x − 2y < −8: the point (0, 5) is feasible and gives −10. So there is no minimum: going up the y-axis makes Z as negative as we like. Never report a corner value on an unbounded region without this test.

Infeasible problems

If the constraints contradict each other, the feasible region is empty and the problem has no feasible solution, so it has neither a maximum nor a minimum. For example, 3x + 2y ≤ 6 and x + y ≥ 4 with x, y ≥ 0 cannot both hold, because 3x + 2y ≥ 2x + 2y = 2(x + y) ≥ 8. Recognise this before wasting time on corners.

Multiple optimal solutions

If two adjacent corners give the same best value, then every point on the edge joining them gives that value too, and the problem has infinitely many optimal solutions. This happens when the lines of constant Z are parallel to that edge.

Worked example 3: a whole edge is optimal

Maximise Z = 3x + 3y subject to x + y ≤ 6, 2x + y ≤ 10, x ≥ 0, y ≥ 0. The lines meet at (4, 2). Corners (0, 0), (5, 0), (4, 2), (0, 6) give Z = 0, 15, 18, 18. The maximum is 18, attained at (4, 2), at (0, 6) and at every point between them, such as (2, 4), because Z = 3(x + y) and x + y = 6 along that edge.

SituationHow to recognise itConclusion
Bounded regionclosed polygonmax and min both exist at corners
Unbounded regionruns off to infinitytest the open half-plane before accepting a corner value
Empty regionconstraints contradictno feasible solution
Tie at two adjacent cornersobjective parallel to an edgeinfinitely many optimal points on that edge

Key takeaways: on an unbounded region the best corner value is only a candidate: confirm it with the open half-plane test. An empty region means no solution at all. A tie between adjacent corners means a whole edge of optimal solutions.

Check your understanding

  1. 1. What is the minimum of Z = 3x + 2y subject to x + y ≥ 5, x + 3y ≥ 9, x ≥ 0, y ≥ 0?

    1. 13
    2. 27
    3. No minimum exists
    4. 10
    Show answer

    Answer: D. Corners: (0, 5), (3, 2) where the lines meet, and (9, 0). Z = 10, 13, 27, so the candidate is 10. The region is unbounded, so test: can 3x + 2y < 10 hold in the region? 3x + 2y = 2(x + y) + x ≥ 2 × 5 + 0 = 10, so no. The minimum is 10 at (0, 5).

  2. 2. On the same region (x + y ≥ 5, x + 3y ≥ 9, x ≥ 0, y ≥ 0), what is the minimum of Z = x − y?

    1. −5
    2. 1
    3. No minimum exists
    4. 9
    Show answer

    Answer: C. Corner values: (0, 5) gives −5, (3, 2) gives 1, (9, 0) gives 9, so the candidate is −5. Test the open half-plane x − y < −5: the point (0, 6) is feasible (6 ≥ 5 and 18 ≥ 9) and gives −6. So Z can be made as small as we like by going up the y-axis, and there is no minimum.

  3. 3. What can be said about: maximise Z = x + y subject to 2x + y ≤ 4, x + y ≥ 5, x ≥ 0, y ≥ 0?

    1. The maximum is 5
    2. There is no feasible solution
    3. The maximum is 4
    4. Z has no maximum because the region is unbounded
    Show answer

    Answer: B. For x ≥ 0, 2x + y ≥ x + y, so x + y ≥ 5 forces 2x + y ≥ 5, which breaks 2x + y ≤ 4. No point satisfies all the constraints: the region is empty and the problem is infeasible.

  4. 4. Maximise Z = 2x + 4y subject to x + 2y ≤ 8, x + y ≤ 6, x ≥ 0, y ≥ 0. Where is the maximum attained?

    1. At every point of the segment joining (4, 2) and (0, 4)
    2. Only at (4, 2)
    3. Only at (0, 4)
    4. Nowhere, Z has no maximum
    Show answer

    Answer: A. Corners (0, 0), (6, 0), (4, 2), (0, 4) give Z = 0, 12, 16, 16. Two adjacent corners tie for the largest value 16, so every point of the edge between them (on the line x + 2y = 8) also gives 16: Z = 2(x + 2y) = 16 there. There are infinitely many optimal solutions.

  5. 5. In the test for an unbounded region, M is the largest value of Z = px + qy at the corners. If the open half-plane px + qy > M has points in common with the feasible region, then:

    1. M is the maximum
    2. M is the minimum
    3. the problem has no feasible solution
    4. Z has no maximum
    Show answer

    Answer: D. A common point is a feasible point where Z is bigger than every corner value, and moving further in that direction makes Z bigger still. So no maximum exists. If the half-plane had no common point, M would be the maximum.

Privacy · Terms · Refunds · Delivery