Edexcel D1 (Decision Mathematics 1) 2019 June

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use and state your improved matching after each iteration.
   (6)

2. \begin{figure}[h] \end{figure} A surveyor needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Figure 3. The number on each arc represents the length of that road in miles. To check all the roads, she needs to travel along each road at least once. She wishes to minimise the total distance travelled. The surveyor's office is at F , so she starts and ends her journey at F .

1. Find a route for the surveyor to follow. State your route and its length. You must make your method and reasoning clear. The surveyor lives at D and wonders if she can reduce the distance travelled by starting from home and inspecting all the roads on the way to her office at F .
2. By considering the pairings of all relevant nodes, find the arcs that will need to be traversed twice in the inspection route from D to F. You must make your method and working clear.
3. Determine which of the two routes, the one starting at F and ending at F , or the one starting at D and ending at F , is longer. You must show your working.

3. The table above shows the lengths, in metres, of the paths between nine vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G, H and J.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book.
2. State whether your minimum spanning tree is unique. Justify your answer.
3. Use Dijkstra's algorithm to find the length of the shortest path from A to J.

4. $$\begin{array} { l l l l l l l l l l l } 25 & 9 & 32 & 16 & 17 & 23 & 18 & 12 & 4 & 8 & 40 \end{array}$$ The numbers in the list represent the weights, in kilograms, of eleven suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 50 kg .

1. Calculate a lower bound for the number of containers needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
3. Carry out a quick sort 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 to allocate the suitcases to the containers. The two heaviest suitcases are replaced with two suitcases both of which weigh \(x \mathrm {~kg}\). It is given that the lower bound for the number of containers needed is now one less than the number found in (a).
5. Determine the range of values for \(x\). You should make your working clear.

5.

1. Draw the activity network described in the precedence table above, using activity on arc and exactly 4 dummies.
2. Explain why one of the activities I or J must be critical. It is given that activity C is a critical activity.
3. State the activities that are therefore guaranteed to be critical.

6. \begin{figure}[h] \end{figure} Figure 4 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The vertices of the feasible region are \(A ( 4,7 ) , B ( 5,3 ) , C ( - 1,5 )\) and \(D ( - 2,1 )\).

1. Determine the inequality that defines the boundary of \(R\) that passes through vertices \(A\) and \(C\), leaving your answer with integer coefficients only. The objective is to maximise \(P = 5 x + y\)
2. Find the coordinates of the optimal vertex and the corresponding value of \(P\). The objective is changed to maximise \(Q = k x + y\)
3. If \(k\) can take any value, find the range of values of \(k\) for which \(A\) is the only optimal vertex.