OCR D2 (Decision Mathematics 2)

The payoff matrix for player \(A\) in a two-person zero-sum game is shown below. \begin{array}{c|c|c|c|c} & & \multicolumn{3}{c}{B}
& & \text{I} & \text{II} & \text{III}
\hline \multirow{3}{*}{A} & \text{I} & -3 & 4 & 0
& \text{II} & 2 & 2 & 1
& \text{III} & 3 & -2 & -1
\end{array} Find the optimal strategy for each player and the value of the game. [4 marks]

Activity	Time	Precedence
A	5
B	20	A
C	3	A
D	7	A
E	4	B
F	15	C
G	6	C
H	17	D
I	10	F, G
J	2	G, H
K	6	E, I
L	9	I, J
M	3	K, L

Fig. 1 Construct an activity network Use appropriate forward and backward scanning to find

1. the minimum number of days needed to complete the entire project, [3 marks]
2. the activities which lie on the critical path. [3 marks]

[6 marks]

Arthur is planning a bus journey from town \(A\) to town \(L\). There are various routes he can take but he will have to change buses three times -- at \(B\), \(C\) or \(D\), at \(E\), \(F\), \(G\) or \(H\) and at \(I\), \(J\) or \(K\). \includegraphics{figure_2} Fig. 2 Figure 2 shows the bus routes that Arthur can use. The number on each arc shows the average waiting time, in minutes, for a bus to come on that route. As the forecast is for rain, Arthur wishes to plan his journey so that the total waiting time is as small as possible. Use dynamic programming to find the route that Arthur should use. [8 marks]

A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job: \begin{array}{c|c|c|c|c} & Windows & Conservatory & Doors & Greenhouse
\hline Team A & 27 & 80 & 8 & 81
Team B & 28 & 60 & 5 & 71
Team C & 30 & 90 & 7 & 73
\end{array} Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment. [10 marks]

The following matrix gives the capacities of the pipes in a system. \begin{array}{c|c|c|c|c|c|c|c} To & & S & T & A & B & C & D
From & & & & & & &
\hline S & & -- & -- & 16 & 26 & -- & --
T & & -- & -- & -- & -- & -- & --
A & & -- & -- & -- & -- & 13 & 5
B & & -- & 16 & -- & -- & -- & 11
C & & -- & 11 & -- & -- & -- & --
D & & -- & 11 & -- & -- & -- & --
\end{array}

1. Represent this information as a digraph. [3 marks]
2. Find the minimum cut, expressing it in the form \(\{\) \(\}|\{\) \(\}\), and state its value. [2 marks]
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
4. Explain how you know that this flow is maximal. [1 mark]

[11 marks]

The payoff matrix for player \(A\) in a two-person zero-sum game is shown below. \begin{array}{c|c|c|c|c} & & \multicolumn{3}{c}{B}
& & \text{I} & \text{II} & \text{III}
\hline \multirow{2}{*}{A} & \text{I} & -2 & 3 & -1
& \text{II} & 4 & -5 & 2
\end{array}

1. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\). [7 marks]
2. By solving this linear programming problem, find the optimal strategy for player \(B\) and the value of the game. [14 marks]

[21 marks]