Feasible and optimal solutions
Bounded and unbounded feasible regions, infeasible regions and the optimal feasible solution.
The essentials
Every point in the feasible region is a feasible solution; points outside it are infeasible. A feasible solution that gives the best value of the objective function is an optimal (feasible) solution.
A feasible region is bounded if it can be enclosed in a circle; then both the maximum and the minimum of Z exist and occur at corner points. It is unbounded if it extends indefinitely in some direction. Then an optimal value may or may not exist, and you need an extra check. Suppose M is the largest value of Z = ax + by at the corner points. If the open half-plane ax + by > M has no point in common with the feasible region, then M is the maximum; otherwise Z has no maximum. Similarly, if m is the smallest corner value and the half-plane ax + by < m has no common point with the region, m is the minimum.
If the constraints have no common point at all, the feasible region is empty: the problem is infeasible and has no solution.
Key points
- Bounded region: the optimum always exists.
- Unbounded region: test with the half-plane before concluding.
- A typical minimisation (diet) problem has an unbounded region but still has a minimum.
- Example: minimise Z = 2x + 3y subject to x + y ≥ 4, x, y ≥ 0. Corners (4, 0) and (0, 4) give 8 and 12; the half-plane 2x + 3y < 8 does not meet the region, so the minimum is 8.
Exam tips
- When the region is unbounded, always write one line stating the half-plane check.
- An empty feasible region usually comes from contradictory constraints such as x + y ≤ 2 and x + y ≥ 5.
Common mistakes
- Declaring the largest corner value the maximum for an unbounded region without checking.
- Confusing "no feasible solution" with "no optimal solution".