OCR MEI D1 (Decision Mathematics 1) 2009 January

1 Alfred, Ben, Charles and David meet, and some handshaking takes place.

• Alfred shakes hands with David.
• Ben shakes hands with Charles and David.
• Charles shakes hands with Ben and David.
  1. Complete the bipartite graph in your answer book showing A (Alfred), B (Ben), C (Charles) and D (David), and the number of people each shakes hands with.
  2. Explain why, whatever handshaking takes place, the resulting bipartite graph cannot contain both an arc terminating at 0 and another arc terminating at 3 .
  3. Explain why, whatever number of people meet, and whatever handshaking takes place, there must always be two people who shake hands with the same number of people.

2 The following algorithm computes the number of comparisons made when Prim’s algorithm is applied to a complete network on \(n\) vertices ( \(n > 2\) ). Step 1 Input the value of \(n\)
Step 2 Let \(i = 1\)
Step 3 Let \(j = n - 2\)
Step 4 Let \(k = j\)
Step 5 Let \(i = i + 1\)
Step 6 Let \(j = j - 1\)
Step 7 Let \(k = k + ( i \times j ) + ( i - 1 )\)
Step 8 If \(j > 0\) then go to Step 5
Step 9 Print \(k\)
Step 10 Stop

1. Apply the algorithm when \(n = 5\), showing the intermediate values of \(i , j\) and \(k\). The function \(\mathrm { f } ( n ) = \frac { 1 } { 6 } n ^ { 3 } - \frac { 7 } { 6 } n + 1\) gives the same output as the algorithm.
2. Showing your working, check that \(\mathrm { f } ( 5 )\) is the same value as your answer to part (i).
3. What does the structure of \(\mathrm { f } ( n )\) tell you about Prim's algorithm?

3 Whilst waiting for her meal to be served, Alice tries to construct a network to represent the meals offered in the restaurant.
\includegraphics[max width=\textwidth, alt={}, center]{9bb2d545-3764-4930-a8a8-9dc5e25d0836-3_684_1310_365_379}

1. Use Dijkstra's algorithm to find the cheapest route through the undirected network from "start" to "end". Give the cost and describe the route. Use the lettering given on the network in your answer book.
2. Criticise the model and suggest how it might be improved.

4 A ski-lift gondola can carry 4 people. The weight restriction sign in the gondola says "4 people - 325 kg ". The table models the distribution of weights of people using the gondola.

1. Give an efficient rule for using 2-digit random numbers to simulate the weight of a person entering the gondola.
2. Give a reason for using 2-digit rather than 1-digit random numbers in these circumstances.
3. Using the random numbers given in your answer book, simulate the weights of four people entering the gondola, and hence give its simulated load.
4. Using the random numbers given in your answer book, repeat your simulation 9 further times. Hence estimate the probability of the load of a fully-laden gondola exceeding 325 kg .
5. What in reality might affect the pattern of loading of a gondola which is not modelled by your simulation?

5 The tasks involved in turning around an "AirGB" aircraft for its return flight are listed in the table. The table gives the durations of the tasks and their immediate predecessors.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Because of delays on the outbound flight the aircraft has to be turned around within 50 minutes, so as not to lose its air traffic slot for the return journey. There are four tasks on which time can be saved. These, together with associated costs, are listed below.

   Task	A	B	D	E
   New time (mins)	20	20	15	15
   Extra cost	250	50	50	100

3. List the activities which need to be speeded up in order to turn the aircraft around within 50 minutes at minimum extra cost. Give the extra cost and the new set of critical activities.

6 A company is planning its production of "MPowder" for the next three months.

• Over the next 3 months 20 tonnes must be produced.
• Production quantities must not be decreasing. The amount produced in month 2 cannot be less than the amount produced in month 1 , and the amount produced in month 3 cannot be less than the amount produced in month 2.
• No more than 12 tonnes can be produced in total in months 1 and 2.
• Production costs are \(\pounds 2000\) per tonne in month \(1 , \pounds 2200\) per tonne in month 2 and \(\pounds 2500\) per tonne in month 3.

The company planner starts to formulate an LP to find a production plan which minimises the cost of production: $$\begin{array} { l l } \text { Minimise } & 2000 x _ { 1 } + 2200 x _ { 2 } + 2500 x _ { 3 }
\text { subject to } & x _ { 1 } \geq 0 x _ { 2 } \geq 0 x _ { 3 } \geq 0
& x _ { 1 } + x _ { 2 } + x _ { 3 } = 20
& x _ { 1 } \leq x _ { 2 }
& \bullet \cdot \cdot \end{array}$$

1. Explain what the variables \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\) represent, and write down two more constraints to complete the formulation.
2. Explain how the LP can be reformulated to: $$\begin{array} { l l } \text { Maximise } & 500 x _ { 1 } + 300 x _ { 2 }
   \text { subject to } & x _ { 1 } \geq 0 x _ { 2 } \geq 0
   & x _ { 1 } \leq x _ { 2 }
   & x _ { 1 } + 2 x _ { 2 } \leq 20
   & x _ { 1 } + x _ { 2 } \leq 12 \end{array}$$
3. Use a graphical approach to solve the LP in part (ii). Interpret your solution in terms of the company's production plan, and give the minimum cost.