flowchart LR
A[Decision variables] --> B[Linear objective]
A --> C[Linear constraints]
B --> D[Optimiser]
C --> D
D --> E[Optimal plan]
E --> F[Shadow prices]
E --> G[Sensitivity ranges]
23 Linear Programming
23.1 What Linear Programming Is
Linear programming (LP) finds the values of a set of decision variables that maximise or minimise a linear objective subject to linear equality and inequality constraints. Dantzig (1947) introduced the simplex algorithm; Kantorovich (1939) and Koopmans (1947) had earlier developed the production-planning applications that motivated the field. LP is the workhorse of prescriptive analytics whenever the quantities to decide are continuous (hours, litres, tonnes, dollars) and the objective and constraints can be written as linear functions of those quantities.
NoteWhen LP is the right tool
LP applies when (1) the decision is continuous, (2) the objective is linear in the decisions, (3) the constraints are linear in the decisions, and (4) certainty about the coefficients is acceptable for the planning horizon. Integer decisions go to Chapter 24; uncertainty-driven problems go to simulation (Chapter 26).
23.2 Standard Form
A linear program in standard form is
\[ \max_{x} \; c'x \quad \text{subject to} \quad Ax \le b, \; x \ge 0 \]
where \(x\) is the \(n\)-vector of decision variables, \(c\) is the objective cost vector, \(A\) is the \(m \times n\) constraint matrix, and \(b\) is the resource vector. Minimisation problems are converted by negating \(c\); equality constraints are converted by splitting each into a \(\le\) and a \(\ge\). Adding a non-negative slack variable to each \(\le\) constraint converts the system into canonical form \(Ax + Is = b\) with \(x, s \ge 0\), which is what the simplex algorithm operates on.
23.3 Graphical Solution
When there are exactly two decision variables, the feasible region is a polygon in the plane and the optimum always lies at one of its corners (the fundamental theorem of linear programming). Plotting the constraints and evaluating the objective at each corner is a visual way to see why.
The objective \(3 x_1 + 2 x_2\) is evaluated at each corner; the maximum (14) occurs at \((4, 0)\), which confirms the fundamental theorem and shows the constraint \(x_1 + x_2 \le 4\) is binding at the optimum.
23.4 The Simplex Algorithm
Simplex (Dantzig 1947) walks from corner to corner of the feasible polytope, moving at each step to an adjacent corner that improves the objective, and stops when no improving move remains. Under mild assumptions the optimum is reached in a finite number of steps. In practice the revised simplex implementation used by modern solvers handles thousands of variables in milliseconds. Interior-point methods (Karmarkar 1984) are an alternative that crosses the interior of the polytope and is usually faster for very large, very sparse problems. For most business-sized LPs the choice of algorithm is invisible to the user.
TipWhat the solver reports
Solvers return the optimal decision vector, the optimal objective value, the slack in each constraint (zero means the constraint is binding), and, as post-optimality output, shadow prices and sensitivity ranges (§9 and §10).
23.5 Solving with lpSolve
The lpSolve R package (Berkelaar et al. 2020) wraps a C simplex implementation and is fast enough for most teaching problems. The four arguments to lp() are the direction, the objective vector, the constraint matrix, the direction of each constraint, and the right-hand side.
The solver confirms the graphical result: \(x_1 = 4\), \(x_2 = 0\), and an objective of 14. status = 0 means an optimal solution was found; any non-zero status flags infeasibility, unboundedness, or numerical failure.
23.6 Product Mix Formulation
A factory makes chairs and tables. Each chair uses 3 hours of labour and 2 units of lumber and sells at a margin of 40; each table uses 4 hours of labour and 5 units of lumber and sells at a margin of 70. Weekly labour is capped at 240 hours and lumber at 200 units. How many of each to make?
The optimal plan is a mix of both products, with labour and lumber both used up to their caps. The formulation is the template for any LP with a bill of materials: rows of mat are resources, columns are products, and the RHS is the resource pool.
23.7 Blending and the Diet Problem
A feedlot blends two feeds at 0.25 and 0.40 per kilogram to meet minimum nutrient requirements of 20 units of protein, 15 of fat, and 30 of fibre per batch. Feed A contributes (4, 2, 3) units per kg; feed B contributes (3, 5, 4). Minimise cost subject to meeting every nutrient floor.
The cheapest feasible blend uses both feeds and brings every nutrient above its minimum. Replacing "min" with "max" and flipping the constraint directions would produce the dual shape of the problem used in diet planning and fuel blending.
23.8 Transportation Problem
Three warehouses ship to four stores. Unit transport costs and supply and demand totals are given. The transportation LP minimises total shipping cost subject to supply and demand balance.
lp.transport is a specialised wrapper that avoids having to build the full constraint matrix by hand. The optimal shipment matrix ships out exactly every warehouse’s supply and delivers exactly every store’s demand at the minimum total cost.
23.9 Sensitivity Analysis
Setting compute.sens = TRUE returns objective-coefficient ranges and right-hand-side ranges. Objective-coefficient ranges describe how far each \(c_j\) can move before the current optimal basis changes; right-hand-side ranges describe how far each \(b_i\) can move before the shadow prices change. Together they answer “how robust is the plan?” without re-running the LP.
Any objective coefficient can move between coef_from and coef_to with the current plan still optimal. Any right-hand-side can move between rhs_from and rhs_to with the current shadow price still valid; outside those ranges the LP must be re-solved.
23.10 Duality and Shadow Prices
Every LP has a dual LP with as many variables as the primal has constraints. The optimal dual values (\(y^*\)) are the shadow prices: the marginal value to the objective of relaxing each constraint’s RHS by one unit. A binding constraint has a positive shadow price; a slack constraint has a zero shadow price (complementary slackness). Shadow prices are the most actionable output of an LP because they directly price the scarce resources.
Both resources are fully used (zero slack) and therefore carry positive shadow prices. The shadow price on labour is the profit gained per additional hour of labour; multiplied by a proposed overtime cost, it tells the manager whether overtime is worth paying for.
23.11 Degeneracy and Alternative Optima
An LP has degeneracy when a basic feasible solution has a zero-valued basic variable; it has alternative optima when more than one corner of the feasible region attains the same optimal objective. Alternative optima are common when the objective line is parallel to a binding constraint: the solver returns one corner, but any convex combination of the tied corners is also optimal.
The objective is 4 at every point on the segment between \((3, 1)\) and \((1, 3)\); the solver returns one of the two corners, but the business should be told that any point on that segment gives the same value. Always flag alternative optima to stakeholders so they do not misread the returned plan as the only right answer.
23.12 Summary
A complete LP report lists the decision variables with units, the objective and its direction, the full constraint set with units, the optimal plan, the optimal objective value, binding vs slack constraints with shadow prices, objective-coefficient and RHS sensitivity ranges, and a note on any alternative optima found. Williams (2013) remains the standard reference for turning business problems into LP formulations; Hillier and Lieberman (2020) cover the full post-optimality toolkit.
| Concept | Description |
|---|---|
| Foundations | |
| LP problem definition | Maximise or minimise a linear objective under linear constraints |
| Linearity assumption | Objective and constraints linear in continuous decision variables |
| Standard form | max c'x s.t. Ax <= b, x >= 0; slacks convert to canonical form |
| Solution Methods | |
| Graphical method | Two-variable feasible polygon; optimum at a corner |
| Simplex algorithm | Corner-to-corner search; optimum reached in finite steps |
| lpSolve wrapper | lp() and lp.transport() wrap a C simplex solver in R |
| Classic Formulations | |
| Product mix | Products and resources; columns are decisions, rows are caps |
| Blending and diet | Minimum-cost blend meeting nutrient or specification floors |
| Transportation | Supplies, demands, unit costs; specialised lp.transport() |
| Post-Optimality | |
| Sensitivity ranges | Ranges of c_j and b_i for which the basis stays optimal |
| Shadow price and duality | Dual value equals marginal objective per unit of resource |
| Edge Cases and Delivery | |
| Degeneracy and alternative optima | Tied optima on a face; solver returns one corner, flag the rest |
| Slack and binding constraints | Zero slack means the constraint drives the plan; positive slack means headroom |
| Reporting checklist | Decisions, objective, constraints, plan, duals, ranges, caveats |