AQA D2 (Decision Mathematics 2) 2008 June

1 [Figures 1 and 2, printed on the insert, are provided for use in this question.]
The following diagram shows an activity network for a project. The time needed for each activity is given in days.
\includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-02_940_1698_721_164}

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.
3. On Figure 2, draw a cascade diagram (Gantt chart) for the project, assuming each activity starts as early as possible.
4. Activity \(C\) takes 5 days longer than first expected. Determine the effect on the earliest start time for other activities and the minimum completion time for the project.
   (2 marks)

2 The following table shows the scores of five people, Alice, Baji, Cath, Dip and Ede, after playing five different computer games. Each of the five games is to be assigned to one of the five people so that the total score is maximised. No person can be assigned to more than one game.

1. Explain why the Hungarian algorithm may be used if each number, \(x\), in the table is replaced by \(20 - x\).
2. Form a new table by subtracting each number in the table above from 20, and hence show that, by reducing columns first and then rows, the resulting table of values is as below.

   3	1	1	1	0
   0	4	5	2	2
   4	0	5	0	7
   5	1	0	1	1
   5	1	0	2	5

3. Show that the zeros in the table in part (b) can be covered with one horizontal and three vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. Hence find the possible allocations of games to the five people so that the total score is maximised.
5. State the value of the maximum total score.

3 Two people, Roseanne and Collette, play a zero-sum game. The game is represented by the following pay-off matrix for Roseanne.

1. 1. Find the optimal mixed strategy for Roseanne.
   2. Show that the value of the game is - 0.5 .
2. 1. Collette plays strategy \(\mathrm { C } _ { 1 }\) with probability \(p\) and strategy \(\mathrm { C } _ { 2 }\) with probability \(q\). Write down, in terms of \(p\) and \(q\), the probability that she plays strategy \(\mathrm { C } _ { 3 }\).
   2. Hence, given that the value of the game is - 0.5 , find the optimal mixed strategy for Collette.

4 A linear programming problem consists of maximising an objective function \(P\) involving three variables \(x , y\) and \(z\). Slack variables \(s , t , u\) and \(v\) are introduced and the Simplex method is used to solve the problem. Several iterations of the method lead to the following tableau.

1. 1. The pivot for the next iteration is chosen from the \(\boldsymbol { y }\)-column. State which value should be chosen and explain the reason for your choice.
   2. Perform the next iteration of the Simplex method.
2. Explain why your new tableau solves the original problem.
3. State the maximum value of \(P\) and the values of \(x , y\) and \(z\) that produce this maximum value.
4. State the values of the slack variables at the optimum point. Hence determine how many of the original inequalities still have some slack when the optimum is reached.

5 [Figure 3, printed on the insert, is provided for use in this question.]
A small firm produces high quality cabinets.
It can produce up to 4 cabinets each month.
Whenever at least one cabinet is made during that month, the overhead costs for that month are \(\pounds 300\). It is possible to hold in stock a maximum of 2 cabinets during any month.
The cost of storage is \(\pounds 50\) per cabinet per month.
The orders for cabinets are shown in the table below. There is no stock at the beginning of January and the firm plans to clear all stock after completing the April orders.

1. Determine the total cost of storing 2 cabinets and producing 3 cabinets in a given month.
2. By completing the table of values on Figure 3, or otherwise, use dynamic programming, working backwards from April, to find the production schedule which minimises total costs.
3. Each cabinet is sold for \(\pounds 2000\) but there is an additional cost of \(\pounds 300\) for materials to make each cabinet and \(\pounds 2000\) per month in wages. Determine the total profit for the four-month period.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-06_796_1337_518_338}

1. 1. Find the value of the cut \(C\).
   2. Hence state what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 32 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(P Q , U Q\) and \(U T\).
3. 1. Taking your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.