Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 1 / 8H / Solution

A transportation problem minimizes ${\sum }_{ij}{c}_{ij}{x}_{ij}$ subject to nonnegative shipments, prescribed row supplies, and prescribed column demands.

One optimal shipment table iswhich has the required row sums $(10,8,8)$ and column sums $(3,9,14)$ and costs $4(3)+6(1)+8(3)+3(3)+5(5)=\boxed{76}$.

For an optimality certificate, take row potentials $(1,3,3)$ and column potentials $(0,2,0)$. Their sums equal costs in occupied cells and do not exceed any cost:The dual value is $10+24+24+18=76$, so linear programming duality proves optimality.