Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 35 / 3 / c / Solution

Use the transportation simplex algorithm, with transportation dual potentials $u_i,v_j$ and reduced costs $r_{ij}=c_{ij}-u_i-v_j$. On a basic cell choose $u_i+v_j=c_{ij}$. The initial shipment matrix, read from the circled entries in the PDF, isIts six positive cells form a transportation spanning tree. Setting $u_1=0$ givesEnter cell $(1,1)$, whose reduced cost is $-6$. The cycle pivot has signsThe maximum feasible increment is $\theta =\min (5,4)=4$, so cell $(4,1)$ leaves the basis. The result isFor the new transportation spanning tree,Enter cell $(2,3)$ with reduced cost $-4$. Its cycle pivot isNow $\theta =\min (5,1)=1$, and cell $(1,3)$ leaves. We obtainIts row sums are $(12,5,7,12)$ and its column sums $(9,14,13)$, as required. The final transportation dual potentials areAll reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix $X$,Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.