= 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 is
$$
\boxed{
\begin{pmatrix}
0&4&6\\
0&0&8\\
3&5&0
\end{pmatrix},}
$$
which 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:
$$
\begin{pmatrix}1&3&1\\3&5&3\\3&5&3\end{pmatrix}
\leq
\begin{pmatrix}4&3&1\\6&10&3\\3&5&7\end{pmatrix}.
$$
The dual value is $10+24+24+18=76$, so <linear programming duality> proves optimality.
Back to article page
