59  Linear programming

The best answer in a constrained space

A factory can make two products — call them chairs and tables. Each chair uses 2 board-hours of cutting time and 1 hour of finishing. Each table uses 1 board-hour of cutting and 3 hours of finishing. The factory has 8 cutting hours and 9 finishing hours available per day. Chairs sell at a $30 margin; tables at $50. How many of each should it make?

This is not a puzzle you can answer by intuition. Make only chairs and you run out of cutting time. Make only tables and finishing is the bottleneck. The mix that squeezes out the most profit sits somewhere in the middle, at a specific corner of the region defined by those constraints — and that is exactly what linear programming finds.

59.1 What this chapter helps you do

Symbols to keep handy

These are the bits of notation you'll see a lot. If a line of symbols feels like a fence, read it out loud once, then keep going.

  • ^: objective function — inner product of cost/profit vector with decision vector

  • A : system of linear inequality constraints

Definitions to keep handy

These are the words we keep coming back to. If one feels slippery, come back here and steady it before you push on.

  • linear programme (LP): An optimisation problem where the objective and all constraints are linear.

  • decision variables: The quantities you get to choose.

  • constraints: The limits your choices must satisfy (resources, requirements, bounds).

  • feasible region: The set of all choices that satisfy the constraints.

  • objective function: The thing you’re trying to maximise or minimise (profit, cost, time, etc.).

  • slack variable: A bookkeeping variable that turns an inequality into an equality by measuring unused resource.

Here is the main move this chapter is making, in plain terms. You do not need to be fast. You just need to keep the thread.

  • Coming in: You want to maximise or minimise something subject to constraints. The relationships are all linear.

  • Leaving with: Every LP has a feasible region that is a convex polytope. The optimum is always at a vertex. The simplex method walks the vertices efficiently.

59.2 LP formulation

A linear programme (LP) has three components: decision variables, an objective function, and constraints.

Decision variables. These are the quantities you control. Write them as x_1, x_2, \ldots, x_n — read as “x-sub-one, x-sub-two, up to x-sub-n” — or as the vector \mathbf{x}, read as “bold x.” For the factory problem, x_1 is the number of chairs made per day and x_2 is the number of tables.

Objective function. This is what you are optimising. It is always a linear combination of the decision variables: z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n, written compactly as z = \mathbf{c}^\top \mathbf{x}, read “z equals c-transpose times x.” The coefficients \mathbf{c} are your profit margins (for maximisation) or costs (for minimisation).

Constraints. Limits on what the variables can be. Each constraint is a linear inequality: a_{i1} x_1 + a_{i2} x_2 + \cdots \leq b_i. Non-negativity \mathbf{x} \geq \mathbf{0} — read “x is non-negative” — is almost always included separately; you cannot make a negative number of chairs.

The factory problem in LP form:

\text{maximise} \quad z = 30x_1 + 50x_2

subject to:

2x_1 + x_2 \leq 8 \qquad \text{(cutting hours)} x_1 + 3x_2 \leq 9 \qquad \text{(finishing hours)} x_1, x_2 \geq 0

Standard form. The simplex method requires equality constraints. Convert each \leq constraint to an equation by adding a slack variable s_i \geq 0, read “slack variable i.” Slack absorbs the difference between the left side and the right side:

2x_1 + x_2 + s_1 = 8, \quad s_1 \geq 0 x_1 + 3x_2 + s_2 = 9, \quad s_2 \geq 0

Now all constraints are equations, all variables are non-negative, and the objective is linear. This is standard form: \text{maximise } \mathbf{c}^\top\mathbf{x} subject to A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}.

A second example: diet/resource allocation. A hospital nutrition service needs to provide at least 60 g of protein, at least 800 mg of calcium, and at most 2000 kcal per patient per day from two food types. Food A costs $1.20 per unit, food B costs $0.80 per unit. Formulate the LP to minimise daily cost.

Let x_1 = units of food A, x_2 = units of food B.

Food A Food B Requirement
Protein (g/unit) 15 10 ≥ 60
Calcium (mg/unit) 200 150 ≥ 800
Energy (kcal/unit) 400 300 ≤ 2000
Cost ($/unit) 1.20 0.80 minimise

