OCR D2 (Decision Mathematics 2)

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

Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).

1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
2. Define your decision variables.
3. Write down the objective function in terms of your decision variables.
4. Write down the constraints.

2. The owner of a small plane is planning a journey from her local airport, \(A\) to the airport nearest her parents, \(K\). On the journey she will make three refuelling stops, the first at \(B , C\) or \(D\), the second at \(E , F\) or \(G\) and the third at \(H , I\) or \(J\). \begin{figure}[h] \end{figure} Figure 1 shows all the possible flights that can be made on the journey with the number by each arc indicating the distance of each flight in hundreds of miles. The owner of the plane wishes to choose a route that minimises the total distance that she flies. Use dynamic programming to find the route that she should use and state the total length of this route.

1. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below.

Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.

4.
\$ FMMUMITI7 IP HIZ3 UFHGHQFHIT
ா\$ மோங்கோ
ா\%\%mmum
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_268_424_301}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_46_465_482_301}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_533_539_301}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_472_593_303}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_497_648_303}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_54_501_703_306}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_45_467_762_303}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_49_463_813_303}
\includegraphics[max width=\textwidth, alt={}, center]{34728928-2a21-463d-982e-c46ab2dc05c8-4_47_460_872_303}
\(\square\)
\(\square\) Fig. 2
Construct an activity network to model the work involved in laying the foundations and putting in services for an industrial complex.

1. Execute a forward scan to find the minimum time in which the project can be completed.
2. Execute a backward scan to determine which activities lie on the critical path. The contractor is committed to completing the project in this minimum time and faces a penalty of \(\pounds 50000\) for each day that the project is late. Unfortunately, before any work has begun, flooding means that activity \(E\) will take 3 days longer than the 7 days allocated.
3. Activity \(K\) could be completed in 1 day at an extra cost of \(\pounds 90000\). Explain why doing this is not economical.
   (2 marks)
4. If the time taken to complete any one activity, other than \(E\), could be reduced by 2 days at an extra cost of \(\pounds 80000\), for which activities on their own would this be profitable. Explain your reasoning.
   (3 marks)
   11 marks

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

A town has adopted a one-way system to cope with recent problems associated with congestion in one area. \begin{figure}[h] \end{figure} Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.

1. Find the capacity of the cut which passes through the \(\operatorname { arcs } A E , B F , B G\) and \(C D\).
   (1 mark) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{34728928-2a21-463d-982e-c46ab2dc05c8-6_714_1280_171_333} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure} Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, \(S\), and a supersink, \(T\), have been used.
2. 1. Use the labelling procedure to find the maximum flow through this network listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. Prove that your flow is the maximum possible through the network.
4. It is suggested that the maximum flow through the network could be increased by making road \(E F\) undirected, so that it has a capacity of 8 in either direction. Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.