= 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 is
$$
\bar c_{ij}=c_{ij}-u_i-v_j.
$$
If 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 set
$$
\theta=\min\{x_{ij}: (i,j)\text{ is a }-\text{ cell}\}.
$$
Add $\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.
Back to article page
