OCR D2 (Decision Mathematics 2)

1. A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue.

\begin{figure}[h] \end{figure} The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day. Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.

2. A two-person zero-sum game is represented by the payoff matrix for player \(A\) shown below.

1. Represent the expected payoffs to \(A\) against \(B\) 's strategies graphically and hence determine which strategy is not worth considering for player \(B\).
2. Find the best strategy for player \(A\) and the value of the game.

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.

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

\begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
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. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.

5. A leisure company owns boats of each of the following types: 2-person boats which are 4 metres long and weigh 50 kg .
4-person boats which are 3 metres long and weigh 20 kg .
8-person boats which are 14 metres long and weigh 100 kg .
The leisure company is willing to donate boats to a local sports club to accommodate up to 40 people at any one time. However, storage facilities mean that the combined length of the boats must not be more than 75 metres. Also, it must be possible to transport all the boats on a single trailer which has a maximum load capacity of 600 kg . The club intends to hire the boats out to help with the cost of maintaining them. It plans to charge \(\pounds 10 , \pounds 12\) and \(\pounds 8\) per day, for the 2 -, 4 - and 8 -person boats respectively and wishes to maximise its daily revenue ( \(\pounds R\) ). Let \(x , y\) and \(z\) represent the number of 2-, 4- and 8-person boats respectively given to the club.

1. Model this as a linear programming problem. Using the Simplex algorithm the following initial tableau is obtained:

   \(R\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)
   1	\({ } ^ { - } 10\)	\({ } ^ { - } 12\)	\({ } ^ { - } 8\)	0	0	0	0
   0	1	2	4	1	0	0	20
   0	4	3	14	0	1	0	75
   0	5	2	10	0	0	1	60

2. Explain the purpose of the variables \(s , t\) and \(u\).
3. By increasing the value of \(y\) first, work out the next two complete tableaus.
4. Explain how you know that your final tableau gives an optimal solution and state this solution in practical terms.

1. A project consists of the activities listed in the table below. For each activity the table shows how long it will take, which other activites must be completed before it can be done and the number of workers needed to complete it.

1. Draw an activity network for the project.
2. Find the critical path and the minimum time in which the project can be completed.
3. Represent all of the activities on a Gantt diagram.
4. By drawing a resource histogram, find out the maximum number of workers required at any one time if each activity is begun as soon as possible.
5. Draw another resource histogram to show how the project can be completed in the minimum time possible using a maximum of 10 workers at any one time. Sheet for answering question 4 \section*{Please hand this sheet in for marking} \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_729_1227_482_338}
   \includegraphics[max width=\textwidth, alt={}, center]{b8eb80d5-5af5-4a8b-8335-6fae95f3aa73-6_723_1223_1466_338}