Historical Context & Motivation
The concept of a feasible region lies at the heart of linear programming, one of the most widely applied branches of optimization in operations research, economics, engineering, and data science. The idea of representing constraints as linear inequalities and searching for optimal solutions within their intersection emerged during the mid-twentieth century, driven by the immense logistical demands of wartime resource allocation. Understanding how to graph these regions and identify their corner points is the geometric skill that transforms abstract inequality systems into visual, intuition-building tools for decision-making.
The central geometric question that motivates this lesson is deceptively simple: given a collection of linear inequalities, what does the set of all points satisfying every inequality simultaneously look like, and where should we look for optimal values of a linear objective function? The answer, as Dantzig's simplex method revealed, is that the optimal value always occurs at a vertex (corner point) of the feasible region—making the ability to graph these regions and identify their corners an indispensable skill in finite mathematics.
Core Principles & Definitions
Before we graph anything, we need a precise vocabulary. A linear inequality in two variables is an expression of the form ax + by ≤ c (or with ≥, <, >). Each such inequality partitions the xy-plane into two half-planes separated by the boundary line ax + by = c. The feasible region is formed by intersecting all the half-planes determined by a system of such inequalities, along with any non-negativity constraints. The following foundational concepts underpin everything that follows.
Half-Plane
Feasible Region
Convexity
Corner Point (Vertex)
Bounded vs. Unbounded
Visual Explanation — Graphing a System of Inequalities
Let us consider a concrete system of inequalities and walk through the graphing process visually. The following diagram illustrates the feasible region for the system: x + y ≤ 6, x + 3y ≤ 12, x ≥ 0, and y ≥ 0. Each constraint contributes a boundary line, and the feasible region is the convex polygon formed by their intersection in the first quadrant.
To construct this diagram, we begin by graphing each boundary line—treating the inequality as an equation. We then test a convenient point (often the origin) to determine which half-plane satisfies each inequality. The feasible region is the overlap of all valid half-planes. Notice that the region is a convex polygon; this is guaranteed by the theory of linear inequalities. The corner points occur exactly where boundary lines (including the axes) intersect on the perimeter of the region. Identifying these vertices is straightforward: solve each pair of boundary equations simultaneously, and check whether the resulting point satisfies all remaining constraints.
Mathematical Framework
The procedure for graphing feasible regions and identifying corner points can be formalized into a systematic algorithm. We begin by expressing each constraint as a linear inequality, graph its boundary line, and shade the appropriate half-plane. The intersection of all shaded regions yields the feasible set. Corner points are then found by solving systems of two linear equations at a time.
The number of candidate corner points for a system of m linear inequalities (including non-negativity constraints) in two variables is at most C(m, 2) = m(m − 1)/2, since each pair of boundary lines can intersect in at most one point. However, many of these intersections will fall outside the feasible region. For practical two-variable problems, the feasible region typically has between 3 and 6 vertices, making the graphical method quite efficient.
Detailed Breakdown — The Graphing Procedure
We now present the complete step-by-step algorithm for graphing a feasible region and identifying its corner points, along with a second visual example. The procedure applies to any system of linear inequalities in two decision variables.
- Step 1 — Rewrite each constraint as a linear inequality in standard form (ax + by ≤ c or ax + by ≥ c). Include non-negativity constraints x ≥ 0 and y ≥ 0 if specified.
- Step 2 — Graph each boundary line by finding two points (typically x- and y-intercepts). Use a solid line for ≤ or ≥; use a dashed line for strict inequalities < or >.
- Step 3 — Shade the correct half-plane for each inequality. Substitute a test point (e.g., the origin) into the inequality: if it satisfies the inequality, shade the side containing the test point; otherwise, shade the opposite side.
- Step 4 — Identify the feasible region as the intersection (overlap) of all shaded half-planes. If no overlap exists, the system is infeasible.
- Step 5 — Find corner points by solving pairs of boundary equations simultaneously. Verify each candidate point satisfies all constraints.
- Step 6 — Evaluate the objective function (if applicable) at each corner point to determine the optimal solution.
In this second example, the corner point (10/3, 10/3) is found by solving the system 2x + y = 10 and x + 2y = 10 simultaneously. Subtracting the second equation from the first gives x − y = 0, hence x = y. Substituting back yields 3x = 10, so x = y = 10/3. This intersection point lies within the first quadrant and satisfies both constraints, confirming it as a valid vertex. The remaining vertices arise from intersections of the constraint lines with the coordinate axes.
Worked Example — Complete Feasible Region Analysis
A small manufacturing company produces two products, A and B. Each unit of A requires 1 hour of labor and 2 units of raw material. Each unit of B requires 3 hours of labor and 1 unit of raw material. The company has 15 hours of labor and 10 units of raw material available per day. The company also wants to produce at least 1 unit of product B per day. Graph the feasible region, identify all corner points, and determine which corner maximizes the profit function P = 5x + 4y, where x is the number of units of A and y is the number of units of B.
This worked example illustrates the full power of the graphical method. By systematically graphing constraints, identifying the feasible polygon, computing its vertices, and evaluating the objective function only at those vertices, we efficiently located the optimal production plan. The company should produce 3 units of A and 4 units of B daily to maximize profit at $31.
Strengths, Limitations & Common Pitfalls
| Aspect | Strengths | Limitations |
|---|---|---|
| Dimensionality | Provides clear geometric intuition in two variables; the feasible region and corner points are visible at a glance. | Cannot be applied beyond three variables; for higher dimensions, algebraic methods (simplex, interior-point) are required. |
| Accuracy | Algebraic computation of corner points gives exact rational answers without rounding error. | Reading coordinates from a hand-drawn graph can introduce estimation errors; always verify algebraically. |
| Efficiency | For small systems (2–4 constraints), the graphical method is fast and requires no technology. | For systems with many constraints, enumerating all pairwise intersections becomes tedious; the simplex method scales better. |
| Special cases | Graphing reveals infeasible systems (empty intersections) and unbounded regions immediately through visual inspection. | Degenerate cases—where multiple constraints intersect at the same point, or the objective function is parallel to an edge—require careful interpretation. |
Connection to the Simplex Method and Higher Dimensions
The graphical method for two-variable problems is not merely pedagogical—it directly mirrors the logic of the simplex algorithm, the workhorse of linear programming in higher dimensions. In two dimensions, the feasible region is a convex polygon, and the simplex method moves from one vertex to an adjacent vertex along an edge, improving the objective function at each step. In n dimensions, the feasible region is a convex polytope (the higher-dimensional analogue of a polygon), and the simplex method traverses its edges in exactly the same fashion. The Corner Point Theorem generalizes: any linear function on a bounded polytope achieves its optimum at a vertex.
| Feature | Graphical Method (2D) | Simplex Method (nD) |
|---|---|---|
| Feasible set | Convex polygon in ℝ² | Convex polytope in ℝⁿ |
| Vertices found by | Pairwise intersection of boundary lines | Basic feasible solutions (BFS) of the system Ax = b |
| Optimality check | Evaluate Z at each vertex; compare values | Reduced cost coefficients ≥ 0 for maximization |
| Scalability | Limited to 2 (occasionally 3) decision variables | Thousands of variables and constraints |
| Primary value | Geometric insight and conceptual understanding | Computational power for real-world applications |
In courses on finite mathematics, the graphical method serves as the conceptual bridge to the simplex algorithm. Once you understand that the simplex method is, in essence, "walking along the edges of a higher-dimensional polygon, checking corners for the best objective value," the tabular mechanics of the algorithm become far more intuitive. Additionally, concepts such as sensitivity analysis and shadow prices have elegant geometric interpretations in two dimensions: changing a constraint's right-hand side shifts its boundary line, potentially altering the feasible region's shape and moving the optimal vertex.
Practice Problems
Summary & Key Concepts
Graphing feasible regions requires translating each constraint into a linear inequality, graphing its boundary line, determining the correct half-plane via a test point, and identifying the intersection of all half-planes as a convex polygon (or unbounded region). Corner points are located by solving pairs of boundary equations simultaneously, then verifying that each candidate satisfies all constraints.
The Corner Point Theorem guarantees that the optimal value of any linear objective function over a bounded feasible region occurs at a vertex, reducing the infinite search problem to a finite comparison. This graphical approach provides the geometric intuition underlying the simplex algorithm, which extends the same vertex-walking strategy to problems with arbitrarily many variables and constraints in higher-dimensional spaces.