OCR MEI D1 (Decision Mathematics 1) 2013 January

1 The weights on the arcs in the network represent times in minutes to travel between vertices.
\includegraphics[max width=\textwidth, alt={}, center]{d1e0f047-6484-435b-a685-2cbbf81a6b02-2_606_782_402_628}

1. Use Dijkstra's algorithm to find the fastest route from A to F . Give the route and the time.
2. Use an algorithm to find the minimum connector for the network, showing your working. Find the minimum time to travel from A to F using only arcs in the minimum connector.

2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.

1. Name the type of graph which is appropriate.
2. What is the maximum possible number of arcs in the graph? Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men. Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy. The three ugly sisters only have one dance each.
3. Add arcs to the graph in your answer book to show this information.
4. What is the maximum possible number of arcs in the graph?

3 The following algorithm computes an estimate of the square root of a number which is between 0 and 2.
Step 1 Subtract 1 from the number and call the result \(x\)
Step 2 Set oldr = 1
Step 3 Set \(i = 1\)
Step 4 Set \(j = 0.5\)
Step 5 Set \(k = 0.5\)
Step 6 Set change \(= x ^ { i } \times k\)
Step 7 Set newr \(=\) oldr + change
Step 8 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 9 Set oldr = newr
Step 10 Set \(i = i + 1\)
Step 11 Set \(j = j - 1\)
Step 12 Set \(k = k \times j \div i\)
Step 13 Set change \(= x ^ { i } \times k\)
Step 14 Set newr \(=\) oldr + change
Step 15 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 16 Go to Step 9
Step 17 Print out newr

1. Use the algorithm to find an estimate of the square root of 1.44 , showing all of the steps.
2. Consider what happens if the algorithm is applied to 0.56 , and then use your four values of change from part (i) to calculate an estimate of the square root of 0.56 .

4 A room has two windows which have the same height but different widths. Each window is to have one curtain. The table lists the tasks involved in making the two curtains, their durations, and their immediate predecessors. The durations assume that only one person is working on the activity.

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. Kate and Pete have two rooms to curtain, each identical to that above. Tasks A, B, C and D only need to be completed once each. All other tasks will have two versions, one for room 1 and one for room 2, eg E1 and E2. Kate and Pete share the tasks between them so that each task is completed by only one person.
3. Complete the diagram to show how the tasks can be shared between them, and scheduled, so that the project can be completed in the least possible time. Give that least possible time.
4. How much extra help would be needed to curtain both rooms in the minimum completion time from part (ii)? Explain your answer.

5 A chairlift for a ski slope has 160 4-person chairs. At any one time half of the chairs are going up and half are coming down empty. An observer watches the loading of the chairs during a moderately busy period, and concludes that the number of occupants per 'up' chair has the following probability distribution.

1. Give a rule for using 1-digit random numbers to simulate the number of occupants of an up chair in a moderately busy period.
2. Use the 10 random digits provided to simulate the number of occupants in 10 up chairs. The observer estimates that, at all times, on average \(20 \%\) of chairlift users are children.
3. Give an efficient rule for using 1-digit random numbers to simulate whether an occupant of an up chair is a child or an adult.
4. Use the random digits provided to simulate how many of the occupants of the 10 up chairs are children, and how many are adults. There are more random digits than you will need.
5. Use your results from part (iv) to estimate how many children and how many adults are on the chairlift (ie on the 80 up chairs) at any instant during a moderately busy period. In a very busy period the number of occupants of an up chair has the following probability distribution.

   number of occupants	0	1	2	3	4
   probability	\(\frac { 1 } { 13 }\)	\(\frac { 1 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 3 } { 13 }\)	\(\frac { 5 } { 13 }\)

6. Give an efficient rule for using 2-digit random numbers to simulate the number of occupants of an up chair in a very busy period.
7. Use the 2-digit random numbers provided to simulate the number of occupants in 5 up chairs. There are more random numbers provided than you will need.
8. Simulate how many of the occupants of the 5 up chairs are children and how many are adults, and thus estimate how many children and how many adults are on the chairlift at any instant during a very busy period.
9. Discuss the relative merits of simulating using a sample of 10 chairs as against simulating using a sample of 5 chairs.

6 Jean knits items for charity. Each month the charity provides her with 75 balls of wool.
She knits hats and scarves. Hats require 1.5 balls of wool each and scarves require 3 balls each. Jean has 100 hours available each month for knitting. Hats require 4 hours each to make, and scarves require 2.5 hours each. The charity sells the hats for \(\pounds 7\) each and the scarves for \(\pounds 10\) each, and wants to gain as much income as possible. Jean prefers to knit hats but the charity wants no more than 20 per month. She refuses to knit more than 20 scarves each month.

1. Define appropriate variables, construct inequality constraints, and draw a graph representing the feasible region for this decision problem.
2. Give the objective function and find the integer solution which will give Jean's maximum monthly income.
3. If the charity drops the price of hats in a sale to \(\pounds 4\) each, what would be an optimal number of hats and scarves for Jean to knit? Assuming that all hats and scarves are sold, by how much would the monthly income drop?