Linear Programming Formulation

Of all the models in operations research, one is so well-behaved that we can solve versions with millions of variables to guaranteed optimality: the linear program. Its good manners come entirely from a single word — linear — and this page is about earning that word. Once you can recognise a linear program, cast it into a tidy standard form, and see its feasible region as a shape carved out of space, everything that follows — the geometry, the simplex method, duality — clicks into place.

We will carry one small factory with us for the rest of the course, so it is worth meeting it now: a workshop that makes tables and chairs.

What makes a program linear?

A program (an old word for "optimization problem") is linear when it has three properties together:

a linear objective — a weighted sum of the variables, c_1 x_1 + \dots + c_n x_n, with constant coefficients;
linear constraints — every restriction is a weighted sum of the variables compared to a constant, using \le, = or \ge;
continuous variables — each x_j may take any real value in its range (fractional amounts allowed; demanding whole numbers makes it an integer program, a much harder beast).

Linearity buys two priceless properties. Proportionality: doubling an activity doubles its contribution and its resource use — no economies of scale, no start-up costs. And additivity: activities do not interfere; total profit is just the sum of each activity's profit. These are modelling assumptions, and when they hold, the geometry becomes flat and the problem becomes tractable.

The tables-and-chairs workshop

The workshop makes tables (x_1) and chairs (x_2). A table earns £40 profit, a chair £30. Each piece passes through two shops. Carpentry takes 1 hour per table and 1 hour per chair, with 30 hours available this week. Finishing takes 2 hours per table and 1 per chair, with 40 hours available. Following the formulation recipe — variables, objective, constraints — the model is:

\max\; 40x_1 + 30x_2 \quad\text{s.t.}\quad \underbrace{x_1 + x_2 \le 30}_{\text{carpentry}},\;\; \underbrace{2x_1 + x_2 \le 40}_{\text{finishing}},\;\; x_1, x_2 \ge 0.

Everything is linear: profit is proportional to output, hours add up, and half a table is (mathematically) allowed. This is a textbook product-mix linear program — and its optimum, which we will find geometrically on the next page, turns out to be 10 tables and 20 chairs for £1000 profit.

Standard form: one shape to rule them all

Real problems arrive in every shape — some constraints \le, some \ge, some maximising, some minimising. To build one algorithm that solves them all, we first launder every LP into a single standard form:

\max\; \mathbf{c}^{\!\top}\mathbf{x} \quad\text{subject to}\quad A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \ge \mathbf{0}, \quad \mathbf{b} \ge \mathbf{0}.

Note the equalities. Any inequality can be turned into an equality by introducing a new non-negative variable that "soaks up" the gap. A slack variable absorbs the unused amount of a \le resource; a surplus variable carries the excess over a \ge requirement:

Original	Add	Becomes	Meaning of the new variable
x_1 + x_2 \le 30	slack s_1 \ge 0	x_1 + x_2 + s_1 = 30	unused carpentry hours
2x_1 + x_2 \le 40	slack s_2 \ge 0	2x_1 + x_2 + s_2 = 40	unused finishing hours
x_1 \ge 5	surplus e \ge 0	x_1 - e = 5	amount above the floor

So the workshop in standard form is x_1 + x_2 + s_1 = 30, 2x_1 + x_2 + s_2 = 40, with x_1, x_2, s_1, s_2 \ge 0. The slacks are not bookkeeping fictions — a positive s_1 literally tells you how many carpentry hours went idle, a fact we will read real money off of when we reach shadow prices.

(A minimisation becomes a maximisation by negating the objective; a free variable is written as the difference of two non-negative variables. With these moves, every LP fits the mould.)

The feasible region is an intersection of half-spaces

Geometry now enters. Each inequality constraint slices space into two: the points that satisfy it and the points that do not. The satisfying side is a half-space (in two dimensions, a half-plane). The feasible region — the set of all points obeying every constraint at once — is the intersection of all these half-spaces, a flat-sided shape called a convex polyhedron (bounded, a polytope). For the workshop, four inequalities (two resources plus the two non-negativity limits) carve out this quadrilateral:

Every candidate production plan the workshop could actually run is a point in that shaded region; everything outside breaks a rule. The whole task of linear programming is to find the single point in this region that pushes the profit as high as it will go — and, remarkably, we will see that we only ever need to look at the corners.

The name is a historical accident that predates computers as we know them. In the 1940s a "programme" meant a plan or schedule — a programme of activities, in the military-logistics sense George Dantzig worked in. "Linear programming" therefore meant "planning with linear relationships," not "writing linear code." By the time software took over the word, the name had stuck. So an LP is a plan we optimise, and the coincidence that we now solve it by programming a computer is just that — a coincidence.

Linearity is fragile. A single product of variables (x_1 x_2, say a term where making more tables changes the profit-per-chair), a ratio (x_1 / (x_1 + x_2), a percentage or blend fraction), a power (x_1^2 for a quadratic cost), or an if-then rule quietly drags the model out of linear programming and into nonlinear or integer territory — where the flat-sided geometry and the corner theorem no longer apply and solving gets dramatically harder. Before reaching for the simplex method, audit every term: is each variable to the first power, multiplied only by a constant? If not, you do not have a linear program, however much it looks like one.