10 min readPathway sheet3 or 5-mark question (often a minimum-cost problem); 1-mark MCQ on whether a maximum exists

Unbounded regions and problems with no solution

On an unbounded region, a corner value is optimal only if an open half-plane test finds no feasible point beyond it. Otherwise no optimum exists.

Testing a maximum MIf the open half-plane ax + by > M has no point in common with the feasible region, M is the maximum; otherwise Z has no maximum

Testing a minimum mIf the open half-plane ax + by < m has no point in common with the feasible region, m is the minimum; otherwise Z has no minimum

Empty feasible regionNo feasible solution, so no maximum and no minimum

The method for an unbounded region (and how to draw the test)

1
Draw the feasible region and find its corner points, as usual.
2
Work out Z at each corner. Let M be the largest value and m the smallest.
3
For a minimum: draw the line ax + by = m as a dotted line and look at the open half-plane ax + by < m.
4
If that half-plane has no point in common with the feasible region, m is the minimum. Otherwise Z has no minimum.
5
For a maximum: do the same with the dotted line ax + by = M and the half-plane ax + by > M.
6★
Write the conclusion in words, for example 'Minimum Z = 380 at (2, 4); Z has no maximum'.

★ key step

Example 1: a minimum that exists

Problem

Minimise Z = 50x + 70y subject to 2x + y ≥ 8, x + 2y ≥ 10, x ≥ 0, y ≥ 0.

Working

The region is unbounded, with corners A(0, 8), B(2, 4), C(10, 0).
Z at A = 560, at B = 100 + 280 = 380, at C = 500. So m = 380.
Draw the dotted line 50x + 70y = 380, that is 5x + 7y = 38, through B.
The half-plane 5x + 7y < 38 lies towards O and has no point in common with the feasible region.

Answer

Minimum Z = 380 at x = 2, y = 4.

Example 2: no maximum

Problem

On the same region, does Z = 50x + 70y have a maximum?

Working

The largest corner value is M = 560.
Test the half-plane 50x + 70y > 560: the point (10, 10) is feasible (30 ≥ 8 and 30 ≥ 10) and gives Z = 1200 > 560.
So the half-plane meets the feasible region.

Answer

Z has no maximum on this region.

Example 3: no minimum either

Problem

Minimise Z = x − 2y subject to x + y ≥ 4, x ≥ 0, y ≥ 0.

Working

The region is unbounded, with corners (4, 0) and (0, 4).
Z at (4, 0) = 4; Z at (0, 4) = −8. So m = −8.
Test x − 2y < −8: the point (0, 5) is feasible (0 + 5 ≥ 4) and gives Z = −10 < −8.

Answer

The half-plane meets the region, so Z has no minimum.

Bounded vs unbounded: what changes

Bounded regionThe largest corner value is the maximum and the smallest is the minimum. No extra test is needed.

Unbounded regionThe best corner value is only a candidate. Confirm it with the open half-plane test, or say that no optimal value exists.

When there is no feasible region

If the constraints have no common region (for example x + y ≤ 2 and 2x + 3y ≥ 12 with x, y ≥ 0), there is no feasible solution.
Then Z has no maximum and no minimum. Write this clearly; do not invent a corner.
An empty region is different from an unbounded one: an unbounded region has infinitely many feasible points.

In real life

A hostel mess finding the cheapest food mix that meets minimum vitamin needs gets an unbounded region. A cheapest mix exists, but there is no 'most expensive' mix, because more food can always be added.

Exam angle

1 marks: “The feasible region of an LPP is unbounded. Must Z = 3x + 2y have a maximum on it?” Not necessarily. Find the largest corner value M and test the half-plane 3x + 2y > M; if it meets the region, there is no maximum.

3 marks: “Minimise Z = 2x + 3y subject to x + y ≥ 6, x + 3y ≥ 10, x ≥ 0, y ≥ 0.” The lines meet at (4, 2). Corners (0, 6), (4, 2), (10, 0): Z = 18, 14, 20. The half-plane 2x + 3y < 14 has no point in common with the region, so minimum Z = 14 at (4, 2).

5 marks: “Solve graphically: Minimise Z = 4x + 3y subject to x + 2y ≥ 8, 3x + 2y ≥ 12, x ≥ 0, y ≥ 0. Show that Z has no maximum.” The lines meet at (2, 3). Corners (0, 6), (2, 3), (8, 0): Z = 18, 17, 32. 4x + 3y < 17 has no point in common with the region, so minimum Z = 17 at (2, 3). The point (10, 10) is feasible with Z = 70 > 32, so there is no maximum.

Remember it

Unbounded? Draw the dotted line and test the open side.