\(\mathbf { 4 }\) & 23 & 27 & 12 & 24
\hline
\end{tabular}
\end{center}
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 3 | 2 | 3 | 3 |
| \(\mathbf { 2 }\) | 1 | 1 | 3 | 3 |
| \(\mathbf { 3 }\) | 1 | 2 | 1 | 4 |
| \(\mathbf { 4 }\) | 3 | 3 | 3 | 3 |
Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal.
4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced.
Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours.
There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.
(i) Formulate a linear programming problem to maximise production within the given constraints.
(ii) Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
(iii) An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.