Past exam of the mathematics course of the University of Cambridge / 2025 / ib / Paper 4 / 18H (Optimisation)

Introduce unrestricted row and column potentials $u_i,v_j$. The dual isPrimal and dual feasible solutions are optimal precisely when complementary slackness holds:Indeed, the primal--dual objective gap is ${\sum }_{ij}{x}_{ij}(c_{ij}-u_i-v_j)$, a sum of nonnegative terms.

One of the $m+n$ balance equations is redundant, and the remaining $m+n-1$ have full rank. A nondegenerate basic feasible solution therefore has exactly $m+n-1$ positive variables. Equivalently, its positive cells form a spanning tree of the complete bipartite row--column graph.

The northwest-corner rule constructs an initial basic feasible solution: fill the current cell with the smaller remaining supply and demand, delete the exhausted row or column, and continue.

For a current spanning-tree basis, solve $u_i+v_j=c_{ij}$ on its occupied cells, fixing one potential to zero. The reduced cost of an unoccupied cell isIf all reduced costs are nonnegative, part (a) proves optimality. Otherwise choose a cell with negative reduced cost. Adding its edge to the tree creates a unique even cycle. Mark its cells alternately $+$ and $-$, starting with $+$ at the entering cell, and setAdd $\theta$ on the plus cells and subtract it on the minus cells. Row and column totals are unchanged, the entering cell becomes positive, and a minimizing minus cell leaves the basis. In the nondegenerate case the objective decreases strictly. There are finitely many bases, so no basis repeats and the algorithm terminates at a basis with no negative reduced cost, which is optimal.

With integer supplies and demands, every northwest-corner allocation is integer. At each pivot, $\theta$ is the minimum of finitely many current allocations on the minus cells, so it remains integer; adding and subtracting it preserves integrality. The algorithm therefore reaches an integer-valued optimal solution.