= Solution
Let $x_{ij}\ge0$ be shipped amounts, with column sums equal to shop demand and row sums at most 15. Total demand is 42, so three units of warehouse stock need not be shipped. A feasible <transportation problem> allocation is
$$
\boxed{X=\begin{pmatrix}9&6&0&0&0\\0&0&12&3&0\\0&0&0&2&10\end{pmatrix}.}
$$
Its row sums are $(15,15,12)$ and its column sums meet every demand. The cost is $18+18+12+3+4+10=65$.
For a <transportation dual certificate with capacity inequalities>, choose warehouse potentials $u=(0,-1,0)$ and shop potentials $v=(2,3,2,2,1)$. They have $u_i\le0$ and $u_i+v_j\le c_{ij}$ for every cell. Any feasible allocation therefore has
$$
\sum_{ij}c_{ij}x_{ij}\ge\sum_i u_i\sum_jx_{ij}+\sum_jv_jd_j
\ge15\sum_i u_i+\sum_jv_jd_j
=-15+80=65.
$$
The second inequality has this direction because $u_i\le0$ and warehouse use is at most 15. \b[The exhibited allocation attains the lower bound, so the minimum cost is $\boxed{65}$.]
Back to article page
