Linear Programming · Lesson 3 of 4

Unbounded and Infeasible Problems

“Decide whether a best value exists when a region extends indefinitely or when constraints have no common solution.”

Learning Objectives

• Recognise an unbounded feasible region and an empty feasible region. • Test whether a candidate corner value is a true optimum in an unbounded region. • Use strict objective half-planes to test maximum and minimum candidates. • Distinguish no feasible solution from a feasible problem with no finite optimum. • Explain how an unbounded region can still have an optimal point or edge.

When the region never ends

An unbounded feasible region contains points arbitrarily far away. That describes the size of the region, not the behaviour of every objective on it. Depending on the coefficients, an objective may increase indefinitely in one direction, decrease indefinitely, or still have a finite optimum.

A corner table lists only finitely many points. In a bounded region that is enough. In an unbounded region the table gives candidates, but we must also ask whether a more distant feasible point can improve the candidate value. Never replace that check with the statement “the region is unbounded, so there is no optimum”.

Testing beyond the corner table

Suppose the largest corner value is $M$ and the smallest is $m$ . To test a candidate, search for feasible points with a strictly better objective value. “Strictly” matters because another point with equal value does not defeat an optimum.

Test a maximum candidateLaTeX

a x + b y > M

Graph this open half-plane. If it has no point in common with the feasible region, M is the maximum. If it overlaps, M is not the maximum; the corner-point result rules out a finite maximum elsewhere in these models.

Test a minimum candidateLaTeX

a x + b y < m

Graph this open half-plane. If it has no point in common with the feasible region, m is the minimum. If it overlaps, m is not the minimum; in these models there is no finite minimum.

An open half-plane excludes its boundary line. Draw that comparison boundary dashed, and test a point to choose the appropriate side. Keep the original constraint boundaries solid when their inequalities allow equality.

An unbounded region with no minimum— The darker triangle contains feasible points with objective values below the smallest corner value, −300. The region continues beyond the frame.

Example — A smallest corner value that is not a minimum

Problem
Minimise $Z = - 50 x + 20 y$ subject to $2 x - y \geq - 5$ , $3 x + y \geq 3$ , $2 x - 3 y \leq 12$ , and $x, y \geq 0$ .

1.Rewrite the constraints as $y \leq 2 x + 5$ , $y \geq 3 - 3 x$ , and $y \geq (2 x - 12) /3$ . Their common first-quadrant region is unbounded.
2.Its vertices are $(0, 5)$ , $(0, 3)$ , $(1, 0)$ , and $(6, 0)$ . The corresponding objective values are 100, 60, $- 50$ , and $- 300$ .
3.The smallest corner value is $- 300$ . Test $- 50 x + 20 y < - 300$ , or equivalently $- 5 x + 2 y < - 30$ .
4.The feasible point $(9, 2)$ satisfies the original inequalities: $18 - 2 \geq - 5$ , $27 + 2 \geq 3$ , and $18 - 6 = 12 \leq 12$ . Its objective is $- 450 + 40 = - 410 < - 300$ . Thus the candidate is not a minimum.
5.To see that values keep decreasing, follow the feasible boundary $y = (2 x - 12) /3$ for $x \geq 6$ . There $Z = - (110/3) x - 80$ , which tends down without bound as $x$ increases. No finite minimum exists.

Vertex	Objective value
$(0, 5)$	100
$(0, 3)$	60
$(1, 0)$	$- 50$
$(6, 0)$	$- 300$ — smallest corner value only

Example — The same region does have a maximum

Problem
For the preceding region and objective $Z = - 50 x + 20 y$ , decide whether 100 at $(0, 5)$ is the maximum.

1.A larger value would require $- 50 x + 20 y > 100$ . We must check whether that open half-plane intersects the feasible region.
2.Every feasible point satisfies $y \leq 2 x + 5$ . Multiplying by the positive number 20 gives $20 y \leq 40 x + 100$ .
3.Therefore $Z = - 50 x + 20 y \leq - 10 x + 100 \leq 100$ , since $x \geq 0$ . No feasible point has a value greater than 100.
4.The point $(0, 5)$ is feasible and gives 100, so it attains the maximum. One direction of optimisation can therefore succeed while the other fails on the very same feasible region.

An unbounded region can have a minimum

Lower limits often produce unbounded regions because there is no upper restriction on the variables. A positive cost objective may still have a cheapest point near the lower boundary. The essential issue is the objective value, not whether the picture fits inside a circle.

An unbounded region with a finite minimum— The region extends upwards and rightwards, but the lowest cost occurs at the intersection of its two lower boundaries.

Example — A finite minimum in an unbounded region

Problem
Minimise $Z = 3 x + 5 y$ subject to $x + 3 y \geq 3$ , $x + y \geq 2$ , and $x, y \geq 0$ .

