AQA D2 (Decision Mathematics 2) 2015 June

1 Figure 2, on the page opposite, shows an activity diagram for a project. Each activity requires one worker. The duration required for each activity is given in hours.

1. On Figure 1 below, complete the precedence table.
2. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 2.
3. List the critical paths.
4. Find the float time of activity \(E\).
5. Using Figure 3 opposite, draw a Gantt diagram 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 is only one worker available for the project, find the minimum completion time for the project.
7. Given that there are two workers available for the project, find the minimum completion time for the project. Show a suitable allocation of tasks to the two workers.
   [0pt] [2 marks] \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1}

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

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_1071_1561_376_278}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-03_801_1301_1644_420}
   \end{figure}

2 Stan and Christine play a zero-sum game. The game is represented by the following pay-off matrix for Stan. \begin{table}[h] \end{table}

1. Find the play-safe strategy for each player.
2. Show that there is no stable solution.
3. Explain why a suitable pay-off matrix for Christine is given by

3 In the London 2012 Olympics, the Jamaican \(4 \times 100\) metres relay team set a world record time of 36.84 seconds. Athletes take different times to run each of the four legs.
The coach of a national athletics team has five athletes available for a major championship. The lowest times that the five athletes take to cover each of the four legs is given in the table below. The coach is to allocate a different athlete from the five available athletes, \(A , B , C , D\) and \(E\), to each of the four legs to produce the lowest total time. Use the Hungarian algorithm, by reducing the columns first, to assign an athlete to each leg so that the total time of the four athletes is minimised. State the allocation of the athletes to the four legs and the total time.
[0pt] [11 marks]

4

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l r } \text { Maximise } & P = 2 x + 3 y + 4 z
   \text { subject to } & x + y + 2 z \leqslant 20
   & 3 x + 2 y + z \leqslant 30
   & 2 x + 3 y + z \leqslant 40
   \text { and } & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
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 your final tableau and state the values of your slack variables.

5 Tom is going on a driving holiday and wishes to drive from \(A\) to \(K\).
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level. Tom wants to ensure that the maximum altitude of any road along the route from \(A\) to \(K\) is minimised.
\includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}

1. Working backwards from \(\boldsymbol { K }\), use dynamic programming to find the optimal route when driving from \(A\) to \(K\). You must complete the table opposite as your solution.
2. Tom finds that the road \(C F\) is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.
   [0pt] [2 marks] \section*{Answer space for question 5}

   Stage	State	From	Value
   1	H	\(K\)
   	I	\(K\)
   	\(J\)	\(K\)
   2

3. Optimal route is \(\_\_\_\_\)
4. Tom's route is \(\_\_\_\_\)
   Maximum altitude is \(\_\_\_\_\) Figure 4 below shows a network of pipes.
   The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
   \end{figure}
5. Find the value of the initial flow.
6. 1. Use the initial flow and the labelling procedure on Figure 5 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 6, illustrate a possible flow along each edge corresponding to this maximum flow.
7. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
8. On a particular day, there is a restriction at vertex \(G\) which allows a maximum flow through \(G\) of 30 . Find, by inspection, the maximum flow through the network on this day.
9. Initial flow \(=\) \(\_\_\_\_\)
10. 1. Figure 5
       \includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296}
       \(7 \quad\) Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where \(x\) is a constant. The value of the game is 2.5 .

       Jose
       \cline { 2 - 4 }	Strategy	C	D
       \cline { 2 - 4 } Arsene	A	\(x + 3\)	1
       \cline { 2 - 4 }	B	\(x + 1\)	3
       \cline { 2 - 4 }
       \cline { 2 - 4 }

11. Find the optimal mixed strategy for Arsene.
12. Find the value of \(x\).
    \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
    \includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}