\text{minimise} \quad z = 1.20x_1 + 0.80x_2

subject to:

15x_1 + 10x_2 \geq 60 200x_1 + 150x_2 \geq 800 400x_1 + 300x_2 \leq 2000 x_1, x_2 \geq 0

For \geq constraints, introduce surplus variables s_i \geq 0: 15x_1 + 10x_2 - s_1 = 60. The minus sign makes s_i the excess above the minimum. This means a surplus variable records how far you are above a required minimum, rather than how much unused capacity remains below a maximum.

Note that the diet problem’s standard form, with its surplus variables and \geq constraints, is not directly ready for the simplex method as presented below. With surplus variables, the origin is no longer a feasible starting point (it violates the minimum requirements), and finding an initial basic feasible solution requires an additional technique — artificial variables — that is covered in more advanced treatments. The simplex worked example uses only \leq constraints to keep the starting point clear.

59.3 Graphical method

For two decision variables you can draw the feasible region — the set of all (x_1, x_2) satisfying every constraint — and read off the optimum. More importantly, you can see the geometry that the simplex method will exploit algebraically when there are too many variables to draw.

For the factory problem, plot each constraint boundary:

  • 2x_1 + x_2 = 8: line through (4, 0) and (0, 8). Feasible side: below/left.
  • x_1 + 3x_2 = 9: line through (9, 0) and (0, 3). Feasible side: below/left.
  • x_1, x_2 \geq 0: first quadrant only.

The feasible region is a convex polygon — a quadrilateral with four vertices: (0,0), (4,0), (3,2), and (0,3).

Corner-point theorem. If an LP has an optimal solution, there is an optimal solution at a vertex (corner point) of the feasible region. This is the foundational geometric fact: the objective function z = 30x_1 + 50x_2 is a family of parallel lines (iso-profit lines). As you push the line in the direction of increasing profit, the last point of contact with the feasible region is a vertex.

Evaluate the objective at each vertex:

Vertex z = 30x_1 + 50x_2
(0, 0) 0
(4, 0) 120
(3, 2) 190
(0, 3) 150

Maximum profit is $190 per day, achieved by making 3 chairs and 2 tables.

The intersection point (3, 2) comes from solving 2x_1 + x_2 = 8 and x_1 + 3x_2 = 9 simultaneously. Subtract twice the second from the first: -5x_2 = -10, so x_2 = 2, x_1 = 3.

Why the optimum is always at a vertex

The feasible region of an LP is a convex polytope — any two feasible points can be connected by a straight line that stays entirely inside the region. The objective function is linear, so it increases at a constant rate in one direction. If the optimum were in the interior, you could always move a little further in the improving direction and still stay feasible, reaching a higher objective value. The only place where you genuinely cannot improve further is a boundary. And on a boundary, you can keep moving along the edge until you hit a vertex. This is why the simplex method only needs to visit vertices.

Use the sliders to watch the feasible region change and see the optimum stay locked to a corner.

What the graphical method shows directly is what the simplex method does systematically: start at one vertex (here, the origin), check whether any neighbour is better, move to the best neighbour, and repeat. The graphical picture makes the logic self-evident. The simplex method turns that logic into algebra so it can work in a hundred dimensions instead of two.

59.4 Simplex method

The graphical method breaks down beyond two variables. The simplex method does the same thing — walk from vertex to vertex, improving the objective each step — algebraically, using the tableau.

Setup: slack variables and initial tableau. Return to the factory problem in standard form with x_1, x_2 (original variables) and s_1, s_2 (slacks):

2x_1 + x_2 + s_1 = 8 x_1 + 3x_2 + s_2 = 9 z = 30x_1 + 50x_2 \quad \Longrightarrow \quad -30x_1 - 50x_2 + z = 0

The basic feasible solution (BFS) at the origin: set non-basic variables x_1 = x_2 = 0, read off basic variables s_1 = 8, s_2 = 9, z = 0. This is the vertex (0, 0).

Initial tableau:

