AQA D2 (Decision Mathematics 2) 2013 January

1
Figure 1 below shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.

1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
2. On Figure 2 opposite, complete the precedence table.
3. Find the critical path.
4. Find the float time of activity \(E\).
5. Using Figure 3 on page 5, draw a resource histogram to illustrate how the project can be completed in the minimum time, assuming that each activity is to start as early as possible.
6. Given that there are two workers available for the project, find the minimum completion time for the project.
7. Given that there is only one worker available for the project, find the minimum completion time for the project. Figure 1 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(a)} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-02_629_1550_1818_292}
   \end{figure}
8. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2}

   Activity	Immediate predecessor(s)
   A
   B
   C
   D
   E
   \(F\)
   G
   H
   I
   J
   \(K\)

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-05_2486_1717_221_150}

2 Harry and Will play a zero-sum game. The game is represented by the following pay-off matrix for Harry.

1. Show that this game has a stable solution and state the play-safe strategy for each player.
2. List any saddle points.

3 Four pupils, Wendy, Xiong, Yasmin and Zaira, are each to be allocated a different memory coach from five available coaches: Asif, Bill, Connie, Deidre and Eric. Each pupil has an initial training session with each coach, and a test which scores their improvement in memory-recall produces the following results.

4

1. When investigating three network flow problems, a student finds:
   1. a flow of 50 and a cut with capacity 50 ;
   2. a flow of 35 and a cut with capacity 50 ;
   3. a flow of 50 and a cut with capacity 35 . In each case, write down what the student can deduce about the maximum flow.
2. The diagram below shows a network. The numbers on the arcs represent the minimum and maximum flow along each arc respectively. By considering the flow at an appropriate vertex, explain why a flow is not possible through this network.
   \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-10_1189_1559_1105_246}
   (2 marks)

5

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = x - 2 y + 3 z\)
   subject to $$\begin{array} { r } x + y + z \leqslant 16
   x - 2 y + 2 z \leqslant 17
   2 x - y + 2 z \leqslant 19 \end{array}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\).
2. 1. The first pivot to be chosen is from the \(z\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method.
3. 1. Perform one further iteration.
   2. Interpret the tableau that you obtained in part (c)(i) and state the values of your slack variables.

6 Kate and Pippa play a zero-sum game. The game is represented by the following pay-off matrix for Kate. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-18_2482_1707_223_155}

7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road. A collector is to drive from \(A\) to \(I\).
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-20_867_1644_552_191}

1. Working backwards from \(\boldsymbol { I }\), use dynamic programming to find the maximum number of bags that can be collected when driving from \(A\) to \(I\). You must complete the table opposite as your solution.
2. State the route that the collector should take in order to collect the maximum number of bags.

3. Stage	State	From	Value
   1	G	I
   	H	I
   2

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge.
\includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}

1. Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
2. 1. Taking your answers to part (a) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 5 opposite, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Route	Flow
   \(A B E H\)
   \(A C F H\)
   \(A D G H\)

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}