find the route the driver should follow, starting and ending at \(F\), to clear all the roads of snow. Give the length of this route.
The local authority decides to build a road bridge over the river at \(B\). The snowplough will be able to cross the road bridge.
Reapply the algorithm to find the minimum distance the snowplough will have to travel (ignore the length of the new bridge).
\section*{6.}
\section*{Figure 3}
Peter wishes to minimise the time spent driving from his home \(H\), to a campsite at \(G\). Figure 3 shows a number of towns and the time, in minutes, taken to drive between them. The volume of traffic on the roads into \(G\) is variable, and so the length of time taken to drive along these roads is expressed in terms of \(x\), where \(x \geq 0\).
On the diagram in the answer book, use Dijkstra's algorithm to find two routes from \(H\) to \(G\) (one via \(A\) and one via \(B\) ) that minimise the travelling time from \(H\) to \(G\). State the length of each route in terms of \(x\).
Find the range of values of \(x\) for which Peter should follow the route via \(A\).
\section*{7.}
\begin{figure}[h]
\end{figure}
The company EXYCEL makes two types of battery, X and Y . Machinery, workforce and predicted sales determine the number of batteries EXYCEL make. The company decides to use a graphical method to find its optimal daily production of X and Y .
The constraints are modelled in Figure 4 where
$$\begin{aligned}
& x = \text { the number (in thousands) of type } \mathrm { X } \text { batteries produced each day, }
& y = \text { the number (in thousands) of type } \mathrm { Y } \text { batteries produced each day. }
\end{aligned}$$
The profit on each type X battery is 40 p and on each type Y battery is 20 p . The company wishes to maximise its daily profit.
Write this as a linear programming problem, in terms of \(x\) and \(y\), stating the objective function and all the constraints.
Find the optimal number of batteries to be made each day. Show your method clearly.
Find the daily profit, in \(\pounds\), made by EXYCEL.