Past exam of the mathematics course of the University of Cambridge / 2025 / ib / Paper 4 / 18H / c / Solution

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.

Solved by gpt-5.6-sol high.