Edexcel D1 (Decision Mathematics 1) 2017 June

1. (a) Define the terms
   1. bipartite graph,
   2. alternating path.
      (4)
   \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_624_526_653_347} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_611_519_662_1192} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} At a hotel, six guests, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be allocated to six rooms, \(1,2,3,4,5\) and 6 . Each room needs to be allocated to exactly one guest. A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
   (b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5 . Hence find an improved matching. You must list the alternating path that you use and state your improved matching.
   (3) Guest C now has room 5 added to his possible allocations.
   (c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.

2. \begin{figure}[h] \end{figure} Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

1. Use Prim's algorithm, starting at B , to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.
   (3)
2. State the minimum cost of connecting the nine computer terminals.
   (1) It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.
3. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.
   (3)
   (Total 7 marks)

3. \(\quad \begin{array} { l l l l l l l l l l } 42 & 21 & 15 & 16 & 35 & 10 & 31 & 11 & 27 & 39 \end{array}\)

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 65 The nine distinct numbers below are to be sorted into descending order $$\begin{array} { l l l l l l l l l } 23 & 14 & 17 & \boldsymbol { x } & 21 & 18 & 8 & 20 & 11 \end{array}$$ A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & \boldsymbol { x } & 21 & 18 & 14 & 20 & 11 & 8 \end{array}$$ After the second complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & 21 & 18 & \boldsymbol { x } & 20 & 14 & 11 & 8 \end{array}$$
4. Using this information, write down the smallest interval that must contain \(\boldsymbol { x }\). Give your answer as an inequality.

4. \begin{figure}[h] \end{figure} Figure 4 represents a network of roads. The number on each edge represents the length, in miles, of the corresponding road. Robyn wishes to travel from A to H. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to H. State the shortest path and its length. On a particular day, Robyn needs to check each road. She must travel along each road at least once. Robyn must start and finish at vertex A.
2. Use the route inspection algorithm to find the length of the shortest inspection route. State the edges that should be repeated. You should make your method and working clear.
   (5) The roads BD and BE become damaged and cannot be used. Robyn needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route must still start and finish at vertex A.
3. 1. State the edges that should be repeated.
   2. State a possible route and calculate its length. You must make your method and working clear.

5. \begin{figure}[h] \end{figure} Figure 5 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region.

1. Write down the inequalities that form region \(R\).
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = 2 x + 3 y\)
3. Use point testing to find the optimal vertex, V, of the feasible region. The objective is changed to maximise \(Q\), where \(Q = 2 x + \lambda y\)
   Given that \(\lambda\) is a constant and V is still the only optimal vertex of the feasible region,
4. find the range of possible values of \(\lambda\).

6. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 6. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the corresponding activity. Each activity requires exactly one worker. The project is to be completed in the shortest possible time.

1. Complete Diagram 1 in the answer book to show the early event times and the late event times.
2. Draw a Gantt chart for the project on the grid provided in the answer book.
3. State the activities that must be happening at time 18.5 An additional activity, P , is now included in the activity network shown in Figure 6. Activity P is immediately preceded only by activity D . No activity is dependent on the completion of activity P . Each activity still requires exactly one worker and the revised project is to be completed in the shortest possible time.
4. Explain, briefly, whether or not the revised project can be completed in the same time as the original project if the duration of activity P is
   1. 10 days
   2. 17 days

7. A caterer can make three different sizes of salad; small, medium and large. The caterer will make a total of at least 280 salads. The caterer wants at least \(35 \%\) of the salads to be small and no more than \(20 \%\) of the salads to be large. The caterer has enough ingredients to make 400 small salads or 300 medium salads or 200 large salads. The profit on each small, medium and large salad is \(40 \mathrm { p } , 60 \mathrm { p }\) and 85 p respectively. The caterer wants to maximise his total profit. Let \(x\) represent the number of small salads, \(y\) represent the number of medium salads and \(z\) represent the number of large salads. Formulate this information as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. You should not attempt to solve the problem.
(Total 8 marks)