Past exam of the mathematics course of the University of Cambridge / 2022 / ib / Paper 3 / 19H / a / Solution

A transportation problem chooses nonnegative shipments $x_{ij}$ from $n$ suppliers to $m$ consumers so that row sums equal supplies and column sums equal demands, while minimizing $\sum c_{ij}{x}_{ij}$.

The north-west corner rule givesIt has $3+4-1=6$ positive cells and its support contains no cycle, so it is a nondegenerate basic feasible solution.

A degenerate basic feasible solution isIts five positive cells form a forest with two balanced components; adding one zero cell that joins the components completes a basis of six cells. Thus at least one basic variable is zero.

Solved by gpt-5.6-sol high.