Unbounded and empty regions

Sometimes the feasible region is unbounded: it runs off to infinity in some direction. This happens with '≥' constraints, as in diet or minimum-cost problems.

The corner point method still gives the candidates, but the best corner value might not be the answer, because Z might keep improving out towards infinity. So you need one extra check.

Checking a minimum m (the smallest corner value): draw the line ax + by = m and look at the open half plane ax + by < m.

• If this half plane has no point in common with the feasible region, m is the minimum.
• If it does share points with the region, Z has no minimum.

Checking a maximum M: the same, with ax + by > M.

Example: minimise Z = x + y subject to x + 2y ≥ 4, 3x + y ≥ 6, x, y ≥ 0. The corners are (4, 0), (8/5, 6/5) and (0, 6), giving Z = 4, 14/5 and 6. The smallest is 14/5. The half plane x + y < 14/5 lies entirely below the region, sharing no point with it, so the minimum is 14/5 at (8/5, 6/5).

For the same region, Z = x + y has no maximum: points far out in the region make Z as large as you like.

No feasible region: if the constraints contradict each other, such as x + y ≤ 1 and x + y ≥ 3, no point satisfies them all. Then the problem has no solution at all.

Always say clearly which case you are in: bounded with an answer, unbounded with the half plane check, or no feasible region.