Edexcel D1 (Decision Mathematics 1) 2016 June

1. $$\begin{array} { l l l l l l l l l } 4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 2.7 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
3. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
4. Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree. A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
5. Explain why Prim's algorithm could not be used to complete the tree.

2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, \(1,2,3,4,5\) and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 2 shows an initial matching.
2. Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.
   (3)
3. Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.

3. \begin{figure}[h] \end{figure} Figure 3 shows the constraints of a linear programming problem in \(x\) and \(y\), where \(R\) is the feasible region. The equations of two of the lines have been given.

1. Determine the inequalities that define the feasible region.
2. Find the exact coordinates of the vertices of the feasible region. The objective is to maximise \(P\), where \(P = k x + y\).
3. For the case \(k = 2\), use point testing to find the optimal vertex of the feasible region.
4. For the case \(k = 2.5\), find the set of points for which \(P\) takes its maximum value.

4. (a) Draw the activity network described in the precedence table below, using activity on arc and the minimum number of dummies. A project is modelled by the activity network drawn in (a). Each activity requires one worker. The project is to be completed in the shortest possible time. The table below gives the time, in days, to complete some of the activities. The critical activities for the project are B, F, I, J and L and the length of the critical path is 30 days.
(b) Calculate the duration of activity I.
(c) Find the range of possible values for the duration of activity K .

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

1. Explain what is meant by the term 'path'.
   (2) Figure 4 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Tomek wishes to travel from A to J.
2. Use Dijkstra's algorithm to find the shortest path from A to J. State your path and its length.
   (6) On a particular day, Tomek needs to travel from G to J via A.
3. Find the shortest route from G to J via A , and find its length.
   (3) The road HJ becomes damaged and cannot be used. Tomek needs to travel along all the remaining roads to check that there is no damage to any of them. The inspection route he uses must start and finish at B .
4. Use an appropriate algorithm to find the length of a shortest inspection route. State the arcs that should be repeated. You should make your method and working clear.
   (5)
5. Write down a possible shortest inspection route.
   (1)

6. \begin{figure}[h] \end{figure} A project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the 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 late event times.
2. State the critical activities.
3. Calculate the maximum number of days by which activity E could be delayed without lengthening the completion time of the project. You must make the numbers used in your calculation clear.
4. Calculate a lower bound for the number of workers needed to complete the project in the minimum time. You must show your working.
5. Draw a cascade (Gantt) chart for this project on the grid provided in the answer book.

7. A theatre company is planning to sell two types of ticket, standard and premier. The theatre company has completed some market research and has used this to form the following constraints.

• They will sell at most 450 tickets.
• They will sell at least three times as many standard tickets as premier tickets.
• At most \(85 \%\) of all the tickets sold will be standard.

The theatre wants to maximise its profit. The profit on each standard ticket sold is \(\pounds 5\) and the profit on each premier ticket sold is \(\pounds 8\)
Let \(x\) represent the number of standard tickets sold and \(y\) represent the number of premier tickets sold. Formulate this 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 6 marks)