AQA D2 (Decision Mathematics 2) 2013 June

1 Figure 1 opposite shows an activity diagram for a project. The duration required for each activity is given in hours. The project is to be completed in the minimum time.

1. Find the earliest start time and the latest finish time for each activity and insert their values on Figure 1.
2. Find the critical path.
3. Find the float time of activity \(E\).
4. Given that activities \(H\) and \(K\) will both overrun by 10 hours, find the new minimum completion time for the project.
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-02_1515_1709_1192_153}
   \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-03_1656_869_627_611}
   \end{figure}

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

3 The table shows the times taken, in minutes, by five people, \(A , B , C , D\) and \(E\), to carry out the tasks \(V , W , X , Y\) and \(Z\). Each of the five tasks is to be given to a different one of the five people so that the total time for the five tasks is minimised. The Hungarian algorithm is to be used.

1. By reducing the columns first, and then the rows, show that the new table of values is

   0	12	13	2	0
   14	21	0	\(k\)	9
   3	10	0	6	23
   0	2	6	20	0
   0	0	0	0	7

   and state the value of the constant \(k\).
2. Show that the zeros in the table in part (a) can be covered with four lines. Use augmentation twice to produce a table where five lines are required to cover the zeros.
3. Hence find the possible ways of allocating the five tasks to the five people to achieve the minimum total time.
4. Find the minimum total time.

4 A haulage company, based in town \(A\), is to deliver a tall statue to town \(K\). The statue is being delivered on the back of a lorry. The network below shows a system of roads. The number on each edge represents the height, in feet, of the lowest bridge on that road. The company wants to ensure that the height of the lowest bridge along the route from \(A\) to \(K\) is maximised.
\includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-10_869_1593_715_221} 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. Optimal route is

5 Romeo and Juliet play a zero-sum game. The game is represented by the following pay-off matrix for Romeo.

1. Find the play-safe strategy for each player.
2. Show that there is no stable solution.
3. Explain why Juliet should never play strategy D.
4. 1. Explain why the following is a suitable pay-off matrix for Juliet.

      4	5	- 1
      0	- 3	2

   2. Hence find the optimal strategy for Juliet.
   3. Find the value of the game for Juliet.

6

1. Display the following linear programming problem in a Simplex tableau.
   Maximise \(\quad P = 4 x + 3 y + z\)
   subject to $$\begin{aligned} & 2 x + y + z \leqslant 25
   & x + 2 y + z \leqslant 40
   & x + y + 2 z \leqslant 30 \end{aligned}$$ and \(x \geqslant 0 , \quad y \geqslant 0 , \quad z \geqslant 0\).
2. The first pivot to be chosen is from the \(x\)-column. 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.

7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
2. 1. Use the initial flow and the labelling procedure on Figure 3 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 4, 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{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}