Past exam of the mathematics course of the University of Cambridge / 2022 / ib / Paper 3 / 19H (Optimisation)

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.

The stated plan isIts six positive cells form a spanning tree of the supplier--consumer bipartite graph, so it is basic and feasible. Taking $u_1=0$, the basic-cell equations $u_i+v_j=c_{ij}$ giveThe complete matrix of reduced costs ${\bar{c}}_{ij}=c_{ij}-u_i-v_j$ isThe negative entry ${\bar{c}}_{12}=-2$ proves that the plan is not optimal.

Enter cell $(1,2)$. The alternating cycle isand the step is $\theta =\min (3,1)=1$. The new plan iswhose cost is $26$, down from $28$. New potentials areand the reduced-cost matrix isEvery reduced cost is nonnegative, so the transportation optimality criterion shows thatThe zero reduced cost in cell $(2,3)$ also indicates an alternative optimum.