OCR D2 (Decision Mathematics 2)

1. A linear programming problem is defined as follows:

$$\begin{array} { l l } \text { Maximise } & P = 3 x + 3 y + 4 z
\text { subject to } & x + 2 y + z \leq 30
& 5 x + y + 3 z \leq 60
\text { and } & x \geq 0 , y \geq 0 , z \geq 0 . \end{array}$$

1. Display the problem in a Simplex Tableau.
2. Starting with a pivot chosen from the \(z\)-column, perform one iteration of your tableau.
3. Write down the resulting values of \(x , y , z\) and \(P\) and state with a reason whether or not these values give an optimal solution.

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the maximum capacity of that arc. In addition to the restrictions on flow through the arcs a maximum flow of 6 units is allowed to pass through vertex \(C\).

1. Redraw the network to take into account this restriction.
2. Starting with an initial flow of 6 units along SADT and 6 units along SBT 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.

3. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below. Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.

4. A rally consisting of four stages is being planned. The first stage will begin at \(A\) and the last stage will end at \(L\). Various routes are being considered, with the end of one stage being the start of the next. The organisers want the total length of the route chosen to be as small as possible. The table below shows the length, in miles, of each of the possible stages. Use dynamic programming to find the route which satisfies the wish of the organisers.

1. A project involves six tasks, some of which cannot be started until others have been completed. This is shown in the table below.

1. Draw an activity network for this project.
2. By labelling your network, find the critical path and the minimum duration of the project. An extra condition is now imposed. Task \(A\) may not begin until task \(B\) has been underway for at least 10 minutes.
3. Draw a new network taking into account this restriction.
4. Find a revised value for the minimum duration of the project and state the new critical path.

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

1. Explain why the game does not have a saddle point.
2. Using a graphical method, find the optimal strategy for player \(B\).
3. Find the optimal strategy for player \(A\).
4. Find the value of the game.