\begin{array}{c|cccc|c} \text{Basic} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & 1 & 1 & 0 & 8 \\ s_2 & 1 & 3 & 0 & 1 & 9 \\ \hline z & -30 & -50 & 0 & 0 & 0 \end{array}

Pivot selection. Look at the objective row (bottom row). The most negative coefficient is -50 in the x_2 column: x_2 enters the basis. The column x_2 is the entering column.

To choose the leaving variable, compute the minimum ratio: \text{RHS} / \text{entering-column coefficient} for rows with positive pivot-column entries only. Rows with zero or negative entries in the pivot column are skipped: a zero entry means increasing x_2 has no effect on that constraint, and a negative entry means the constraint becomes easier to satisfy as x_2 increases — neither constrains the move.

\frac{8}{1} = 8 \qquad \frac{9}{3} = 3

Minimum ratio is 3, so s_2 leaves. The pivot element is the entry in row s_2, column x_2: that is 3.

Pivot operation. Divide the s_2 row by 3 to make the pivot element 1:

\text{new row 2}: \quad \tfrac{1}{3}x_1 + x_2 + 0 \cdot s_1 + \tfrac{1}{3}s_2 = 3

Eliminate x_2 from every other row by adding/subtracting multiples of the new row 2:

  • Row 1 \leftarrow Row 1 - 1 \times new row 2: (2 - \frac{1}{3})x_1 + 0 \cdot x_2 + s_1 - \frac{1}{3}s_2 = 8 - 3 \Rightarrow \tfrac{5}{3}x_1 + s_1 - \tfrac{1}{3}s_2 = 5

  • Objective row \leftarrow Obj row + 50 \times new row 2: (-30 + \frac{50}{3})x_1 + 0 \cdot x_2 + 0 \cdot s_1 + \frac{50}{3}s_2 = 150 \Rightarrow -\tfrac{40}{3}x_1 + \tfrac{50}{3}s_2 = 150

Tableau after first pivot (x_2 enters, s_2 leaves):

\begin{array}{c|cccc|c} \text{Basic} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 5/3 & 0 & 1 & -1/3 & 5 \\ x_2 & 1/3 & 1 & 0 & 1/3 & 3 \\ \hline z & -40/3 & 0 & 0 & 50/3 & 150 \end{array}

Current BFS: x_1 = 0, x_2 = 3, s_1 = 5, s_2 = 0, z = 150. This is vertex (0, 3).

Second pivot. Most negative objective coefficient: -40/3 in the x_1 column. x_1 enters. Minimum ratio:

\frac{5}{5/3} = 3 \qquad \frac{3}{1/3} = 9

s_1 leaves. Pivot element: 5/3. Divide row 1 by 5/3:

\text{new row 1}: \quad x_1 + 0 \cdot x_2 + \tfrac{3}{5}s_1 - \tfrac{1}{5}s_2 = 3

Eliminate x_1 from other rows:

  • Row 2 \leftarrow Row 2 - \frac{1}{3} \times new row 1: 0 \cdot x_1 + x_2 - \tfrac{1}{5}s_1 + \tfrac{2}{5}s_2 = 2

  • Obj row \leftarrow Obj row + \frac{40}{3} \times new row 1: 0 \cdot x_1 + 8 \cdot s_1 + 14 \cdot s_2 = 190

    Let’s be precise: -\tfrac{40}{3} + \tfrac{40}{3} \cdot 1 = 0; s_1 coefficient: 0 + \tfrac{40}{3} \cdot \tfrac{3}{5} = 8; s_2 coefficient: \tfrac{50}{3} + \tfrac{40}{3} \cdot (-\tfrac{1}{5}) = \tfrac{50}{3} - \tfrac{8}{3} = 14; RHS: 150 + \tfrac{40}{3} \cdot 3 = 150 + 40 = 190.

Final tableau:

\begin{array}{c|cccc|c} \text{Basic} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline x_1 & 1 & 0 & 3/5 & -1/5 & 3 \\ x_2 & 0 & 1 & -1/5 & 2/5 & 2 \\ \hline z & 0 & 0 & 8 & 14 & 190 \end{array}

