Paper 4, Section II, H

Optimization
Part IB, 2011

A company must ship coal from four mines, labelled A,B,C,DA, B, C, D, to supply three factories, labelled a,b,ca, b, c. The per unit transport cost, the outputs of the mines, and the requirements of the factories are given below.

\begin{tabular}{c|c|c|c|c|c} & AA & BB & CC & DD & \ \hlineaa & 12 & 3 & 5 & 2 & 34 \ \hlinebb & 4 & 11 & 2 & 6 & 21 \ \hlinecc & 3 & 9 & 7 & 4 & 23 \ \hline & 20 & 32 & 15 & 11 & \end{tabular}

For instance, mine BB can produce 32 units of coal, factory a requires 34 units of coal, and it costs 3 units of money to ship one unit of coal from BB to aa. What is the minimal cost of transporting coal from the mines to the factories?

Now suppose increased efficiency allows factory bb to reduce its requirement to 20.820.8 units of coal, and as a consequence, mine BB reduces its output to 31.831.8 units. By how much does the transport cost decrease?