OCR D2 (Decision Mathematics 2)

1. \begin{figure}[h] \end{figure} A salesman is planning a four-day trip beginning at his home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 1 shows the distances, in tens of miles, that he will drive each day according to the route he chooses. Use dynamic programming to find the shortest route the salesman can take and state the distance he will drive in total using this route.

2. Four athletes are put forward for selection for a mixed stage relay race at a local competition. They may each be selected for a maximum of one stage and only one athlete can be entered for each stage. The average time, in seconds, for each athlete to complete each stage is given below, based on past performances. Use the Hungarian algorithm to find an optimal allocation which will minimise the team's total time. Your answer should show clearly how you have applied the algorithm.

3. A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.

1. Draw an activity network for the project.
2. Find the critical path and the minimum time in which the project can be completed. Activity \(F\) can be carried out more cheaply if it is allocated more time.
3. Find the maximum time that can be allocated to activity \(F\) without increasing the minimum time in which the project can be completed.

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

\begin{figure}[h] \end{figure} Figure 2 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. Calculate the values of cuts \(C _ { 1 }\) and \(C _ { 2 }\).
2. Find the minimum cut and state its value. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_645_1316_1430_338} \captionsetup{labelformat=empty} \caption{Fig. 3}
   \end{figure} Figure 3 shows a feasible flow through the same network.
3. State the values of \(x , y\) and \(z\).
4. 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. State how you know that you have found a maximal flow.

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

1. Using a graphical method, find the optimal strategy for player \(X\).
2. Find the optimal strategy for player \(Y\).
3. Find the value of the game.