OCR MEI D1 (Decision Mathematics 1) 2005 June

1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h] \end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.

1. Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
2. What is the minimum number of connections which the electrician will have to make if he uses the junction box?
3. The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
4. Will this result in the minimum number of connections? Justify your answer.

2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h] \end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."

1. On the insert for this question show Janet's route through the maze. On the insert show John's route.
2. Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where \(\mathbf { X }\) is the marked point. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to \(\mathbf { X }\). John's algorithm does not take him to \(\mathbf { X }\). John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting \(\mathbf { X }\). He will then move onwards, continuing to keep a hand in contact with the wall on the left.
3. Will this modified algorithm take John to the point \(\mathbf { X }\) in the maze in Fig. 2.2?
4. Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.

3 Table 3 gives the durations and immediate predecessors for the five activities of a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early and late event times for the vertices of your network, and list the critical activities.
3. Give the total and independent float for each activity which is not critical.

4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h] \end{figure}

1. Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
2. Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
3. What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
4. What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
5. Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.

5 A computer store has a stock of 10 laptops to lend to customers while their machines are being repaired. On any particular day the number of laptop loans requested follows the distribution given in Table 5.1. \begin{table}[h] \end{table}

1. Give an efficient rule for using two-digit random numbers to simulate the daily number of requests for laptop loans.
2. Use two-digit random numbers from the list below to simulate the number of loans requested on each of ten successive days. Random numbers: \(23,02,57,80,31,72,92,78,04,07\) The number of laptops returned from loan each day is modelled by the distribution given in Table 5.2, independently of the number on loan (which is always at least 5 ). \begin{table}[h]

   Number returned	0	1	2	3
   Probability	\(\frac { 1 } { 6 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 4 }\)	\(\frac { 1 } { 3 }\)

   \captionsetup{labelformat=empty} \caption{Table 5.2}
   \end{table}
3. Give an efficient rule for using two-digit random numbers to simulate the daily number of laptop returns.
4. Use two-digit random numbers from the list below to simulate the number of returns on each of ten successive days. Random numbers: \(32,98,01,32,14,21,32,71,82,54,47\) At the end of day 0 there are 7 laptops out on loan and 3 in stock. Each day returns are made in the morning and loans go out in the afternoon. If there is no laptop available the customer is disappointed and never gets a loaned laptop.
5. Use your simulated numbers of requests and returns to simulate what happens over the next 10 days. For each day record the day number, the number of laptops in stock at the end of the day, and the number of customers that have to be disappointed.
   [0pt] [3] To try to avoid disappointing customers, if the number of laptops in stock at the end of a day is 2 or fewer, the store sends out e-mails to customers with loaned laptops asking for early return if possible. This changes the return distribution for the next day to that given in Table 5.3. \begin{table}[h]

   Number returned	0	1	2	3	4
   Probability	0.1	0.1	0.4	0.2	0.2

   \captionsetup{labelformat=empty} \caption{Table 5.3}
   \end{table}
6. Simulate the 10 days again, but using this new policy. Use the requests you produced in part (ii). Use the random numbers given in part (iv) to simulate returns, but use either the distribution given in Table 5.2 or that given in Table 5.3, depending on the number of laptops in stock at the end of the previous day. Is the new policy better?

6 A company manufactures two types of potting compost, Flowerbase and Growmuch. The weekly amounts produced of each are constrained by the supplies of fibre and of nutrient mix. Each litre of Flowerbase requires 0.75 litres of fibre and 1 kg of nutrient mix. Each litre of Growmuch requires 0.5 litres of fibre and 2 kg of nutrient mix. There are 12000 litres of fibre supplied each week, and 25000 kg of nutrient mix. The profit on Flowerbase is 9 p per litre. The profit on Growmuch is 20 p per litre.

1. Formulate an LP to maximise the weekly profit subject to the constraints on fibre and nutrient mix.
2. Solve your LP using a graphical approach.
3. Consider each of the following separate circumstances.
   (A) There is a reduction in the weekly supply of fibre from 12000 litres to 10000 litres. What effect does this have on profit?
   (B) The price of fibre is increased. Will this affect the optimal production plan? Justify your answer.
   [0pt] (C) The supply of nutrient mix is increased to 30000 kg per week. What is the new profit? [1]