Find the Feasible Region of Linear Inequalities
Determine the exact feasible region, compute boundary corner points (extreme vertices), classify geometric boundedness, and optimize objective functions for any system of two-variable linear inequalities with interactive SVG shaded polygon visualization.
| Vertex | Coordinates (x, y) | Objective Value Z | Status |
|---|
How to Find the Feasible Region of Linear Inequalities
To find the feasible region of a system of linear inequalities, graph the boundary line for each constraint, shade the appropriate half-plane (using a test point like (0,0)), and identify the overlapping intersection of all shaded regions. Calculate the corner point vertices by solving the simultaneous 2x2 systems of intersecting boundary lines. Finally, evaluate the objective function Z at each corner point to determine the optimal maximum or minimum value.
Mathematical Foundations: Half-Planes and Feasibility
In analytic geometry and mathematical optimization, a two-variable linear equation $ax + by = c$ partitions the two-dimensional Cartesian plane $\mathbb{R}^2$ into two infinite regions termed half-planes. Replacing the equality with an inequality sign ($\le, \ge, <, >$) designates one of these two half-planes as the solution space. If the inequality is non-strict ($\le$ or $\ge$), the dividing boundary line is included in the solution set (a closed half-plane); if strict ($<$ or $>$), the boundary line is excluded (an open half-plane).
When dealing with a system of $m$ simultaneous linear inequalities, the feasible region $\mathcal{R}$ is formally defined as the intersection of all $m$ corresponding half-spaces:
A fundamental theorem of convex analysis establishes that any half-plane is a convex set, and because the arbitrary intersection of convex sets is always convex, the feasible region of any system of linear inequalities is guaranteed to be a convex polygonal set (or convex polytope). This convexity guarantees that any line segment connecting two points in $\mathcal{R}$ lies entirely within $\mathcal{R}$.
The Corner Point Theorem & Fundamental Principle of Linear Programming
Linear Programming (LP) is the mathematical discipline concerned with maximizing or minimizing a linear objective function $Z = c_1 x + c_2 y$ subject to a system of linear constraints. The theoretical cornerstone of this field is the Corner Point Theorem (also known as the Fundamental Theorem of Linear Programming):
If a linear programming problem possesses an optimal solution (maximum or minimum) over a non-empty, bounded feasible region $\mathcal{R}$, that optimal value occurs at one or more of the extreme points (corner point vertices) of the feasible region.
Geometrically, the objective function represents a family of parallel level lines (isocost or isoprofit contours) defined by $c_1 x + c_2 y = k$. As $k$ increases, this line sweeps across the Cartesian plane. The last point of contact between this sweeping line and the convex feasible polygon before exiting the region must inevitably touch a vertex (or an entire boundary edge connecting two adjacent vertices). Therefore, rather than testing infinite interior points, an analyst only needs to evaluate $Z$ at the finite set of corner vertices!
Classification of Feasible Regions: Bounded, Unbounded, and Infeasible
Depending on the orientation and consistency of the inequality constraints, feasible regions fall into three distinct structural categories:
Enclosed on all sides by constraint boundaries. Has a finite perimeter and area. Guarantees that both a global maximum and a global minimum exist for any linear objective function.
Stretches infinitely along one or more coordinate directions. While a minimum or maximum may exist, the objective value often grows without bound ($Z \to \infty$), leading to an unbounded solution.
The constraints contain mutually contradictory requirements (e.g., $x + y \le 2$ and $x + y \ge 5$). The intersection of half-planes is empty ($\mathcal{R} = \emptyset$). No solution exists.
Algorithmic Methodology: Graphing Boundaries and Finding Vertices
To solve any system of linear inequalities algebraically and graphically, execute this rigorous six-step procedure:
Step 1: Graph the Boundary Lines
Convert each inequality $a_i x + b_i y \le c_i$ into an equation $a_i x + b_i y = c_i$. Find the intercepts $(0, c_i/b_i)$ and $(c_i/a_i, 0)$ to plot the line. Use a solid line for non-strict inequalities ($\le, \ge$) and a dashed line for strict inequalities ($<, >$).
Step 2: Test Half-Planes with an Anchor Point
Select a test point not lying on the boundary line—typically the origin $(0, 0)$. If substituting $(0, 0)$ satisfies the inequality, shade the half-plane containing the origin; if not, shade the opposite half-plane.
Step 3: Account for Non-Negativity Constraints
In real-world linear programming, decision variables represent physical quantities (units produced, hours worked) that cannot be negative. The constraints $x \ge 0$ and $y \ge 0$ restrict the feasible region strictly to Quadrant I.
Step 4: Compute Boundary Intersections
Solve the 2x2 system of linear equations for every pairwise combination of boundary lines:
Step 5: Filter for Feasible Vertices
Test each candidate intersection point against all remaining constraints. Discard any intersection point that violates even a single inequality. The surviving coordinates constitute the extreme vertices of the feasible region.
Linear Optimization: Evaluating the Objective Function Z
Once the set of corner points $V = {V_1, V_2, \dots, V_k}$ is determined, finding the optimal solution to the linear program requires constructing an evaluation table. For each vertex coordinate $(x_j, y_j)$, compute:
The largest evaluated scalar $Z$ provides the absolute maximum, and the smallest evaluated scalar provides the absolute minimum. For related coordinate geometry and line calculations, visit our equation of a line calculator and slope calculator.
Comprehensive Worked Examples with Complete Vertex Calculations
Maximize $Z = 5x + 4y$ subject to:
Step 1: Intersect Boundary Lines with Coordinate Axes
- Intersection of $x=0$ and $y=0$: Vertex $V_1 = (0, 0)$.
- Line (2) $3x + 2y = 12$ with $y=0$: $3x = 12 \implies x = 4$. Vertex $V_2 = (4, 0)$.
- Line (1) $x + 2y = 8$ with $x=0$: $2y = 8 \implies y = 4$. Vertex $V_3 = (0, 4)$.
Step 2: Intersect Constraints (1) and (2)
Subtract $(x + 2y = 8)$ from $(3x + 2y = 12)$: $2x = 4 \implies x = 2$. Substitute $x = 2$ into (1): $2 + 2y = 8 \implies 2y = 6 \implies y = 3$. Vertex $V_4 = (2, 3)$.
Step 3: Evaluate Objective Function $Z = 5x + 4y$
| Vertex | Calculation (5x + 4y) | Value of Z | Conclusion |
|---|---|---|---|
| (0, 0) | 5(0) + 4(0) | 0 | Minimum |
| (4, 0) | 5(4) + 4(0) | 20 | - |
| (0, 4) | 5(0) + 4(4) | 16 | - |
| (2, 3) | 5(2) + 4(3) = 10 + 12 | 22 | Maximum Optimal Point |
Real-World Applications in Operations Research and Economics
Feasible region analysis forms the computational engine behind modern logistics, manufacturing, and financial portfolio management:
Supply Chain Resource Allocation
Manufacturers produce multiple product lines competing for finite warehouse space, raw materials, and assembly labor. Linear programming delineates the boundary of possible production outputs and pinpoints the exact product mix maximizing revenue.
Diet & Nutritional Blending
Originally formulated by George Stigler, the diet problem determines the least expensive combination of foods that satisfies minimum daily requirements for calories, proteins, and vitamins, solved by minimizing an objective function over an unbounded nutrition feasible region.
Common Analytical Pitfalls and Graphing Errors
Inequality Sign Reversal on Negative Division
Dividing an inequality by a negative coefficient (such as dividing $-2y \le 6$ by $-2$) requires reversing the inequality sign to $y \ge -3$. Failing to reverse this sign inverts the shaded half-plane completely.
Assuming the Optimum is Always at (0, 0)
While $(0, 0)$ is often a vertex under non-negativity constraints, it is rarely the maximum unless all objective coefficients are negative. Always evaluate every valid corner point vertex methodically.
Lead Developer & Founder of Basic Math Tools. Specializes in browser-native computational algorithms and applied mathematics.
Mathematics & curriculum specialists. Audited against standard algebraic and arithmetic principles.