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 $c$ is orthogonal to an edge, every point of that edge is optimal. "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.