AQA D1 (Decision Mathematics 1) 2014 June

1 Five people, \(A , B , C , D\) and \(E\), are to be allocated to five tasks, 1, 2, 3, 4 and 5 . The following bipartite graph shows the tasks that each person is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-02_441_437_699_797}

1. Represent this information in an adjacency matrix.
2. Initially, \(A\) is allocated to task 3, \(B\) to task 2 and \(C\) to task 4.
   1. Demonstrate, by using an alternating-path algorithm from this initial matching, how each person can be allocated to a different task.
   2. Find a different allocation of people to tasks.

2 A document which is currently written in English is to be translated into six other European Union languages. The cost of translating a document varies, as it is harder to find translators for some languages. The costs, in euros, are shown in the table below.

1. 1. On the table below, showing the order in which you select the edges, use Prim's algorithm, starting from \(E\), to find a minimum spanning tree for the graph connecting \(D , E , F , G , H , I\) and \(S\).
   2. Find the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. It is given that the graph has a unique minimum spanning tree. State the final two edges that would be added to complete the minimum spanning tree in the case where:
   1. Prim's algorithm starting from \(H\) is used;
   2. Kruskal's algorithm is used. \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Answer space for question 2}

      	Danish ( \(\boldsymbol { D }\) )	English ( \(\boldsymbol { E }\) )	French (F)	German ( \(G\) )	Hungarian (H)	Italian (I)	Spanish \(\boldsymbol { ( } \boldsymbol { S } \boldsymbol { ) }\)
      Danish (D)	-	120	140	80	170	140	140
      English ( \(\boldsymbol { E }\) )	120	-	70	80	130	130	110
      French (F)	140	70	-	90	190	85	90
      German ( \(G\) )	80	80	90	-	110	100	100
      Hungarian (H)	170	130	190	110	-	140	150
      Italian (I)	140	130	85	100	140	-	60
      Spanish ( \(\boldsymbol { S }\) )	140	110	90	100	150	60	-

      \end{table}

3 The network below shows 11 towns, \(A , B , \ldots , K\). The number on each edge shows the time, in minutes, to travel between a pair of towns.

1. 1. Use Dijkstra's algorithm on the diagram below to find the minimum time to travel from \(A\) to \(K\).
   2. State the corresponding route.
2. On a particular day, Jenny travels from \(A\) to \(K\) but visits her friend at \(D\) on her way. Find Jenny's minimum travelling time.
3. On a different day, all roads connected to \(I\) are closed due to flooding. Jenny does not visit her friend at \(D\). Find her minimum time to travel from \(A\) to \(K\). State the route corresponding to this minimum time.
   [0pt] [2 marks] \section*{Answer space for question 3}
   \includegraphics[max width=\textwidth, alt={}]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-06_1478_1548_1213_239}

4 Paulo sells vegetables from his van. He drives around the streets of a small village. The network shows the streets in the village. The number on each edge shows the time, in minutes, to drive along that street. Paulo starts from his house located at vertex \(A\) and drives along all the streets at least once before returning to his house.
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-10_1518_1605_598_198} The total of all the times in the diagram is 79.5 minutes.

1. Find the length of an optimal Chinese postman route around the village, starting and finishing at \(A\). (Shortest routes between vertices may be found by inspection.)
2. For an optimal Chinese postman route, state:
   1. the number of times the vertex \(F\) would occur;
   2. the number of times the vertex \(D\) would occur.
3. Toto is standing for the position of Mayor in the local elections. He intends to travel along all the roads at least once. He can start his journey at any vertex and can finish his journey at any vertex.
   1. Find the length of an optimal route for Toto.
      [0pt]
   2. State the vertices from which Toto could start in order to achieve this optimal route. [3 marks]

5 The feasible region of a linear programming problem is determined by the following: $$\begin{aligned} x & \geqslant 1
y & \geqslant 3
x + y & \geqslant 5
x + y & \leqslant 12
3 x + 8 y & \leqslant 64 \end{aligned}$$

1. On the grid below, draw a suitable diagram to represent the inequalities and indicate the feasible region.
2. Use your diagram to find, on the feasible region:
   1. the maximum value of \(3 x + y\);
   2. the maximum value of \(2 x + 3 y\);
   3. the minimum value of \(- 2 x + y\). In each case, state the coordinates of the point corresponding to your answer.
      [0pt] [6 marks]

6

1. Sarah is solving a travelling-salesman problem.
   1. She finds the following upper bounds: \(32,33,32,32,30,32,32\). Write down the best upper bound.
   2. She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20. Write down the best lower bound.
2. Rob is travelling by train to a number of cities. He is to start at \(M\) and visit each other city at least once before returning to \(M\). The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available.
   \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443} The table below shows the minimum travelling times between all pairs of cities.

   \cline { 2 - 6 } \multicolumn{1}{c|}{}	\(\boldsymbol { B }\)	\(\boldsymbol { E }\)	\(\boldsymbol { L }\)	\(\boldsymbol { M }\)	\(\boldsymbol { N }\)
   \(\boldsymbol { B }\)	-	230	82	102	192
   \(\boldsymbol { E }\)	230	-	148	244	258
   \(\boldsymbol { L }\)	82	148	-	126	110
   \(\boldsymbol { M }\)	102	244	126	-	236
   \(\boldsymbol { N }\)	192	258	110	236	-

   1. Explain why the minimum travelling time from \(M\) to \(N\) is not 283 .
   2. Find an upper bound for the minimum travelling time by using the tour \(M N B E L M\).
   3. Write down the actual route corresponding to the tour \(M N B E L M\).
   4. Use the nearest-neighbour algorithm, starting from \(M\), to find another upper bound for the minimum travelling time of Rob's tour.
      [0pt] [4 marks] QUESTION
3. 1. The best upper bound is \(\_\_\_\_\)
   2. The best lower bound is \(\_\_\_\_\)

7 A factory makes batches of three different types of battery: basic, long-life and super.
Each basic batch needs 4 minutes on machine \(A\), 7 minutes on machine \(B\) and 14 minutes on machine \(C\). Each long-life batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 21 minutes on machine \(C\). Each super batch needs 10 minutes on machine \(A\), 14 minutes on machine \(B\) and 28 minutes on machine \(C\). Machine \(A\) is available for 4 hours a day, machine \(B\) for 3.5 hours a day and machine \(C\) for 7 hours a day. Each day the factory must make:
more basic batches than the total number of long-life and super batches; at least as many long-life batches as super batches. At least 15\% of the production must be long-life batches.
Each day, the factory makes \(x\) basic, \(y\) long-life and \(z\) super batches.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), writing your answers with simplified integer coefficients.

8 In this question you may use the fact that any simple graph must have an even number of vertices of odd degree.

1. A simple graph has five vertices and their degrees are $$x , x + 1 , x + 1 , x + 2 \text { and } x + 3$$
   1. Show that \(x\) must be odd.
   2. Find the value of \(x\) and draw a graph with vertices having the given degrees.
2. A simple graph has 10 vertices.
   1. State the minimum possible degree and maximum possible degree of a vertex.
   2. Show that the degrees of the vertices cannot all be different.
      □
      □