55 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.

55.1 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.

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.

55.2 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.

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.

55.3 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 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.

55.4 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.

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.

55.5 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.

55.6 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.

55.7 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 4) and $s_2$ basic (value 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.

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