All objective-row coefficients are non-negative. Termination condition met. Optimal solution: x_1 = 3, x_2 = 2, z = 190. This means there is no adjacent basic feasible solution that can improve the objective any further, so the current vertex is optimal.

This matches the graphical answer exactly.

Why simplex terminates

Each pivot strictly improves the objective (assuming no degeneracy — no zero RHS values). There are finitely many vertices. So the method must reach an optimum in a finite number of steps. In practice, simplex visits far fewer vertices than the total count even for large LPs.

Use the stepper to see how simplex moves from one basic feasible solution to the next by pivoting on an entering column and a leaving row.

59.5 Duality

Every LP — the primal — has a companion LP called the dual. The dual is not just a mathematical curiosity; it has direct economic meaning and provides a powerful optimality check.

Constructing the dual. Start from the primal in standard inequality form:

\text{maximise} \quad \mathbf{c}^\top \mathbf{x} \quad \text{subject to} \quad A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0}

The dual introduces one dual variable y_i — read “y-sub-i” — for each primal constraint. The dual is:

\text{minimise} \quad \mathbf{b}^\top \mathbf{y} \quad \text{subject to} \quad A^\top \mathbf{y} \geq \mathbf{c},\ \mathbf{y} \geq \mathbf{0}

The roles reverse: primal constraints become dual variables, primal variables become dual constraints, primal objective coefficients become dual RHS values, and primal RHS values become dual objective coefficients. The maximisation becomes minimisation.

Dual of the factory problem. Primal: maximise 30x_1 + 50x_2 subject to 2x_1 + x_2 \leq 8, x_1 + 3x_2 \leq 9, x_1, x_2 \geq 0.

Let y_1, y_2 be the dual variables (one per primal constraint):

\text{minimise} \quad 8y_1 + 9y_2

subject to:

2y_1 + y_2 \geq 30 \qquad \text{(column 1 of } A^\top\text{)} y_1 + 3y_2 \geq 50 \qquad \text{(column 2 of } A^\top\text{)} y_1, y_2 \geq 0

Weak duality theorem. For any primal feasible \mathbf{x} and any dual feasible \mathbf{y}:

\mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top \mathbf{y}

Proof. The dual constraint says A^\top\mathbf{y} \geq \mathbf{c}, meaning each component satisfies (A^\top\mathbf{y})_j \geq c_j. Since x_j \geq 0, multiplying through and summing over all j gives \mathbf{c}^\top \mathbf{x} \leq (A^\top\mathbf{y})^\top \mathbf{x} = \mathbf{y}^\top A\mathbf{x}. The primal constraint A\mathbf{x} \leq \mathbf{b} combined with \mathbf{y} \geq \mathbf{0} then gives \mathbf{y}^\top A\mathbf{x} \leq \mathbf{y}^\top \mathbf{b} = \mathbf{b}^\top\mathbf{y}. Chaining both inequalities: \mathbf{c}^\top \mathbf{x} \leq \mathbf{b}^\top\mathbf{y}. \square

The strong duality theorem (proved via simplex theory) says the inequality is tight at optimality: primal and dual optimal values are equal.

Economic interpretation: shadow prices. The optimal dual variables have a direct meaning. y_1 is the shadow price of the first constraint (cutting hours): it tells you how much the optimal objective increases if you add one unit of that resource. At optimality, y_1 = 8 and y_2 = 14 — each additional cutting hour is worth $8, each additional finishing hour is worth $14. You can verify: 8y_1 + 9y_2 = 8 \times 8 + 9 \times 14 = 64 + 126 = 190. Dual optimal matches primal optimal — strong duality holds. This means the dual variables are not abstract extras: they price the scarce resources in exactly the units of the original objective.

Complementary slackness. At optimality, either a primal constraint is tight (active, A_i \mathbf{x} = b_i) or the corresponding dual variable is zero (y_i = 0); and either a dual constraint is tight or the corresponding primal variable is zero. Formally: y_i(b_i - A_i\mathbf{x}) = 0 and (A^\top\mathbf{y} - \mathbf{c})_j x_j = 0 for all i, j. This gives you a system of equations to verify optimality without running the full simplex.