1.The feasible vertices are $(0, 2)$ , $(3/2, 1/2)$ , and $(3, 0)$ . For the middle point, subtract $x + y = 2$ from $x + 3 y = 3$ to get $2 y = 1$ , then $x = 3/2$ .
2.The objective values are 10, 7, and 9. The smallest corner value is 7, but the region is unbounded, so verify it.
3.Rewrite the objective as $Z = 2 (x + y) + (x + 3 y)$ . Every feasible point has $Z \geq 2 (2) + 3 = 7$ . Thus the strict half-plane $3 x + 5 y < 7$ has no feasible point.
4.The intersection $(3/2, 1/2)$ gives 7, so the minimum is attained there despite the region being unbounded.

Example — Many minimum points in an unbounded region

Problem
Minimise $Z = x + 2 y$ subject to $2 x + y \geq 3$ , $x + 2 y \geq 6$ , and $x, y \geq 0$ . Show that more than two points attain the minimum.

1.One constraint is exactly $Z \geq 6$ , so no feasible value can be less than 6.
2.On $x + 2 y = 6$ , write $y = 3 - x /2$ . For $0 \leq x \leq 6$ , both coordinates are non-negative.
3.Along this segment, $2 x + y = 2 x + 3 - x /2 = 3 + 3 x /2 \geq 3$ , so the whole segment from $(0, 3)$ to $(6, 0)$ is feasible.
4.Every point on that segment gives $Z = 6$ . For instance, $(0, 3)$ , $(2, 2)$ , and $(6, 0)$ are three distinct minimum points, and infinitely many more lie between them.

When there is no feasible point

Sometimes constraints make incompatible demands. Then their chosen half-planes have no common point. There is no allowed decision to optimise, even if each inequality considered separately has many solutions.

Incompatible constraints— The orange and blue sets have no overlap. Shading separate constraint regions does not create a common feasible region.

Example — Prove that the feasible region is empty

Problem
Consider minimising $Z = 3 x + 2 y$ subject to $x + y \geq 8$ , $3 x + 5 y \leq 15$ , and $x, y \geq 0$ .

1.The first constraint requires a total of at least 8. Non-negative $y$ gives $3 x + 5 y = 3 (x + y) + 2 y \geq 3 (x + y)$ .
2.Using $x + y \geq 8$ , this implies $3 x + 5 y \geq 24$ . That contradicts the requirement $3 x + 5 y \leq 15$ .
3.No point can satisfy all the constraints. The graph therefore has no common feasible region.
4.The problem has no feasible solution and hence no optimal solution. Changing the objective alone would not remove the contradiction.

Two different reasons for no optimum

An infeasible problem has no permitted point at all. A feasible problem with an objective unbounded below or above has permitted points, but their objective values keep improving without a finite best value. Diagnose the region first, then the objective.

Situation	What to check	Conclusion
Empty feasible region	No common point satisfies all constraints	No feasible or optimal solution
Nonempty bounded region	All vertex values	Both extrema exist
Nonempty unbounded region	Vertex candidates and strict better-value half-planes	Each direction must be checked separately

Quick check

An unbounded feasible region necessarily means which statement?

Quick check

The smallest corner value is $m$ in an unbounded region. Which test is needed for minimisation?

Quick check

Why is $- 300$ not the minimum of the unbounded example?

Quick check

In that same example, why is 100 a valid maximum?

Quick check

If the constraint half-planes have no common point, what follows?

Quick check

For $Z = x + 2 y$ with the constraint $x + 2 y \geq 6$ , a feasible segment lies on $x + 2 y = 6$ . What follows?

Practice Problems

For the example $Z = - 50 x + 20 y$ , find a feasible point with objective less than $- 410$ . Explain how you know it is feasible.
Re-solve the minimisation of $Z = 3 x + 5 y$ under $x + 3 y \geq 3$ , $x + y \geq 2$ , $x, y \geq 0$ using a vertex table and the strict half-plane test.
For $Z = x + 2 y$ under $2 x + y \geq 3$ , $x + 2 y \geq 6$ , $x, y \geq 0$ , write four distinct minimum points and describe all of them.
Maximise $Z = - x + 2 y$ subject to $x \geq 3$ , $x + y \geq 5$ , $x + 2 y \geq 6$ , and $y \geq 0$ . Show a feasible family along which $Z$ increases indefinitely.
Maximise $Z = x + y$ subject to $x - y \leq - 1$ , $- x + y \leq 0$ , and $x, y \geq 0$ . Explain the contradiction in words and by a graph.
Give an unbounded feasible region on which $Z = x + y$ has a minimum but no maximum. Justify both conclusions.
Explain why a strict comparison inequality excludes its boundary, whereas an original constraint such as $x + y \geq 6$ includes its boundary.

Key Takeaways

Unbounded describes the region; it does not by itself determine whether an optimum exists. In an unbounded region, check whether a strict better-value half-plane overlaps the feasible region. A feasible unbounded region may have a finite maximum, a finite minimum, or an optimal edge. An empty feasible region means no allowed decision exists. Keep infeasibility distinct from an objective that improves without bound.

Previous · Lesson 2

Feasible Regions and Corner-Point Solutions

Next · Lesson 4

Chapter Summary and Practice

When the region never ends

Testing beyond the corner table

An unbounded region can have a minimum

When there is no feasible point

Quiz

Practice Problems

Key Takeaways