Bounded vs unbounded feasible regions

A feasible region is bounded if it fits inside some large rectangle , i.e. it is finite in extent. Otherwise it is unbounded: it stretches to infinity in some direction.

For a bounded feasible region, the corner-point theorem guarantees both a maximum and a minimum of the linear objective $Z$, attained at corner points.

For an unbounded feasible region, things are subtler. Either or both of the maximum and the minimum may fail to exist. You must check separately.

Recognising boundedness

The feasible region of an LPP with non-negativity constraints $x, y \ge 0$ is bounded iff for every direction in the first quadrant, there is some constraint that restricts movement in that direction.

In practice:

• All constraints with $\le$ (and non-negativity) typically give a bounded region , the feasible region is "below and to the left of" each constraint line.
• All constraints with $\ge$ typically give an unbounded region , extending up and to the right.
• Mixed $\le$ and $\ge$ constraints may give a bounded or unbounded region, depending on the geometry.

A reliable test: after sketching, ask if there is a direction in which you can move arbitrarily far and still stay feasible.

Optimum behaviour on unbounded regions

For an unbounded feasible region $S$ and linear objective $Z = ax + by$:

• The minimum exists iff $Z$ is bounded below on $S$. Equivalently, there is no direction within $S$ in which $Z$ decreases without bound.
• The maximum exists iff $Z$ is bounded above on $S$. Equivalently, $Z$ does not increase without bound in any feasible direction.

The fundamental theorem of LP, suitably extended: when the optimum does exist on an unbounded region, it is attained at a corner point.

Checking by gradient

The level lines of $Z = ax + by$ are parallel to the line $ax + by = 0$. The gradient (direction of fastest increase) is $(a, b)$. To check whether $Z$ is bounded above on $S$:

• See if the feasible region extends in the direction $(a, b)$.
• If yes, $Z \to \infty$; no maximum.
• If no, the maximum is finite, attained at a corner.

Symmetric for minimum: check whether $S$ extends in $-(a, b)$.

Worked examples

Example 1. Maximise $Z = 3x + 2y$ subject to $x + y \ge 5$, $x, y \ge 0$.

Feasible region: above the line $x + y = 5$ in the first quadrant , unbounded. The gradient of $Z$ is $(3, 2)$. The region extends in direction $(1, 1)$ (and many others); the inner-product of $(3, 2)$ with $(1, 1)$ is $5 > 0$, so $Z$ increases without bound. No maximum.

For minimum: $Z$ decreases in direction $-(3, 2)$, but that's outside the first quadrant (negative components), and the region doesn't extend there. So the minimum is attained somewhere on the boundary. Corners are at $(5, 0)$ and $(0, 5)$, giving $Z = 15$ and $Z = 10$. So min $Z = 10$ at $(0, 5)$.

Example 2. Minimise $Z = -x + 4y$ subject to $x + y \ge 4$, $x, y \ge 0$.

Feasible region: above $x + y = 4$. Gradient of $Z$ is $(-1, 4)$. Direction of decrease: $(1, -4)$ , has a positive $x$-component and a negative $y$-component. Feasible region allows arbitrarily large $x$ with $y = 0$ (since $x \ge 4, y = 0$ is feasible). Moving along $(1, 0)$, $Z = -x$ decreases without bound. No minimum.

Maximum: gradient direction $(-1, 4)$ , negative $x$-component, positive $y$-component. Feasible region extends along $(0, 1)$ (arbitrary large $y$). Moving along this direction, $Z = -0 + 4y$ increases without bound. No maximum either.

Lesson: an LPP on an unbounded region may have neither maximum nor minimum.

Example 3. Minimise $Z = 3x + 2y$ subject to $x + y \ge 4$, $x + 2y \ge 6$, $x, y \ge 0$.

Both constraints are $\ge$; region is unbounded toward upper-right. Gradient direction $(3, 2)$ has positive components, so $Z$ increases without bound in that direction , no maximum.

But minimisation in direction $-(3, 2)$ (negative components) is not feasible , the region doesn't extend in that direction. So minimum is finite, attained at a corner.

Corners: $(4, 0)$ (on $y = 0$, $x + y = 4$; check $x + 2y = 4 + 0 = 4 < 6$, infeasible). Discard. $(6, 0)$ ($y = 0$, $x + 2y = 6$; check $x + y = 6 \ge 4$ ✓). $(0, 4)$ ($x = 0$, $x + 2y = 8 \ge 6$ ✓; $x + y = 4$ ✓). Intersection of $x + y = 4, x + 2y = 6$: subtract: $y = 2, x = 2$.

