The Feasible Region: A Map Drawn by Linear Inequalities
The Building Blocks: Lines and Half-Planes
Everything begins with a line. A linear equation like $y = 2x + 1$ graphs a straight line that divides the plane into two distinct halves. When we replace the equals sign ($=$) with an inequality like $<$ (less than), $>$ (greater than), $\le$ (less than or equal to), or $\ge$ (greater than or equal to), we are no longer describing just a line, but an entire half-plane.
For example, the inequality $y \ge 2x + 1$ means "all the points whose y-coordinate is greater than or equal to $2x+1$." To graph this:
- First, graph the boundary line $y = 2x + 1$. Since the inequality is "$\ge$" (includes equality), we draw a solid line. If it were "$>$" or "$<$" (strict inequality), we would use a dashed line to show points on the line are not included.
- Next, choose a test point not on the line, like the origin $(0,0)$. Substitute it into the inequality: $0 \ge 2(0)+1$ simplifies to $0 \ge 1$, which is false.
- Because the test point made the inequality false, we shade the half-plane on the opposite side of the line from the test point. This shaded area represents all points that make the inequality true.
Forming a Region: The Intersection of Conditions
A single inequality defines a vast area. The real power emerges when we combine two or more linear inequalities into a system. The solution to the system is the set of points that satisfy all inequalities at the same time. Graphically, this is the intersection of all the shaded half-planes. This overlapping area is what we call the feasible region or simply the region defined by the system.
Let's consider a simple system with two inequalities:
- $x + y \le 4$
- $y \ge 1$
We graph each inequality on the same coordinate plane. The region where the shading from $x+y \le 4$ and the shading from $y \ge 1$ overlap is our solution. This region is often a polygon (like a triangle or quadrilateral). The corners of this polygon, where the boundary lines intersect, are called the vertices or corner points.
Regions can be bounded or unbounded. A bounded region is a polygon completely enclosed, like a triangle on all sides. An unbounded region extends infinitely in at least one direction.
Finding the Vertices: The Cornerstone of the Region
The vertices of the feasible region are critically important, especially in optimization problems. To find them algebraically, you solve the systems of equations formed by the relevant boundary lines. For a region formed by several inequalities, you check the intersection of each pair of boundary lines and then verify if that intersection point satisfies all the other inequalities in the system. If it does, it's a vertex of the feasible region.
Consider this system:
- $2x + y \le 10$
- $x + 3y \le 12$
- $x \ge 0$
- $y \ge 0$
The inequalities $x \ge 0$ and $y \ge 0$ simply mean we are restricted to the first quadrant of the coordinate plane. To find a vertex, we treat inequalities 1 and 2 as equations and solve: $2x + y = 10$ and $x + 3y = 12$. Solving this system (e.g., by substitution or elimination) gives the point $(3.6, 2.8)$. We must check that it satisfies $x \ge 0$ and $y \ge 0$, which it does. This point is one vertex. Other vertices come from intersecting each line with the axes.
| Boundary Line Intersection | Resulting Point | Is it a Vertex? | Reason |
|---|---|---|---|
| $2x+y=10$ and $x=0$ | $(0, 10)$ | No | Fails $x+3y \le 12$ because $0+3(10)=30 > 12$. |
| $2x+y=10$ and $y=0$ | $(5, 0)$ | Yes | Satisfies all four inequalities. |
| $x+3y=12$ and $x=0$ | $(0, 4)$ | Yes | Satisfies all four inequalities. |
| $x+3y=12$ and $y=0$ | $(12, 0)$ | No | Fails $2x+y \le 10$ because $2(12)+0=24 > 10$. |
| $2x+y=10$ and $x+3y=12$ | $(3.6, 2.8)$ | Yes | Satisfies all four inequalities. |
Real-World Application: The Snack Stand Dilemma
Imagine you run a small stand selling fruit cups and sandwiches. This is a classic problem in linear programming1, where we use regions defined by inequalities to make the best business decision.
Scenario: You can carry at most 20 items total (fruit cups and sandwiches combined). Each fruit cup costs you $1 to make and sells for $3. Each sandwich costs $2 to make and sells for $5. You have a budget of $30 for ingredients. You also know from experience that you need at least 5 fruit cups to meet demand. How many of each item should you prepare to maximize your profit?
Let's define our variables:
Let $x$ = number of fruit cups.
Let $y$ = number of sandwiches.
We can now translate the words into a system of linear inequalities (our constraints):
- Carrying capacity: $x + y \le 20$
- Budget constraint: The total cost is $1x + 2y$. This must be less than or equal to $30: $x + 2y \le 30$.
- Minimum demand: $x \ge 5$
- Non-negativity: You can't make a negative number of items: $y \ge 0$. (Note: $x \ge 5$ already covers $x \ge 0$).
The feasible region is the set of all integer coordinate points $(x, y)$ that satisfy all four inequalities. This region represents every possible combination of fruit cups and sandwiches you could feasibly make given your limits.
But which point gives the most profit? Profit for one fruit cup is $3 - 1 = $2. Profit for one sandwich is $5 - 2 = $3. So our total profit P is given by the linear equation: $P = 2x + 3y$.
The key principle in linear programming is that the maximum (or minimum) value of $P$ will always occur at a vertex of the feasible region. So, we find the vertices of the region defined by our inequalities, plug each $(x, y)$ into $P = 2x + 3y$, and see which gives the largest number.
For this problem, the vertices (found by solving the relevant line intersections) are approximately: $(5, 0)$, $(5, 12.5)$, $(10, 10)$, and $(20, 0)$. Since we likely can't make half a sandwich, we'd consider integer points near $(5, 12.5)$, like $(5,12)$. Checking profits:
• $(5,0)$: $P = 2(5)+3(0)=10$
• $(5,12)$: $P = 2(5)+3(12)=46$
• $(10,10)$: $P = 2(10)+3(10)=50$
• $(20,0)$: $P = 2(20)+3(0)=40$
The maximum profit of $50 is achieved at $(10, 10)$—making 10 fruit cups and 10 sandwiches. The feasible region visually showed us all possible options, and its vertices guided us directly to the optimal one.
Important Questions
A: The safest method is always the test point. Graph the line (dashed for $<$ or $>$). Pick an easy point not on the line, usually $(0,0)$. Plug its coordinates into the inequality. If the statement is TRUE, shade the side of the line that contains the test point. If FALSE, shade the opposite side. Remember, if the inequality is solved for $y$ and says "$y > ...$", it often means shade above the line, and "$y < ...$" often means shade below, but the test point is a foolproof check.
A: Yes, it's possible. An empty feasible region means there is no point that satisfies all the inequalities simultaneously. This happens when the constraints are contradictory. For example, the system $x \ge 5$ and $x \le 2$ has no solution because no number can be both greater than or equal to 5 and less than or equal to 2 at the same time. Graphically, the half-planes simply do not overlap at all.
A: This is a fundamental theorem of linear programming. The profit function $P = 2x + 3y$ is itself a linear equation. On a graph, lines of constant profit ($P = 10, P = 20, P = 50$, etc.) are all parallel lines. To maximize $P$, you want to move this profit line as far in the increasing direction as possible while it still touches the feasible region. The last point of contact as you slide the line will always be a corner (vertex) of the region, or sometimes an entire edge if the profit line is parallel to a boundary. Checking vertices is therefore an efficient way to find the optimum.
From Simple Shading to Powerful Planning
Footnote
1 Linear Programming (LP): A mathematical method used to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships (equations or inequalities). The "programming" refers to planning, not computer programming.
2 Feasible Region: The set of all possible points that satisfy a given system of constraints (inequalities). It represents all allowable or "feasible" solutions to the problem.
3 Constraint: A condition or limitation expressed as an equation or inequality that must be satisfied by the solution to a problem. In our snack stand example, budget and carrying capacity were constraints.
4 Vertex (plural: Vertices): A corner point of a polygon. In the context of a feasible region, it is the intersection point of two or more boundary lines.