AQA D2 (Decision Mathematics 2) 2011 January

1
A group of workers is involved in a decorating project. The table shows the activities involved. Each worker can perform any of the given activities. The activity network for the project is given in Figure 1 below.

1. Find the earliest start time and the latest finish time for each activity, inserting their values on Figure 1.
2. Hence find:
   1. the critical path;
   2. the float time for activity \(D\).
3. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-02_647_1657_1640_180}
   \end{figure}
4. 1. The critical path is \(\_\_\_\_\)
   2. The float time for activity \(D\) is \(\_\_\_\_\)
5. 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 below, indicating clearly which activities are taking place at any given time.
6. It is later discovered that there are only 8 workers available at any time. Use resource levelling to construct a new resource histogram on Figure 3 below, showing how the project can be completed with the minimum extra time. State the minimum extra time required.
7. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_586_1708_922_150}
   \end{figure}
8. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-03_496_1705_1672_153}
   \end{figure} The minimum extra time required is \(\_\_\_\_\)

2 A farmer has five fields. He intends to grow a different crop in each of four fields and to leave one of the fields unused. The farmer tests the soil in each field and calculates a score for growing each of the four crops. The scores are given in the table below. The farmer's aim is to maximise the total score for the four crops.

1. 1. Modify the table of values by first subtracting each value in the table above from 20 and then adding an extra row of equal values.
   2. Explain why the Hungarian algorithm can now be applied to the new table of values to maximise the total score for the four crops.
2. 1. By reducing rows first, show that the table from part (a)(i) becomes

      2	6	10	0	\(p\)
      0	5	12	4	8
      8	7	5	0	\(q\)
      1	8	2	4	0
      0	0	0	0	0

      State the values of the constants \(p\) and \(q\).
   2. Show that the zeros in the table from part (b)(i) can be covered by one horizontal and three vertical lines, and use the Hungarian algorithm to decide how the four crops should be allocated to the fields.
   3. Hence find the maximum possible total score for the four crops.

3 Two people, Rhona and Colleen, play a zero-sum game. The game is represented by the following pay-off matrix for Rhona. It is given that \(x < 2\).

1. 1. Write down the three row minima.
   2. Show that there is no stable solution.
2. Explain why Rhona should never play strategy \(R _ { 3 }\).
3. 1. Find the optimal mixed strategy for Rhona.
   2. Find the value of the game.

4 The Simplex method is to be used to maximise \(P = 3 x + 2 y + z\) subject to the constraints $$\begin{aligned} - x + y + z & \leqslant 4
2 x + y + 4 z & \leqslant 10
4 x + 2 y + 3 z & \leqslant 21 \end{aligned}$$ The initial Simplex tableau is given below.

1. 1. The first pivot is to be chosen from the \(x\)-column. Identify the pivot and explain why this particular value is chosen.
   2. Perform one iteration of the Simplex method and explain how you know that the optimal value has not been reached.
2. 1. Perform one further iteration.
   2. Interpret the final tableau and write down the initial inequality that still has slack.
      \includegraphics[max width=\textwidth, alt={}]{172c5c92-4254-4593-b741-1caa83a1e833-11_2486_1714_221_153}

5 Each path from \(S\) to \(T\) in the network below represents a possible way of using the internet to buy a ticket for a particular event. The number on each edge represents a charge, in pounds, with a negative value representing a discount. For example, the path SAEIT represents a ticket costing \(23 + 5 - 4 - 7 = 17\) pounds.
\includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-12_1023_1330_540_350}

1. By working backwards from \(\boldsymbol { T }\) and completing the table on Figure 4, use dynamic programming to find the minimum weight of all paths from \(S\) to \(T\).
2. State the minimum cost of a ticket for the event and the paths corresponding to this minimum cost.
   (3 marks)
3. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Stage	State	From	Value
   1	I	\(T\)	-7
   	\(J\)	\(T\)	-6
   	\(K\)	\(T\)	-5
   2	\(E\)	\(I\)	\(- 7 - 4 = - 11\)
   	F	I
   		\(J\)
   	G	I
   		\(J\)
   		\(K\)
   	\(H\)	\(K\)
   3

   \end{table}

6 A retail company has warehouses at \(P , Q\) and \(R\), and goods are to be transported to retail outlets at \(Y\) and \(Z\). There are also retaining depots at \(U , V , W\) and \(X\). The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram.
\includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}

1. On Figure 5 opposite, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
2. On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
3. 1. On Figure 7, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
4. Find a cut with value equal to the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
   \end{figure} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 6}

   Route	Flow
   SPUYT
   SRVWZT

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 7} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
   \end{figure}