Linear inequalities show up everywhere in optimization problems. If you have a budget constraint, a time constraint, and a resource constraint, each one is an inequality. The feasible region -- where all constraints are satisfied simultaneously -- is the shaded area where all inequalities overlap. Finding the optimal solution within that region is what linear programming does.
But understanding why the optimal solution sits at a vertex of the feasible region, or why adding a constraint can dramatically change the answer, is much easier when you can see the inequalities graphed.
How inequality graphing works
A linear inequality like y >= 2x + 1 divides the plane into two half-planes. The boundary line y = 2x + 1 separates them. Points above the line satisfy the inequality; points below it do not.
To graph an inequality:
- Graph the boundary line (solid for >= or <=, dashed for > or <)
- Shade the side that satisfies the inequality
- Test a point (typically the origin) to verify which side to shade
For y >= 2x + 1, test (0, 0): is 0 >= 2(0) + 1? Is 0 >= 1? No. So the origin is not in the solution set, and you shade the opposite side.
Systems of inequalities
Real problems involve multiple inequalities. A manufacturing optimization might look like:
x >= 0 (can't produce negative units)
y >= 0 (same)
2x + y <= 100 (labor hours constraint)
x + 3y <= 120 (materials constraint)
Graphing all four inequalities, the feasible region is the polygon where all shaded areas overlap. For these constraints, it is a quadrilateral with vertices at (0, 0), (50, 0), (0, 40), and (36, 28).
The optimal solution for any linear objective function (like "maximize profit = 5x + 8y") always occurs at a vertex of the feasible region. This is a fundamental theorem of linear programming, and seeing the feasible region graphically makes it intuitive: the objective function is a family of parallel lines, and the last line to touch the feasible region as you slide it in the optimization direction will touch a vertex.
Beyond two dimensions
Real optimization problems have dozens or hundreds of variables. You cannot graph 50-dimensional inequalities. But understanding the 2D case builds the intuition for the general case: the feasible region is a polytope (higher-dimensional polygon), the optimal solution is at a vertex, and the simplex algorithm essentially walks along edges of this polytope from vertex to vertex, improving the objective at each step.
Practical applications
Budget allocation. You have $10,000 to split between advertising and development. Each dollar in advertising generates 2 units of reach. Each dollar in development generates 3 units of product quality. You need at least 5,000 units of reach and at least 12,000 units of quality. Graph the constraints to find your feasible allocations.
Scheduling. You have 40 hours per week. Each client project takes a minimum of 5 hours. You need at least 10 hours for internal work. You want to maximize billable hours. The constraints define a feasible region; the optimal schedule is at a vertex.
Diet optimization. This was actually one of the first applications of linear programming. Minimize food cost while meeting minimum nutritional requirements. Each food has a cost, calories, protein, and vitamin content. The constraints are minimum daily nutritional needs, and the objective is minimum total cost.
I built a graphing inequalities calculator at zovo.one/free-tools/graphing-inequalities-calculator that plots systems of linear inequalities, shades the feasible region, and identifies the vertices. Enter your constraints, see the feasible region visually, and understand your optimization problem before trying to solve it algebraically.
I'm Michael Lip. I build free developer tools at zovo.one. 500+ tools, all private, all free.
Top comments (0)