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

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.