OCR D2 (Decision Mathematics 2)

1. Whilst Clive is in hospital, four of his friends decide to redecorate his lounge as a welcomehome surprise. They divide the work to be done into four jobs which must be completed in the following order:

• strip the wallpaper,
• paint the woodwork and ceiling,
• hang the new wallpaper,
• replace the fittings and tidy up.

The table below shows the time, in hours, that each of the friends is likely to take to complete each job. As they do not know how long Clive will be in hospital his friends wish to complete the redecoration in the shortest possible total time.

1. Use the Hungarian method to obtain the optimal allocation of the jobs, showing the state of the table after each stage in the algorithm.
2. Hence find the minimum time in which the friends can redecorate the lounge.

2. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

1. Applying the dominance rule, explain, with justification, which strategy can be ignored by
   1. player \(A\),
   2. player \(B\).
2. For the reduced table, find the optimal strategy for
   1. player \(A\),
   2. player \(B\).

1. A sheet is provided for use in answering this question.

\begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the minimum and maximum capacity of that arc. \begin{figure}[h] \end{figure} Figure 2 shows a feasible flow through the same network.

1. Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.
   (6 marks)
2. Find a cut of the same value as your maximum flow and explain why this proves it gives the maximim possible flow.

4. Construct an activity network to show the tasks involved in widening a bridge over the B451.

1. Find those tasks which lie on the critical path and list them in order.
2. State the minimum length of time needed to widen the bridge.
3. Represent the tasks on a Gantt diagram. Tasks \(F\) and \(J\) each require 3 workers, tasks \(B\), \(D\) and \(I\) each require 2 workers and the remaining tasks each require one worker.
4. Draw a resource histogram showing how it is possible for a team of 4 workers to complete the project in the minimum possible time.

1. A company wishes to plan its production of a particular item over the coming four months based on its current orders. In each month the company can manufacture up to three of the item with the costs according to how many it makes being as follows:

There are no items in stock at the start of the period and the company wishes to meet all its orders on time and have no stock left at the end of the 4-month period. If any items are not to be supplied in the month they are made there is also a storage cost incurred of \(\pounds 400\) per item per month. The orders for each of the four months being considered are as follows: Use dynamic programming to find how many of the item the company should make in each of these four months in order to minimise the total cost for this period. \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1285_504_276}
\includegraphics[max width=\textwidth, alt={}, center]{df7b056f-1446-43f1-a2fd-c0d56533550e-6_588_1280_1361_276}