AQA D2 (Decision Mathematics 2) 2011 June

1 Figure 1 below shows an activity diagram for a cleaning project. The duration of each activity is given in days.

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 paths and state the minimum time for completion of the project.
3. Find the activity with the greatest float time and state the value of its float time.
4. On Figure 2 opposite, draw a cascade diagram (Gantt chart) for the project, assuming that each activity starts as late as possible.
5. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-02_846_1488_1391_292}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1295_1714_219_150} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(d)} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-03_1023_1584_1589_278}
   \end{figure}

2 The times taken, in minutes, for five people, \(A , B , C , D\) and \(E\), to complete each of five different puzzles are recorded in the table below. Using the Hungarian algorithm, each of the five people is to be allocated to a different puzzle so that the total time for completing the five puzzles is minimised.

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

   3	1	0	4	1
   0	\(k\)	0	1	3
   1	0	3	1	2
   2	3	2	0	0
   0	5	1	2	1

   State the value of the constant \(k\).
2. 1. Show that the zeros in the table in part (a) can be covered with one horizontal and three vertical lines.
   2. Use augmentation to produce a table where five lines are required to cover the zeros.
3. Hence find all the possible ways of allocating the five people to the five puzzles so that the total completion time is minimised.
4. Find the minimum total time for completing the five puzzles.
5. Explain how you would modify the original table if the Hungarian algorithm were to be used to find the maximum total time for completing the five puzzles using five different people.

3

1. Two people, Tom and Jerry, play a zero-sum game. The game is represented by the following pay-off matrix for Tom.

   	Jerry
   \cline { 2 - 5 }	Strategy	A	B	C
   Tom	I	- 4	5	- 3
   \cline { 2 - 5 }	II	- 3	- 2	8
   \cline { 2 - 5 }	III	- 7	6	- 2

   Show that this game has a stable solution and state the play-safe strategy for each player.
2. Rohan and Carla play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Rohan. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Carla} Rohan

   Strategy	\(\mathbf { C } _ { \mathbf { 1 } }\)	\(\mathbf { C } _ { \mathbf { 2 } }\)	\(\mathbf { C } _ { \mathbf { 3 } }\)
   \(\mathbf { R } _ { \mathbf { 1 } }\)	3	5	- 1
   \(\mathbf { R } _ { \mathbf { 2 } }\)	1	- 2	4

   \end{table}
   1. Find the optimal mixed strategy for Rohan and show that the value of the game is \(\frac { 3 } { 2 }\).
   2. Carla plays strategy \(\mathrm { C } _ { 1 }\) with probability \(p\), and strategy \(\mathrm { C } _ { 2 }\) with probability \(q\). Find the values of \(p\) and \(q\) and hence find the optimal mixed strategy for Carla.
      (4 marks)
      
      \includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-10_2486_1714_221_153}
      \includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-11_2486_1714_221_153}

4 A linear programming problem involving variables \(x , y\) and \(z\) is to be solved. The objective function to be maximised is \(P = 2 x + 6 y + k z\), where \(k\) is a constant. The initial Simplex tableau is given below.

1. In addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), write down three inequalities involving \(x , y\) and \(z\) for this problem.
2. 1. By choosing the first pivot from the \(\boldsymbol { y }\)-column, perform one iteration of the Simplex method.
   2. Given that the optimal value has not been reached, find the possible values of \(k\).
3. In the case when \(k = 20\) :
   1. perform one further iteration;
   2. interpret the final tableau and state the values of the slack variables.

5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding.
\includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at \(A\) and \(G\) and the exit is at \(X\). The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.

1. Find the value of the cut shown on the diagram.
2. Find the maximum flow along each of the routes \(A B D X , G F B X\) and \(G H E X\) and enter their values in the table on Figure 3 opposite.
3. 1. Taking your answers to part (b) as the initial flow, use 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.
4. During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex \(B\). State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
   \end{figure} Figure 4
   \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is \(\_\_\_\_\) people per minute.

6 Bob is planning to build four garden sheds, \(A , B , C\) and \(D\), at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below. By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit. \section*{Schedule} Turn over