AQA D2 (Decision Mathematics 2) 2009 January

1 The times taken in minutes for five people, \(\mathrm { P } , \mathrm { Q } , \mathrm { R } , \mathrm { S }\) and T , to complete each of five different tasks are recorded in the table. Using the Hungarian algorithm, each of the five people is to be allocated to a different task so that the total time for completing the five tasks is minimised.

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

   3	5	3	0	1
   6	4	3	2	0
   3	5	4	1	0
   3	2	3	0	1
   0	0	0	1	1

2. Show that the zeros in the table in part (a) can be covered with three lines, and use adjustments to produce a table where five lines are required to cover the zeros.
3. Hence find the two possible ways of allocating the five people to the five tasks so that the total completion time is minimised.
4. Find the minimum total time for completing the five tasks.

2 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
Figure 1 shows the activity network and the duration in days of each activity for a particular project.

1. On Figure 1:
   1. find the earliest start time for each activity;
   2. find the latest finish time for each activity.
2. Find the critical paths and state the minimum time for completion.
3. The number of workers required for each activity is shown in the table.

   Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
   Number of workers required	3	3	4	2	3	4	1	2	2	5

   1. Given that each activity starts as early as possible and assuming that there is no limit to the number of workers available, draw a resource histogram for the project on Figure 2, indicating clearly which activities take place at any given time.
   2. It is later discovered that there are only 6 workers available at any time. Explain why the project will overrun, and use resource levelling to indicate which activities need to be delayed so that the project can be completed with the minimum extra time. State the minimum extra time required.

3

1. Display the following linear programming problem in a Simplex tableau. $$\begin{array} { l l } \text { Maximise } & P = 4 x - 5 y + 6 z
   \text { subject to } & 6 x + 7 y - 4 z \leqslant 30
   & 2 x + 4 y - 5 z \leqslant 8
   & x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
2. The Simplex method is to be used to solve this problem.
   1. Explain why it is not possible to choose a pivot from the \(z\)-column initially.
   2. Identify the initial pivot and explain why this particular element should be chosen.
   3. Perform one iteration using your initial tableau from part (a).
   4. State the values of \(x , y\) and \(z\) after this first iteration.
   5. Without performing any further iterations, explain why \(P\) has no finite maximum value.
3. Using the same inequalities as in part (a), the problem is modified to $$\text { Maximise } \quad Q = 4 x - 5 y - 20 z$$
   1. Write down a modified initial tableau and the revised tableau after one iteration.
   2. Hence find the maximum value of \(Q\).

4

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

   	Cal
   \cline { 2 - 5 }	Strategy	X	Y	Z
   Raj	I	- 7	8	- 5
   \cline { 2 - 5 }	II	6	2	- 1
   \cline { 2 - 5 }	III	- 2	4	- 3
   \cline { 2 - 5 }
   \cline { 2 - 5 }

   Show that this game has a stable solution and state the play-safe strategy for each player.
2. Ros and Carly play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Ros, where \(x\) is a constant.

   	Carly
   \cline { 2 - 4 }	Strategy		\(\mathbf { C } _ { \mathbf { 1 } }\)
   \cline { 2 - 4 }\cline { 2 - 3 } \(\operatorname { Ros }\)	\(\mathbf { R } _ { \mathbf { 1 } }\)	5	\(\mathbf { C } _ { \mathbf { 2 } }\)
   \cline { 2 - 4 }	\(\mathbf { R } _ { \mathbf { 2 } }\)	- 2	\(x\)
   \cline { 2 - 4 }			4

   Ros chooses strategy \(\mathrm { R } _ { 1 }\) with probability \(p\).
   1. Find expressions for the expected gains for Ros when Carly chooses each of the strategies \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   2. Given that the value of the game is \(\frac { 8 } { 3 }\), find the value of \(p\) and the value of \(x\).

5 [Figure 3, printed on the insert, is provided for use in this question.]
A truck has to transport stones from a quarry, \(Q\), to a builders yard, \(Y\). The network shows the possible roads from \(Q\) to \(Y\). Along each road there are bridges with weight restrictions. The value on each edge indicates the maximum load in tonnes that can be carried by the truck along that particular road.
\includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-6_723_1280_589_372} The truck is able to carry a load of up to 20 tonnes. The optimal route, known as the maximin route, is that for which the possible load that the truck can carry is as large as possible.

1. Explain why the route \(Q A C Y\) is better than the route \(Q B E Y\).
2. By completing the table on Figure 3, or otherwise, use dynamic programming, working backwards from \(\boldsymbol { Y }\), to find the optimal (maximin) route from \(Q\) to \(Y\). Write down the maximin route and state the maximum possible load that the truck can carry from \(Q\) to \(Y\).

6 [Figures 4 and 5, printed on the insert, are provided for use in this question.]
The network shows the routes along corridors from two arrival gates to the passport control area, \(P\), in a small airport. The number on each edge represents the maximum number of passengers that can travel along a particular corridor in one minute.
\includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-7_933_1063_552_486}

1. State the vertices that represent the arrival gates.
2. Find the value of the cut shown on the network.
3. State the maximum flow along each of the routes UTSP and RQVP.
4. 1. Taking your answers to part (c) 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 paths 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, illustrate a possible flow along each edge corresponding to this maximum flow.
5. On a particular day, there is an obstruction allowing no more than 50 passengers per minute to pass through vertex \(V\). State the maximum number of passengers that can move through the network per minute on this particular day.
   (2 marks)