OCR MEI D1 (Decision Mathematics 1) 2012 June

1 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.

2 This question concerns the following algorithm which operates on a given function, f. The algorithm finds a point between A and B at which the function has a minimum, with a maximum error of 0.05 .

1. Working correct to three decimal places, perform two iterations of the algorithm for \(\mathrm { f } ( x ) = 2 x ^ { 2 } - 15 x + 30\), when \(\mathrm { A } = 3\) and \(\mathrm { B } = 4\). Start at Step 1 and stop when you reach Step 8 for the second time.
2. The \(\left( \frac { \sqrt { 5 } - 1 } { 2 } \right)\) factor in Step 3 ensures that either the new ' \(L\) ' is equal to the old ' \(R\) ', or vice versa. Why is this important?
3. This algorithm is used when the function is not known explicitly, but where its value can be found for any given input. Give a practical example of where it might be used.

3 The diagram shows three sets, A, B and C. Each region of the diagram contains at least one element. The diagram shows that B is a subset of \(\mathrm { A } , \mathrm { C }\) is a subset of A , and that B shares at least one element with C .
\includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_410_615_342_726} The two graphs below give information about the three sets \(\mathrm { A } , \mathrm { B }\) and C . The first graph shows the relation 'is a subset of' and the second graph shows the relation 'shares at least one element with'. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw two graphs to represent the sets \(\mathrm { X } , \mathrm { Y }\) and Z shown in the following diagram.
   \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_415_613_1388_731}
2. Draw a diagram to represent the sets \(\mathrm { P } , \mathrm { Q }\) and R for which both of the following graphs apply. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_202_264_1980_621} \captionsetup{labelformat=empty} \caption{'is a subset of'}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_200_260_1982_1155} \captionsetup{labelformat=empty} \caption{'shares at least one element with'}
   \end{figure}

4 In a factory, two types of motor are made. Each motor of type X takes 10 man hours to make and each motor of type Y takes 12 man hours to make. In each week there are 200 man hours available. To satisfy customer demand, at least 5 of each type of motor must be made each week.
Once a motor has been started it must be completed; no unfinished motors may be left in the factory at the end of each week. When completed, the motors are put into a container for shipping. The volume of the container is \(7 \mathrm {~m} ^ { 3 }\). A type X motor occupies a volume of \(0.5 \mathrm {~m} ^ { 3 }\) and a type Y motor occupies a volume of \(0.3 \mathrm {~m} ^ { 3 }\).

1. Define appropriate variables and from the above information derive four inequalities which must be satisfied by those variables.
2. Represent your inequalities on a graph and shade the infeasible region. The profit on each type X is \(\pounds 100\) and on each type Y is \(\pounds 70\).
3. The weekly profit is to be maximised. Write down the objective function and find the maximum profit.
4. Because of absenteeism, the manager decides to organise the work in the factory on the assumption that there will be only 180 man hours available each week. Find the number of motors of each type that should now be made in order to maximise the profit.

5 Each morning I reach into my box of tea bags and, without looking, randomly choose a bag. The bags are manufactured in pairs, which can be separated along a perforated line. So when I choose a bag it might be attached to another, in which case I have to separate them and return the other bag to the box. Alternatively, it might be a single bag, having been separated on an earlier day. I only use one tea bag per day, and the box always gets thoroughly shaken during the day as things are moved around in the kitchen. You are to simulate this process, starting with 5 double bags and 0 single bags in the box. You are to use single-digit random numbers in your simulation.

1. On day 2 there will be 4 double bags and 1 single bag in the box, 9 bags in total. Give a rule for simulating whether I choose a single bag or a double bag, assuming that I am equally likely to choose any of the 9 bags. Use single-digit random numbers in your simulation rule.
2. On day 3 there will either be 4 double bags or 3 double bags and 2 single bags in the box. Give a rule for simulating what sort of bag I choose in the second of these cases. Use single-digit random numbers in your simulation rule.
3. Using the random digits in your answer book, simulate what happens on days 2,3 and 4 , briefly explaining your simulations. Give an estimate of the probability that I choose a single bag on day 5 .
4. Using the random digits in your answer book, carry out 4 more simulations and record the results.
5. Using your 5 simulations, estimate the probability that I choose a single bag on day 5 .
   [0pt] [Question 6 is printed overleaf.]

6 The table shows the tasks involved in making a batch of buns, the time in minutes required for each task, and their precedences.

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. Preparing the batch for baking consists of tasks A to G ; each of these tasks can only be done by one person. Baking, task H, requires no people.
3. How many people are required to prepare the batch for baking in the minimum time?
4. What is the minimum time required to prepare the batch for baking if only one person is available? Jim is preparing and baking three batches of buns. He has one oven available for baking. For the rest of the question you should consider 'preparing the batch for baking' as one activity.
5. Assuming that the oven can bake only one batch at a time, draw an activity on arc diagram for this situation and give the minimum time in which the three batches of buns can be prepared and baked.
6. Assuming that the oven is big enough to bake all three batches of buns at the same time, give the minimum time in which the three batches of buns can be prepared and baked.