Suppose the recycling manager in a particular region is responsible for allocating all the recyclable waste that is collected in $n$ towns in the region to the $m$ recycling centres in the region. Town $i$ produces $s_{i}$ lorry loads of recyclable waste each day, and recycling centre $j$ needs to handle $d_{j}$ lorry loads of waste a day in order to be viable. Suppose that $\sum_{i} s_{i}=\sum_{j} d_{j}$. Suppose further that $c_{i j}$ is the cost of transporting a lorry load of waste from town $i$ to recycling centre $j$. The manager wishes to decide the number $x_{i j}$ of lorry loads of recyclable waste that should go from town $i$ to recycling centre $j$, $i=1, \ldots, n, j=1, \ldots, m$, in such a way that all the recyclable waste produced by each town is transported to recycling centres each day, and each recycling centre works exactly at the viable level each day. Use the Lagrangian sufficiency theorem, which you should quote carefully, to derive necessary and sufficient conditions for $\left(x_{i j}\right)$ to minimise the total cost under the above constraints.

Suppose that there are three recycling centres $A, B$ and $C$, needing 5,20 and 20 lorry loads of waste each day, respectively, and suppose there are three towns $a, b$ and $c$ producing 20,15 and 10 lorry loads of waste each day, respectively. The costs of transporting a lorry load of waste from town $a$ to recycling centres $A, B$ and $C$ are $£ 90, £ 100$ and $£ 100$, respectively. The corresponding costs for town $b$ are $£ 130, £ 140$ and $£ 100$, while for town $c$ they are $£ 110, £ 80$ and $£ 80$. Recycling centre $A$ has reported that it currently receives 5 lorry loads of waste per day from town $a$, and recycling centre $C$ has reported that it currently receives 10 lorry loads of waste per day from each of towns $b$ and c. Recycling centre $B$ has failed to report. What is the cost of the current arrangement for transporting waste from the towns to the recycling centres? Starting with the current arrangement as an initial solution, use the transportation algorithm (explaining each step carefully) in order to advise the recycling manager how many lorry loads of waste should go from each town to each of the recycling centres in order to minimise the cost. What is the minimum cost?