Linear programming, simplex and duality

In one sentence

A linear programme optimises a linear objective over a polyhedron, so if an optimum exists it is attained at a vertex — and the dual programme tells you whether one exists at all.

Why the exam asks it

Because Part C can set four independent statements about a single programme — is it feasible, is it bounded, is the optimum attained, what does the dual say — and score them all-or-nothing. The arithmetic is deliberately light. The marks turn on reading the constraints exactly, and on not confusing "the region is unbounded" with "the objective is unbounded".

The idea

Write the programme in standard form: maximise $c^{T}x$ subject to $Ax \le b$ and $x \ge 0$. The feasible set is an intersection of half-spaces — a convex polyhedron.

Exactly three things can happen, and every exam question is really asking which:

1. Infeasible. The constraints contradict each other and the feasible set is empty.
2. Unbounded. Feasible, but the objective grows without limit along some direction in the set.
3. Optimal. A finite maximum, attained.

Why vertices are enough

A linear objective has no interior stationary point — its gradient $c$ is constant and never zero unless $c = 0$. So it improves steadily in one direction until the region stops it, and the region stops it at a face. Hence the fundamental theorem: if a standard-form programme has an optimal solution, one optimal solution is an extreme point of the feasible set.

That is what makes the problem finite. There are finitely many vertices, so checking them all is an algorithm — a bad one, but an algorithm. The simplex method is the same walk done well: start at a vertex, move along an edge that improves the objective, stop when no edge improves it.

The dual, and what it is for

Every maximisation has a partner minimisation:

$\text{primal: } \max\ c^{T}x,\ Ax \le b,\ x \ge 0 \qquad \text{dual: } \min\ b^{T}y,\ A^{T}y \ge c,\ y \ge 0 .$

Weak duality. For any feasible $x$ and any feasible $y$,

$c^{T}x \;\le\; y^{T}Ax \;\le\; b^{T}y .$

Both inequalities are immediate: $A^{T}y \ge c$ with $x \ge 0$ gives the first, $Ax \le b$ with $y \ge 0$ gives the second. Every dual feasible point is a certificate bounding the primal.

Strong duality. If either programme has a finite optimum, so does the other, and the two optimal values are equal. This is the theorem doing the work in most exam statements.

Complementary slackness. At an optimal pair, a constraint with slack forces its dual variable to zero, and a variable that is positive forces its dual constraint to be tight.

Where intuition breaks

An unbounded region does not mean an unbounded objective. This is the single most common error. Maximise $x_1$ subject to $x_1 \le 1$, $x_2 \ge 0$: the feasible set runs to infinity in the $x_2$ direction, and the maximum is $1$. Unboundedness of the objective needs a direction that is both feasible and improving.

A constraint can be an equality in disguise. If $x_2 \ge 0$, $x_3 \ge 0$ and $x_2 + x_3 \le 0$, then $x_2 = x_3 = 0$ — a non-negative sum bounded above by zero has only one solution. Two variables vanish and the programme collapses to one. Papers set this deliberately, and a candidate who starts drawing a region has already lost the question.

Unbounded primal $\Rightarrow$ infeasible dual, but not the converse. Weak duality gives the forward direction: if the primal runs to $+\infty$ no $b^{T}y$ could bound it, so no dual feasible $y$ exists. The converse fails — both programmes can be infeasible at once, and a statement asserting "the dual is infeasible, therefore the primal is unbounded" is false.

The optimum need not be unique. If the objective is constant along an edge that meets an optimal vertex — that is, $c$ is orthogonal to that edge — then every point of the edge is optimal, and so is the whole face it spans. Orthogonality on its own is not enough, and the difference is worth a mark. Maximise $x_1$ over the unit square: $c = (1,0)$ is orthogonal to the edge from $(0,0)$ to $(0,1)$, yet every point of that edge scores $0$ — the minimum. "The optimal solution is unique" is a separate claim from "an optimal solution exists", and Part C will ask for both.

The exam's angle

Work in this order, because it is the order that makes questions collapse:

1. Read every constraint for a forced value before anything else. Non-negative variables with a $\le 0$ bound, or two constraints that pin a variable between equal bounds.
2. Decide feasibility. A single contradiction ends the question.
3. Decide boundedness by looking for an improving feasible direction, not by looking at the picture of the region.
4. Then find the optimum, at a vertex.

For "what is the optimal value" with small integers, evaluating the objective at each vertex is usually faster than a simplex tableau, and much harder to slip on.

The night before

• Three outcomes only: infeasible, unbounded, optimal.
• Optimum, if it exists, sits at a vertex.
• Weak duality always; strong duality when either side is finite.
• Unbounded region $\ne$ unbounded objective.
• Non-negative variables summing to $\le 0$ are all zero.
• Primal unbounded $\Rightarrow$ dual infeasible; the converse is false.

In plain English

Maximise a linear quantity subject to linear constraints. The feasible region is a shape with flat faces.

Because a linear objective has no peak in the middle, the best value has to sit at a corner. So an infinite problem becomes a finite one: check the corners. The simplex method is that walk done sensibly, moving along edges that improve things.

The dual is a second problem whose value bounds the first, and at the optimum the two values are equal.

Where this shows up

This is one of the most commercially valuable pieces of mathematics there is.

Airline crew scheduling, refinery blending, freight routing, portfolio construction and power grid dispatch are all linear programmes, often with millions of variables.

Duality has a direct reading. The dual variables are shadow prices, saying what one more unit of a scarce resource would be worth. That is usually the number a manager actually wants.

Recent research

The simplex method can take exponentially many steps in the worst case, though it almost never does in practice. Interior-point methods cut through the middle of the region rather than walking its corners, carry polynomial guarantees, and now handle the largest problems. They are still being sharpened: a 2024 two-step variant cut iterations by around a quarter on standard benchmarks, in Algorithms 17(7), 303.