On this page
Solving a linear programming problem (LPP) usually involves graphing constraints and finding the corner points of the feasible region. For a bounded region, the highest corner value is always the maximum. But when the feasible region is unbounded, the objective function might grow infinitely large.
According to the NCERT Class 12 mathematics textbook, the largest value found at a corner point is only a candidate. You must perform an open half-plane test to check whether a true maximum exists.
Why does the corner point method fail for unbounded regions?
The fundamental theorem of linear programming states that if an optimal solution exists, it must occur at a corner point (vertex) of the feasible region. When a region is bounded (a closed polygon), the objective function is trapped. It must reach its highest and lowest values at the corners before leaving the shape.
However, an unbounded region stretches to infinity in at least one direction. While a minimum value often rests safely at a corner closest to the origin, a maximization problem might follow the open path forever. The corner point gives you a starting baseline, but the open half-plane test is the only mathematical way to prove whether the function escapes to infinity.
How to find the maximum value in an unbounded region?
When a feasible region is open on one or more sides, you must test whether the objective function can push past your best corner value.
Find the candidate: Calculate the objective function Z = ax + by at all corner points of the feasible region. Let M be the largest value among them.
Form the inequality: Set up the strict inequality ax + by > M.
Graph the line: Draw the line ax + by = M. Because the inequality is strict, this should be drawn as a dotted line.
Shade the half-plane: Shade the open half-plane representing ax + by > M.
What if the half-plane intersects the feasible region?
The final step is to look at where the open half-plane lies relative to your feasible region.
No intersection: If the open half-plane shares no points with the feasible region, then M is the true maximum.
Intersection: If the open half-plane enters the feasible region, then Z has no maximum value. You can always find a point further out in the region that gives a higher value.
How do you test an unbounded region with a worked example?
Consider the problem: Maximize Z = 4x + 3y subject to x + y ≥ 5, x + 3y ≥ 9, and x, y ≥ 0.
To find the corners, we solve the constraint equations. The y-axis intercept of the first constraint is (0, 5), and the x-axis intercept of the second is (9, 0). Setting x + y = 5 and x + 3y = 9 equal to each other reveals they cross at (3, 2). Since both constraints use ≥, the feasible region is the unbounded area sitting above both lines in the first quadrant.
Testing Z at each corner point:
At (0, 5): 4(0) + 3(5) = 15
At (3, 2): 4(3) + 3(2) = 18
At (9, 0): 4(9) + 3(0) = 36
Our candidate maximum is M = 36. Now, we test the open half-plane 4x + 3y > 36.
As shown in the graph above, the dotted line 4x + 3y = 36 passes through (9, 0) and heads steeply upward. The region 4x + 3y > 36 lies above and to the right of this line, which clearly overlaps with our unbounded feasible region. For instance, the point (10, 10) is deep inside the feasible region, and its value is Z = 70. Because the open half-plane shares points with the feasible region, this problem has no maximum value.
How do you check for a minimum value?
The exact same logic applies to finding a minimum, but you test the lower bound instead. Let m be the smallest value at a corner point, and test the open half-plane ax + by < m.
In our example, the smallest corner value is m = 15 at (0, 5). To prove it is the minimum, we draw the open half-plane 4x + 3y < 15. This region lies entirely below the dashed line passing through (3.75, 0) and (0, 5). If you look at our feasible region, it never dips below the boundary x + y = 5. The open half-plane shares absolutely no points with the feasible region. Therefore, 15 is the confirmed true minimum.
What happens with multiple optimal solutions?
What happens if the dotted line perfectly matches one of your boundary lines? If your objective function happens to be parallel to a constraint line, the maximum or minimum value might occur along that entire edge. The open half-plane test still holds: the open region (> or <) will not share points with the feasible region, proving your candidate is correct. The difference is simply that you have infinitely many optimal solutions along that segment.
If you are unsure where your graph went wrong, you can hand the inequalities to the Fermi Problem Library. Its step-by-step solver works through the reasoning behind each boundary line and explains the open half-plane test for your specific constraints. You can also explore how systems of linear inequalities define regions in the Fermi Concept Library.
Related reading:
