Linear Programming

By the end of this lesson, you will be able to set up and solve linear programming problems: define the objective function and constraints, graph the feasible region, identify corner points, and evaluate the objective function to find the optimal solution.

The Big Idea

Linear programming finds the maximum or minimum value of a linear function subject to a set of linear inequality constraints. This is operations research — the mathematics behind scheduling, logistics, manufacturing, and resource allocation used by every major company. The fundamental theorem guarantees that the optimal solution always occurs at a corner point (vertex) of the feasible region.

Key Terms

Objective function: the linear function to maximize or minimize (e.g., profit $P = 3x + 5y$ or cost $C = 2x + y$).

Constraints: the system of linear inequalities defining the restrictions.

Feasible region: the set of all points satisfying all constraints simultaneously (a convex polygon).

Corner points (vertices): the intersection points of the boundary lines of the feasible region.

Fundamental Theorem: the optimal value of the objective function occurs at a corner point of the feasible region.

The Procedure

1. Define variables for what you're optimizing
2. Write the objective function
3. Write all constraint inequalities
4. Graph the feasible region (shade appropriately)
5. Find all corner points (solve pairs of boundary equations)
6. Evaluate the objective function at each corner point
7. Select the maximum or minimum

Example 1 — Profit Maximization

A factory makes tables ($x$) and chairs ($y$). Profits are $40/table and $25/chair.

Constraints:

• Wood: $2x + y \leq 40$
• Labor: $x + y \leq 25$
• Non-negativity: $x \geq 0$, $y \geq 0$

Objective: Maximize $P = 40x + 25y$

Step 1 — Find corner points:

Intersection of $x = 0$ and $y = 0$: $(0, 0)$

Intersection of $2x + y = 40$ and $x = 0$: $(0, 40)$

But check: $(0, 40)$ must satisfy $x + y \leq 25$: $0 + 40 = 40 > 25$ ✗ — not feasible.