Edexcel D1 (Decision Mathematics 1) 2019 January

1. (a) Define the term 'bipartite graph'.

Six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be matched to six tasks, 1, 2, 3, 4, 5 and 6 The table below shows the tasks that each worker is able to do. (b) Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocation of workers to tasks.
(1) Initially, workers \(\mathrm { A } , \mathrm { C } , \mathrm { E }\) and F are allocated to tasks 2, 4, 5 and 6 respectively.
(c) Starting from the given initial matching, apply the maximum matching algorithm to obtain a complete matching. You must state the alternating paths that you use, and state your improved matching after each iteration.

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads. The number on each arc is the length, in km , of the corresponding road.

1. Use Dijkstra's algorithm to find the shortest route from A to L. State the shortest route and its length.
2. Explain how you determined the shortest route from your labelled diagram.
3. Find the length of the shortest route from J to F via A , and state your route.

3. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 2. 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 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. State the critical activities.
3. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
4. Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

4. $$\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}$$ The numbers in the list above represent the weights, in kilograms, of 11 boxes. John must transport all the boxes using his van. You may assume the van has sufficient space for any combination of boxes. Each van load of boxes must weigh at most 475 kg .

1. Calculate a lower bound for the number of van loads needed to transport all 11 boxes.
2. Use the first-fit bin packing algorithm to show how the boxes could be put into van loads. State the number of van loads needed according to this solution.
3. Carry out a quick sort on the numbers in the list given above to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm on your ordered list to show how the boxes could be put into van loads. State the number of van loads needed according to this solution. Due to volume restrictions, the van cannot transport more than three boxes at any one time.
5. Show how the boxes could now be put into the minimum number of van loads.

5.

1. Draw the activity network described in the precedence table above, using activity on arc. Your activity network must contain only the minimum number of dummies.
   (5) Given that D is a critical activity,
2. state which other activities must also be critical.
   (1)

6. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 17\) ]

1. Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
2. During rush hour one day \(x = 9\)
   1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
   2. Calculate the weight of the minimum spanning tree. You are now given that \(x > 3\) A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
3. Determine the value of \(x\), showing your working clearly.

7. A company makes two types of wooden bookcase, the Manhattan and the Brooklyn. The pieces of wood used for each bookcase go through three stages. They must be cut, assembled and packaged. The table below shows the time, in hours, needed to complete each of the three stages for a single bookcase, and the profit made, in pounds, when each type of bookcase is sold. The table also shows the amount of time, in hours, that is available each week for each of the three stages. Shortest route: \(\_\_\_\_\)
Length of shortest route: \(\_\_\_\_\)
3. \section*{Diagram 1} \section*{Grid 1} 4. \(\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}\) \(\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}\) 5.

1. (a)
   \includegraphics[max width=\textwidth, alt={}, center]{e7f89fa1-0afa-4aec-a430-14ec98f487c8-22_616_1477_735_230}
   

\begin{figure}[h] \end{figure} 7. \begin{figure}[h] \end{figure}