AQA D2 (Decision Mathematics 2) 2012 January

1 The diagram shows the activity network and the duration, in days, of each activity for a particular project. Some of the earliest start times and latest finish times are shown on the diagram.
\includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-02_830_1447_678_301}

1. Find the values of the constants \(x , y\) and \(z\).
2. Find the critical paths.
3. Find the activity with the largest float and state the value of this float.
4. 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	4	2	3	4	2	4	3	3	5	6

   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 1 below, indicating clearly which activities are taking place at any given time.
5. It is later discovered that there are only 9 workers available at any time. Use resource levelling to find the new earliest start time for activity \(J\) so that the project can be completed with the minimum extra time. State the minimum extra time required.
6. Number of workers \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-03_803_1330_1224_468}
   \end{figure}

2 A team with five members is training to take part in a quiz. The team members, Abby, Bob, Cait, Drew and Ellie, attempted sample questions on each of the five topics and their scores are given in the table. For the actual quiz, each topic must be allocated to exactly one of the team members. The maximum total score for the sample questions is to be used to allocate the different topics to the team members.

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

   8	6	8	0	4
   0	11	\(p\)	4	4
   10	4	6	0	12
   \(q\)	2	0	4	0
   0	0	6	6	0

3. Show that the zeros in the table in part (b) can be covered with two horizontal and two vertical lines. Hence use the Hungarian algorithm to reduce the table to a form where five lines are needed to cover the zeros.
4. 1. Hence find the possible allocations of topics to the five team members so that the total score for the sample questions is maximised.
   2. State the value of this maximum total score.

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

1. Explain what is meant by the term 'zero-sum game'.
2. Determine the play-safe strategy for Colum, giving a reason for your answer.
3. 1. Show that the matrix can be reduced to a 2 by 3 matrix, giving the reason for deleting one of the rows.
   2. Hence find the optimal mixed strategy for Roz.

4 A linear programming problem consists of maximising an objective function \(P\) involving three variables, \(x , y\) and \(z\), subject to constraints given by three inequalities other than \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\). Slack variables \(s , t\) and \(u\) are introduced and the Simplex method is used to solve the problem. One iteration of the method leads to the following tableau.

1. 1. State the column from which the pivot for the next iteration should be chosen. Identify this pivot and explain the reason for your choice.
   2. Perform the next iteration of the Simplex method.
2. 1. Explain why you know that the maximum value of \(P\) has been achieved.
   2. State how many of the three original inequalities still have slack.
3. 1. State the maximum value of \(P\) and the values of \(x , y\) and \(z\) that produce this maximum value.
   2. The objective function for this problem is \(P = k x - 2 y + 3 z\), where \(k\) is a constant. Find the value of \(k\).
      
      \includegraphics[max width=\textwidth, alt={}]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-11_2486_1714_221_153}

5 A firm is considering various strategies for development over the next few years. In the network, the number on each edge is the expected profit, in millions of pounds, moving from one year to the next. A negative number indicates a loss because of building costs or other expenses. Each path from \(S\) to \(T\) represents a complete strategy.
\includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-12_748_1575_559_228}

1. By completing the table on the page opposite, or otherwise, use dynamic programming working backwards from \(\boldsymbol { T }\) to find the maximum weight of all paths from \(S\) to \(T\).
2. State the overall maximum profit and the paths from \(S\) to \(T\) corresponding to this maximum profit.

3. Stage	State	From	Calculation	Value
   1	G	\(T\)
   	H	\(T\)
   	I	\(T\)
   2	D	G
   		\(H\)
   	E	G
   		\(H\)
   		I
   	\(F\)	\(H\)
   		I
   3

4. Maximum profit is £ \(\_\_\_\_\) million Corresponding paths from \(S\) to \(T\) \(\_\_\_\_\)

6 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]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}

1. Find the value of the cut \(Q\).
2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
   1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
   2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
   3. Use flow augmentation on Figure 3 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. 1. State the value of the maximum flow.
   2. Illustrate your maximum flow on Figure 4.
4. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
   \end{figure} Figure 3 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
   \end{figure}