OCR MEI D1 (Decision Mathematics 1) 2006 June

1 Answer this question on the insert provided. \begin{figure}[h] \end{figure}

1. Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D. Give your route and its weight.
2. Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.
   [0pt] [2]

2 Fig. 2.1 represents the two floors of a house. There are 5 rooms shown, plus a hall and a landing, which are to be regarded as separate rooms. Each " × " represents an internal doorway connecting two rooms. The " ⊗ " represents the staircase, connecting the hall and the landing. \begin{figure}[h] \end{figure}

1. Draw a graph representing this information, with vertices representing rooms, and arcs representing internal connections (doorways and the stairs). What is the name of the type of graph of which this is an example?
2. A larger house has 12 rooms on two floors, plus a hall and a landing. Each ground floor room has a single door, which leads to the hall. Each first floor room has a single door, which leads to the landing. There is a single staircase connecting the hall and the landing. How many arcs are there in the graph of this house?
3. Another house has 12 rooms on three floors, plus a hall, a first floor landing and a second floor landing. Again, each room has a single door on to the hall or a landing. There is one staircase from the hall to the first floor landing, and another staircase joining the two landings. How many arcs are there in the graph of this house?
4. Fig. 2.2 shows the graph of another two-floor house. It has 8 rooms plus a hall and a landing. There is a single staircase. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_208_666_1896_694} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Draw a possible floor plan, showing internal connections.

3 An incomplete algorithm is specified in Fig. 3.
\(\mathrm { f } ( \mathrm { x } ) = \mathrm { x } ^ { 2 } - 2\)
Initial values: \(\mathrm { L } = 0 , \mathrm { R } = 2\).
Step 1 Compute \(\mathrm { M } = \frac { \mathrm { L } + \mathrm { R } } { 2 }\).
Step 2 Compute \(\mathrm { f } ( \mathrm { M } )\).
Step 3 If \(\mathrm { f } ( \mathrm { M } ) < 0\) change the value of L to that of M .
Otherwise change the value of \(R\) to that of \(M\).
Step 4 Go to Step 1. \section*{Fig. 3}

1. Apply two iterations of the algorithm.
2. After 10 iterations \(\mathrm { L } = 1.414063 , \mathrm { R } = 1.416016 , \mathrm { M } = 1.416016\) and \(\mathrm { f } ( \mathrm { M } ) = 0.005100\). Say what the algorithm achieves.
3. Say what is needed to complete the algorithm.

4 Table 4.1 shows some of the activities involved in preparing for a meeting. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and the late event time for each vertex of your network, and list the critical activities.
3. Assuming that each activity requires one person and that each activity starts at its earliest start time, draw a resource histogram.
4. In fact although activity A has duration 1 hour, it actually involves only 0.5 hours work, since 0.5 hours involves waiting for replies. Given this information, and the fact that there is only one person available to do the work, what is the shortest time needed to prepare for the meeting? Fig. 4.2 shows an activity network for the tasks which have to be completed after the meeting. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-5_533_844_1688_294} \captionsetup{labelformat=empty} \caption{Fig. 4.2}
   \end{figure} P: Clean room
   Q: Prepare draft minutes
   R: Allocate action tasks
   S: Circulate draft minutes
   T: Approve task allocations
   U: Obtain budgets for tasks
   V: Post minutes
   W: Pay refreshments bill
5. Draw a precedence table for these activities.

5 John is reviewing his lifestyle, and in particular his leisure commitments. He enjoys badminton and squash, but is not sure whether he should persist with one or both. Both cost money and both take time. Playing badminton costs \(\pounds 3\) per hour and playing squash costs \(\pounds 4\) per hour. John has \(\pounds 11\) per week to spend on these activities. John takes 0.5 hours to recover from every hour of badminton and 0.75 hours to recover from every hour of squash. He has 5 hours in total available per week to play and recover.

1. Define appropriate variables and formulate two inequalities to model John's constraints.
2. Draw a graph to represent your inequalities. Give the coordinates of the vertices of your feasible region.
3. John is not sure how to define an objective function for his problem, but he says that he likes squash "twice as much" as badminton. Letting every hour of badminton be worth one "satisfaction point" define an objective function for John's problem, taking into account his "twice as much" statement.
4. Solve the resulting LP problem.
5. Given that badminton and squash courts are charged by the hour, explain why the solution to the LP is not a feasible solution to John's practical problem. Give the best feasible solution.
6. If instead John had said that he liked badminton more than squash, what would have been his best feasible solution?

6 Answer parts (ii)(A) and (iii)(B) of this question on the insert provided. A particular component of a machine sometimes fails. The probability of failure depends on the age of the component, as shown in Table 6. \section*{Table 6} You are to simulate six years of machine operation to estimate the probability of the component failing during that time. This will involve you using six 2-digit random numbers, one for each year.

1. Give a rule for using a 2-digit random number to simulate failure of the component in its first year of life. Similarly give rules for simulating failure during each of years 2 to 6 .
2. (A) Use your rules, together with the random numbers given in the insert, to complete the simulation table in the insert. This simulates 10 repetitions of six years operation of the machine. Start in the first column working down cell-by-cell. In each cell enter a tick if there is no simulated failure and a cross if there is a simulated failure. Stop and move on to the next column if a failure occurs.
   (B) Use your results to estimate the probability of a failure occurring. It is suggested that any component that has not failed during the first three years of its life should automatically be replaced.
3. (A) Describe how to simulate the operation of this policy.
   (B) Use the table in the insert to simulate 10 repetitions of the application of this policy. Re-use the same random numbers that are given in the insert.
   (C) Use your results to estimate the probability of a failure occurring.
4. How might the reliability of your estimates in parts (ii) and (iii) be improved?