Linear Programming

Linear programming maximises or minimises a quantity subject to limits on resources. Every problem has the same shape: constraints define a region, and the best point is always at one of its corners.

Formulating a problem

Three steps, in order.

1. Define the variables explicitly, with units.

Let $x$ be the number of tables and $y$ the number of chairs produced per week.

2. Write the objective function — the quantity to be optimised.

Maximise $P = 4x + 3y$ (profit in dollars).

3. Write the constraints as inequalities, including non-negativity.

Graphing the constraints

Each linear inequality is a half-plane.

1. Draw the boundary line by replacing the inequality with an equals sign. The intercepts are quickest: for $x + y = 10$, plot $(10, 0)$ and $(0, 10)$.
2. Decide which side to keep by testing a point — usually the origin. For $x + y \le 10$, the origin gives $0 \le 10$ ✓, so keep the side containing the origin.
3. Shade consistently: either shade the region you want or shade out the region you do not, but say which.

Use a solid line for $\le$ or $\ge$ (the boundary is included) and a dashed line for $<$ or $>$ (it is not).

The feasible region

The feasible region is the set of points satisfying every constraint at once — the overlap of all the half-planes. Label it clearly on the diagram.

Two situations to recognise:

• Empty region — the constraints contradict each other and no solution exists.
• Unbounded region — it extends to infinity. A minimum may still exist, but a maximum may not.

The objective function

$$P = 4x + 3y$$

Lines of constant $P$ are parallel — $P = 12$, $P = 24$, $P = 36$ all have gradient $-\frac43$. Optimising means sliding that line as far as possible in the improving direction while still touching the feasible region.

The last point it touches is the optimum, and because the region is a polygon, that point is always a vertex (or, if the objective line is parallel to an edge, the whole of that edge).

The vertex method

Since the optimum is at a corner, evaluate the objective at every vertex and compare.

Maximise $P = 4x + 3y$ subject to $x + y \le 10$, $2x + y \le 16$, $x, y \ge 0$.

Find the vertices:

• $(0,0)$ — the origin.
• $(0,10)$ — where $x + y = 10$ meets the $y$-axis. Check: $2(0) + 10 = 10 \le 16$ ✓
• $(8,0)$ — where $2x + y = 16$ meets the $x$-axis. Check: $8 + 0 \le 10$ ✓
• The intersection of the two lines: subtracting $x + y = 10$ from $2x + y = 16$ gives $x = 6$, so $y = 4$.

Evaluate:

Maximum profit $36$ at $x = 6$, $y = 4$.

A minimisation. Minimise $C = 3x + 2y$ subject to $x + y \ge 8$, $3x + y \ge 12$, $x, y \ge 0$. The vertices are $(0,12)$, $(2,6)$ and $(8,0)$:

Minimum cost $18$ at $x = 2$, $y = 6$.

Integer solutions

Many problems count indivisible things: chairs, buses, staff. The graphical optimum may then be fractional.

Rounding is not reliable. The rounded point may lie outside the feasible region, and even when it is inside it may not be the best integer point.

The safe procedure:

1. Find the optimal vertex.
2. List the integer points nearby that lie inside the feasible region.
3. Evaluate the objective at each and take the best.