Values: $(6, 0): 18$; $(0, 4): 8$; $(2, 2): 10$. Minimum $Z = 8$ at $(0, 4)$.

Example 4. Bounded LPP: maximise $Z = 2x + 3y$ subject to $x + y \le 5$, $x \le 4$, $y \le 4$, $x, y \ge 0$.

All $\le$ constraints in first quadrant , bounded. Corners: $(0, 0), (4, 0), (4, 1)$ (on $x = 4$ and $x + y = 5$), $(1, 4)$, $(0, 4)$.

Values: $0; 8; 8 + 3 = 11; 2 + 12 = 14; 12$. Maximum $Z = 14$ at $(1, 4)$.

Example 5. Unbounded with finite minimum. Minimise $Z = x + y$ subject to $5x + y \ge 5$, $x + y \ge 3$, $x, y \ge 0$.

Both $\ge$, unbounded upper-right. Corners: $(5, 0)$ ($y = 0$ and $5x + y = 5$; check $x + y = 5 \ge 3$ ✓). $(0, 5)$ ($x = 0$, $5x + y = 5$; check $x + y = 5 \ge 3$ ✓). Intersection $5x + y = 5, x + y = 3$: subtract: $4x = 2, x = 1/2, y = 5/2$. But check: does $(0, 3)$ work? $5(0) + 3 = 3 < 5$, infeasible. $(3, 0)$? $5(3) + 0 = 15 \ge 5$, $3 + 0 = 3 \ge 3$, feasible. So corners are $(5, 0), (1/2, 5/2), (0, 5)$... wait, also $(3, 0)$? But $(3, 0)$ is interior of the segment from $(5, 0)$ to $(0, 5)$ on the line $x + y = 3$. Actually, $(3, 0)$ is on $x + y = 3$ and $y = 0$, and check $5(3) + 0 = 15 \ge 5$ ✓. So $(3, 0)$ is a corner. The full set: $(3, 0), (1/2, 5/2), (0, 5)$.

Values: $(3, 0): 3$; $(1/2, 5/2): 3$; $(0, 5): 5$. Minimum $Z = 3$ , attained on the edge from $(3, 0)$ to $(1/2, 5/2)$ (and at both endpoints). Infinitely many optima!

Example 6. Empty feasible region. $x + y \le 2$ and $x + y \ge 5$ are inconsistent. No feasible point; no maximum or minimum.

Try it yourself

For each, identify whether the feasible region is bounded or unbounded; then determine whether the maximum and minimum exist.

1. $x + y \le 4$, $x, y \ge 0$, maximise $x + y$.
2. $x + y \ge 3$, $x, y \ge 0$, maximise $x + y$.
3. $x + y \ge 3$, $x, y \ge 0$, minimise $x + y$.
4. $2x + y \le 8$, $x + 2y \le 8$, $x, y \ge 0$, maximise $3x + 2y$.
5. $x \ge 1$, $y \ge 1$, maximise $x + y$.
6. $x + y \ge 5$, $x \le 4$, $y \le 4$, $x, y \ge 0$, maximise $x + y$.
7. $-x + y \ge 1$, $x + y \le 6$, $x, y \ge 0$, max $Z = 2x + y$.
8. $x + y \ge 4$, $x + y \le 8$, $x, y \ge 0$, min $Z = 3x + 2y$.
9. $x + y \le 1$, $x \ge 2$, $y \ge 0$. (Empty?)
10. $x - y \ge 1$, $x, y \ge 0$. (Region behaviour at large $x$?)
11. $x + y \le 6$, $x - y \le 4$, $x, y \ge 0$, max $Z = x + y$.
12. $2x + y \ge 4$, $-x + y \ge 0$, $x, y \ge 0$, min $Z = x + 2y$.
13. Unique-edge: $Z = 3x + 2y$ subject to $3x + 2y \le 12$, $x, y \ge 0$. Maximum value, and where?
14. $x + 2y \ge 6$, $3x + 4y \ge 18$, $x, y \ge 0$, min $Z = x + y$.

Pitfalls and tricks

• Always check boundedness by examining whether the feasible region extends without limit in some direction.
• For unbounded regions, examine the objective at infinity along the boundary directions. If $Z$ can grow without bound in a feasible direction, the maximum is infinite.
• A maximum or minimum may not exist on unbounded regions. Don't assume it does.
• Equal $Z$ at adjacent corners $\Rightarrow$ infinitely many optima along the connecting edge.
• Empty feasible region $\Rightarrow$ no solution; mention this in your answer.