5 A network of roads connects the villages \(A , B , C , D , E , F\) and \(G\)
The weight on each arc in the network represents the distance, in miles, between adjacent villages.
The network is shown in the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{2e397d7b-b751-4f2c-aa0e-31dd4a071b56-05_769_983_543_511}
5
- Draw, in the space below, the spanning tree of minimum total length for this road network.
5
- Find the total length of the spanning tree drawn in part (a).
A Young Enterprise Company decides to sell two types of cakes at a breakfast club.
The two types of cakes are blueberry and chocolate.
From its initial market research, the company knows that it will:
- sell at most 200 cakes in total
- sell at least twice as many blueberry cakes as they will chocolate cakes
- make 20 p profit on each blueberry cake they sell
- make 15p profit on each chocolate cake they sell.
The company's objective is to maximise its profit.
Formulate the Young Enterprise Company's situation as a linear programming problem.