What Is Linear Programming?
Linear programming (LP) is an optimization technique for allocating limited resources to achieve the best possible outcome — maximum profit, minimum cost, best utilization — when both the objective and the limits can be expressed as linear relationships. It is one of the most widely applied tools in operations research, used in production planning, blending, scheduling, logistics, and finance.
Formulating an LP Model
Every LP has three ingredients:
- Decision variables — the quantities under your control (e.g., x₁ = units of product A, x₂ = units of product B).
- Objective function — the linear quantity to maximize or minimize (e.g., maximize profit Z = 40x₁ + 30x₂).
- Constraints — linear inequalities or equalities expressing resource limits and requirements, plus non-negativity (x₁, x₂ ≥ 0).
Example. A shop makes two products. Each unit of A needs 2 hours of labor and 1 unit of material; each unit of B needs 1 hour and 3 units of material. There are 100 labor hours and 90 material units available. Profit is $40 per A and $30 per B. The model is:
Maximize Z = 40x₁ + 30x₂
subject to: 2x₁ + x₂ ≤ 100 (labor); x₁ + 3x₂ ≤ 90 (material); x₁, x₂ ≥ 0
The Graphical Method
With only two decision variables, an LP can be solved by graphing. Each constraint is a line; the region satisfying all constraints simultaneously is the feasible region, a convex polygon. A key theorem of LP states that the optimum, if it exists, always occurs at a vertex (corner point) of the feasible region. So you evaluate the objective at each corner and pick the best:
| Corner point (x₁, x₂) | Z = 40x₁ + 30x₂ |
|---|---|
| (0, 0) | 0 |
| (50, 0) | 2000 |
| (0, 30) | 900 |
| (42, 16) | 2160 (optimum) |
The corner-point principle is the conceptual heart of all LP solution methods.
The Simplex Method
The graphical method breaks down beyond two variables. The simplex method, developed by George Dantzig, is the workhorse algorithm for real problems. It starts at a feasible vertex and repeatedly moves to an adjacent vertex that improves the objective, stopping when no neighboring vertex is better — which, because the feasible region is convex, guarantees the global optimum. Mechanically, simplex works on a tableau: it converts inequalities to equalities with slack variables, then pivots, swapping variables in and out of the "basis" until the optimality condition is met. Modern solvers handle thousands of variables in this framework.
Sensitivity Analysis and Shadow Prices
The optimal solution is only the beginning. Sensitivity analysis asks how the solution responds to changes in the data:
- Objective coefficient ranges — how much a profit/cost coefficient can change before the optimal mix changes.
- Right-hand-side ranges — how much a resource limit can change while the shadow price stays valid.
- Shadow price (dual value) — the change in the optimal objective per one-unit increase in a binding constraint's right-hand side. If labor's shadow price is $15, an extra labor hour is worth $15 of additional profit — telling you exactly how much you should be willing to pay for more.
A constraint is binding if it is met with equality at the optimum (the resource is fully used); a non-binding constraint has slack and a shadow price of zero. Shadow prices come from LP duality — every LP has a dual problem whose solution provides these values.
Special LP Structures
The Transportation Problem
The transportation problem minimizes shipping cost from m supply sources to n demand destinations. Given supply capacities, demand requirements, and per-unit costs cij, it finds the shipment quantities xij that satisfy all demand from available supply at least cost. Its special structure permits efficient methods (Northwest Corner, Vogel's Approximation for an initial solution; MODI/stepping-stone for optimization).
The Assignment Problem
The assignment problem is a special case where each source is matched to exactly one destination — assigning n workers to n jobs to minimize total cost or time. The Hungarian algorithm solves it efficiently. Both transportation and assignment problems have integer-valued optimal solutions automatically, even though they are solved as LPs.
Integer and Beyond
When variables must be whole numbers (you cannot build half a machine), the problem becomes integer programming, solved by branch-and-bound. When some variables are continuous and others integer, it is mixed-integer programming. These are harder than pure LP but build directly on the LP framework.
LP in Project and Operations Planning
LP-style optimization underpins many planning problems, including resource-constrained scheduling, which connects to network methods like CPM. For project scheduling and crashing decisions — where you trade cost against time along the critical path — see the CPM/PERT calculator, which applies optimization logic to project networks.
Best Practices in LP Modeling
- Define decision variables precisely — ambiguous variables produce wrong models.
- Check linearity — if a relationship is genuinely nonlinear, LP is the wrong tool.
- Read the sensitivity report — shadow prices often deliver more managerial insight than the optimal solution itself.
- Watch for degeneracy and alternate optima — multiple optimal solutions can exist, offering flexibility.