AQA D1 (Decision Mathematics 1) 2009 January

1 The following network shows the lengths, in miles, of roads connecting 11 villages, \(A , B , \ldots , K\).
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}

1. Starting from \(G\) and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.

2 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_401_517_429_751}
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_408_520_943_751}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task \(1 , C\) to task \(2 , D\) to task 4, and \(E\) to task 5 . Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.

3 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows roads connecting some places of interest in Berlin. The numbers represent the times taken, in minutes, to walk along the roads.
\includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-4_1427_1404_502_319} The total of all walking times is 167 minutes.

1. Mia is staying at \(D\) and is to visit \(H\).
   1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to walk from \(D\) to \(H\).
   2. Write down the corresponding route.
2. Each day, Leon has to deliver leaflets along all of the roads. He must start and finish at \(A\).
   1. Use your answer to part (a) to write down the shortest walking time from \(D\) to \(A\).
   2. Find the walking time of an optimum Chinese Postman route for Leon. (6 marks)

4 [Figure 2, printed on the insert, is provided for use in this question.]
Each year, farmer Giles buys some goats, pigs and sheep.
He must buy at least 110 animals.
He must buy at least as many pigs as goats.
The total of the number of pigs and the number of sheep that he buys must not be greater than 150 .
Each goat costs \(\pounds 16\), each pig costs \(\pounds 8\) and each sheep costs \(\pounds 24\).
He has \(\pounds 3120\) to spend on the animals.
At the end of the year, Giles sells all of the animals. He makes a profit of \(\pounds 70\) on each goat, \(\pounds 30\) on each pig and \(\pounds 50\) on each sheep. Giles wishes to maximize his total profit, \(\pounds P\). Each year, Giles buys \(x\) goats, \(y\) pigs and \(z\) sheep.

1. Formulate Giles's situation as a linear programming problem.
2. One year, Giles buys 30 sheep.
   1. Show that the constraints for Giles's situation for this year can be modelled by $$y \geqslant x , \quad 2 x + y \leqslant 300 , \quad x + y \geqslant 80 , \quad y \leqslant 120$$ (2 marks)
   2. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
      (8 marks)
   3. Find Giles's maximum profit for this year and the number of each animal that he must buy to obtain this maximum profit.
      (3 marks)

5 A student is using the algorithm below to find an approximate value of \(\sqrt { 2 }\).
Line 10 Let \(A = 1 , B = 3 , C = 0\)
Line \(20 \quad\) Let \(D = 1 , E = 2 , F = 0\)
Line 30 Let \(G = B / E\)
Line \(40 \quad\) Let \(H = G ^ { 2 }\)
Line 50 If \(( H - 2 ) ^ { 2 } < 0.0001\) then go to Line 130
Line 60 Let \(C = 2 B + A\)
Line 70 Let \(A = B\)
Line 80 Let \(B = C\)
Line 90 Let \(F = 2 E + D\)
Line 100 Let \(D = E\)
Line 110 Let \(E = F\)
Line 120 Go to Line 30
Line 130 Print ' \(\sqrt { 2 }\) is approximately', \(B / E\)
Line 140 Stop
Trace the algorithm.

6 A connected graph \(G\) has five vertices and has eight edges with lengths \(8,10,10,11,13,17\), 17 and 18.

1. Find the minimum length of a minimum spanning tree for \(G\).
2. Find the maximum length of a minimum spanning tree for \(G\).
3. Draw a sketch to show a possible graph \(G\) when the length of the minimum spanning tree is 53 .

7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points \(A , B , C , D\) and \(E\). The table shows the distances between pairs of points. All of the distances are functions of \(x\), where \(\boldsymbol { x }\) is an integer. Liam must travel to all five points, starting and finishing at \(A\).

1. The nearest point to \(A\) is \(C\).
   1. By considering \(A C\) and \(A B\), show that \(x < 10\).
   2. Find two other inequalities in \(x\).
2. The nearest neighbour algorithm, starting from \(A\), gives a unique minimum tour \(A C D E B A\).
   1. By considering the fact that Liam's tour visits \(D\) immediately after \(C\), find two further inequalities in \(x\).
   2. Find the value of the integer \(x\).
   3. Hence find the total distance travelled by Liam if he uses this tour.