59.6 Sensitivity analysis

The optimal basis found by simplex remains optimal as long as the problem data stays within certain ranges. If the profit margin on x_1 changes from 30 to 30 + \Delta, the basis \{x_1, x_2\} stays optimal while the objective-row coefficient of s_1 (currently 8) remains non-negative and the coefficient of s_2 (currently 14) remains non-negative. The x_1 basic row is [1, 0, 3/5, -1/5, 3], so changing c_1 by \Delta shifts the s_1 coefficient to 8 - \tfrac{3}{5}\Delta and the s_2 coefficient to 14 + \tfrac{1}{5}\Delta. Requiring both to remain non-negative: 8 - \tfrac{3}{5}\Delta \geq 0 \Rightarrow \Delta \leq \tfrac{40}{3} and 14 + \tfrac{1}{5}\Delta \geq 0 \Rightarrow \Delta \geq -70. The basis is stable for -70 \leq \Delta \leq \tfrac{40}{3}, i.e., c_1 \in [-40, 43\tfrac{1}{3}]. Similarly, if the RHS b_1 = 8 changes, the solution coordinates shift but the same basis remains feasible as long as all basic variables stay non-negative — the range can be read from the current tableau’s column for s_1. This analysis is done without re-running simplex.

59.7 Where this goes

Chapter 2 of this section develops network flow problems — shortest path, maximum flow, minimum cost flow — all of which can be formulated as LPs with special structure (network matrices) that allows faster algorithms than general simplex. Network LPs arise everywhere: logistics, circuit analysis, pipeline routing.

The broader field of integer programming (mixed-integer LP) handles the case where some or all variables must be integers — scheduling problems, facility location, combinatorial optimisation. Branch-and-bound solves these by solving a sequence of LP relaxations. The LP theory in this chapter is the computational core of those methods.

Where LP shows up

  • A refinery blends crude feedstocks to meet fuel-grade specifications at minimum cost — an LP with 50–500 variables, solved daily.
  • An airline schedules crews to cover flights while meeting duty-time regulations — an integer LP with millions of variables in practice.
  • A fund manager maximises expected portfolio return subject to risk limits and position constraints — LP or quadratic programming depending on the risk model.
  • A nutritionist formulates minimum-cost meal plans meeting dietary requirements — the diet problem, which drove early LP development.
  • A chip manufacturer allocates fab capacity across product lines to maximise margin — LP with supply chain constraints.

59.8 Exercises

These are puzzles. Each has a clean optimal solution. The interesting work is in the formulation — translating the situation into variables, objective, and constraints — and in executing the simplex steps carefully.

Exercise 1. A workshop makes two products, shelves and benches. Each shelf uses 3 kg of timber and 1 hour of labour. Each bench uses 2 kg of timber and 4 hours of labour. The workshop has 24 kg of timber and 16 hours of labour available per week. Profit is $20 per shelf and $45 per bench. Formulate the LP to maximise weekly profit.

Exercise 2. Solve the LP from Exercise 1 graphically. Plot both constraint boundaries, shade the feasible region, evaluate the objective at every vertex, and identify the optimal solution.

Exercise 3. Convert the LP from Exercise 1 to standard form by introducing slack variables. Write out the full system of equality constraints and identify the initial basic feasible solution (the origin vertex).

Exercise 4. Solve the following LP using the simplex tableau method. Show all pivots.

\text{maximise} \quad z = 5x_1 + 4x_2

subject to:

6x_1 + 4x_2 \leq 24 x_1 + 2x_2 \leq 6 x_1, x_2 \geq 0

Exercise 5. Write the dual of the LP in Exercise 4. Then use complementary slackness to find the dual optimal solution (y_1, y_2). Verify strong duality by checking that primal and dual objective values agree at optimality.

Exercise 6. In Exercise 4, the optimal basis has x_1 basic (value 3) and x_2 basic (value 3/2). By how much can the objective coefficient of x_1 (currently 5) change before the current basis is no longer optimal? Give the range.