Edexcel D1 (Decision Mathematics 1) 2018 January

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

1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, \(1,2,3\), 4, 5 and 6 Figure 2 shows an initial matching.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.

2. \begin{figure}[h] \end{figure} The network in Figure 3 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. Each activity requires exactly one worker. The early event times and late event times are shown at each vertex. Given that the total float on activity B is 2 days and the total float on activity F is also 2 days,

1. find the values of \(w , x , y\) and \(z\).
2. Draw a cascade (Gantt) chart for this project on Grid 1 in the answer book.
3. 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.)

3. \begin{figure}[h] \end{figure} Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
2. Find a route of minimal length that goes from D to H via A and state its length.
3. Use Prim's algorithm, starting at E , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. Find the length, in kilometres, of your minimum spanning tree.

4. \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. 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 = 2 x + 3 y\).
3. Use point testing at each vertex to find the optimal vertex, \(V\), of the feasible region and state the corresponding value of \(P\) at \(V\).
   (3) The objective is changed to maximise \(Q = 2 x + k y\), where \(k\) is a constant.
4. Find the range of values of \(k\) for which the vertex identified in (c) is still optimal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 6 represents a network of footpaths in a park. The number on each arc is the length, in metres, of the corresponding footpath. An inspection route of minimum length that traverses each footpath at least once needs to be found.

1. Write down the nodes at which the route will start and finish.
   (1) It is now decided to start the inspection route at B and finish the inspection route at D . A route of minimum length that traverses each footpath at least once needs to be found.
2. By considering the pairings of all relevant nodes find the arcs that will need to be traversed twice. You must make your method and working clear.
3. Write down a possible shortest inspection route, giving its length.

6. $$\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}$$ The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.

1. Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting. The list of numbers above is to be sorted into ascending order.
   Starting at the left-hand end of the list, after three passes of the bubble sort, the list is $$\begin{array} { l l l l l l l l l l } 11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60 \end{array}$$
2. 1. Write down the list that results at the end of the fourth pass.
   2. Write down the number of comparisons and swaps performed during the fourth pass. The original list of numbers is now to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.

7. Emily is planning to sell three types of milkshake, strawberry, vanilla and chocolate. Emily has completed some market research and has used this to form the following constraints on the number of milkshakes that she will sell each week.

• She will sell fewer than 200 non-vanilla milkshakes in total.
• She will sell at most 2.5 times as many strawberry milkshakes as vanilla milkshakes.
• At most, \(75 \%\) of the milkshakes that she will sell will be vanilla.

The profit on each strawberry milkshake sold is \(\pounds 0.75\), the profit on each vanilla milkshake sold is \(\pounds 1.20\) and the profit on each chocolate milkshake sold is \(\pounds 1.45\) Emily wants to maximise her profit.
Let \(x\) represent the number of strawberry milkshakes sold, let \(y\) represent the number of vanilla milkshakes sold and let \(z\) represent the number of chocolate milkshakes sold.

1. Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. In week 1, Emily sells 100 strawberry milkshakes and 25 chocolate milkshakes.
2. Calculate the maximum possible profit and minimum possible profit, in pounds, for the sale of all milkshakes in week 1. You must show your working.

8. \begin{figure}[h] \end{figure} 4. \begin{figure}[h] \end{figure} 5. \begin{figure}[h] \end{figure} 6.
\(\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}\) 7.