Edexcel D1 (Decision Mathematics 1) 2005 June

1. The table shows the marks obtained by students in a test. The students are listed in alphabetical order. Carry out a quick sort to produce a list of students in descending order of marks. You should show the result of each pass and identify your pivots clearly.
(Total 5 marks)

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

1. Starting from \(A\); write down a Hamiltonian cycle for the graph in Figure 1.
2. Use the planarity algorithm to show that the graph in Figure 1 is planar. Arcs \(A F\) and \(E F\) are now added to the graph.
3. Explain why the new graph is not planar.
   (2) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-3_725_1318_266_352}
   \end{figure} Figure 2 models a network of roads which need to be inspected to assess if they need to be resurfaced. The number on each arc represents the length, in km, of that road. Each road must be traversed at least once and the length of the inspection route must be minimised.
4. Starting and finishing at \(A\), solve this route inspection problem. You should make your method and working clear. State the length of the shortest route.
   (The weight of the network is 77 km .) Given that it is now permitted to start and finish the inspection at two distinct vertices,
5. state which two vertices you should choose to minimise the length of the route. Give a reason for your answer.

4. The precedence table shows the activities involved in a project.

1. Draw the activity network for this project, using activity on arc and using two dummies.
2. Explain why each of the two dummies is necessary.
   (3)
   (Total 7 marks) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-5_635_446_296_485}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-5_639_450_296_1233}
   \end{figure} A film critic, Verity, must see five films A, B, C, D and E over two days.
   The films are being shown at five special critics' preview times:
   \(\begin{array} { l l } 1 & ( \text { Monday } 4 \mathrm { pm } ) ,
   2 & ( \text { Monday } 7 \mathrm { pm } ) ,
   3 & ( \text { Tuesday } 1 \mathrm { pm } ) ,
   4 & ( \text { Tuesday } 4 \mathrm { pm } ) ,
   5 & ( \text { Tuesday } 7 \mathrm { pm } ) . \end{array}\)
   The bipartite graph in Figure 3 shows the times at which each film is showing.
   Initially Verity intends to see \begin{displayquote} Film A on Monday at 4 pm , Film B on Tuesday at 4 pm , Film C on Tuesday at 1 pm , Film D on Monday at 7 pm . \end{displayquote} This initial matching is shown in Figure 4.
   Using the maximum matching algorithm and the given initial matching,
3. find two distinct alternating paths and complete the matchings they give. Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm .
4. Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself.

6. \begin{figure}[h] \end{figure} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km .

1. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length.
   (5)
2. Explain how you determined the shortest route from your labelled diagram. The road from \(C\) to \(F\) will be closed next week for repairs.
3. Find the shortest route from \(A\) to \(J\) that does not include \(C F\) and state its length.
   (3)
   (Total 10 marks)

7. Polly has a bird food stall at the local market. Each week she makes and sells three types of packs \(A , B\) and \(C\). Pack \(A\) contains 4 kg of bird seed, 2 suet blocks and 1 kg of peanuts.
Pack \(B\) contains 5 kg of bird seed, 1 suet block and 2 kg of peanuts.
Pack \(C\) contains 10 kg of bird seed, 4 suet blocks and 3 kg of peanuts.
Each week Polly has 140 kg of bird seed, 60 suet blocks and 60 kg of peanuts available for the packs. The profit made on each pack of \(A , B\) and \(C\) sold is \(\pounds 3.50 , \pounds 3.50\) and \(\pounds 6.50\) respectively. Polly sells every pack on her stall and wishes to maximise her profit, \(P\) pence. Let \(x , y\) and \(z\) be the numbers of packs \(A , B\) and \(C\) sold each week.
An initial Simplex tableau for the above situation is

1. Explain the meaning of the variables \(r , s\) and \(t\) in the context of this question.
   (2)
2. Perform one complete iteration of the Simplex algorithm to form a new tableau \(T\). Take the most negative number in the profit row to indicate the pivotal column.
3. State the value of every variable as given by tableau \(T\).
4. Write down the profit equation given by tableau \(T\).
5. Use your profit equation to explain why tableau \(T\) is not optimal. Taking the most negative number in the profit row to indicate the pivotal column,
6. identify clearly the location of the next pivotal element.
   (2)
   (Total 15 marks)

8. \begin{figure}[h] \end{figure} Figure 6 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.

1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
2. Complete the initial labelling procedure in Diagram 2.
3. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow, and state the maximal flow.
4. Show a maximal flow pattern on Diagram 3.
5. Prove that your flow is maximal.
6. Describe briefly a situation for which this network could be a suitable model.