OCR MEI D2 (Decision Mathematics 2) 2007 June

1

1. A joke has it that army recruits used to be instructed: "If it moves, salute it. If it doesn't move, paint it." Assume that this instruction has been carried out completely in the local universe, so that everything that doesn't move has been painted.
   1. A recruit encounters something which is not painted. What should he do, and why?
   2. A recruit encounters something which is painted. Do we know what he or she should do? Justify your answer.
2. Use a truth table to prove \(( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s\).
3. You are given the following two rules. $$\begin{aligned} & 1 \quad ( a \Rightarrow b ) \Leftrightarrow ( \sim b \Rightarrow \sim a )
   & 2 \quad ( x \wedge ( x \Rightarrow y ) ) \Rightarrow y \end{aligned}$$ Use Boolean algebra to prove that \(( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s\).

2 Bill is at a horse race meeting. He has \(\pounds 2\) left with two races to go. He only ever bets \(\pounds 1\) at a time. For each race he chooses a horse and then decides whether or not to bet on it. In both races Bill's horse is offered at "evens". This means that, if Bill bets \(\pounds 1\) and the horse wins, then Bill will receive back his \(\pounds 1\) plus \(\pounds 1\) winnings. If Bill's horse does not win then Bill will lose his \(\pounds 1\).

1. Draw a decision tree to model this situation. Show Bill's payoffs on your tree, i.e. how much money Bill finishes with under each possible outcome. Assume that in each race the probability of Bill's horse winning is the same, and that it has value \(p\).
2. Find Bill's EMV when
   (A) \(p = 0.6\),
   (B) \(p = 0.4\). Give his best course of action in each case.
3. Suppose that Bill uses the utility function utility \(= ( \text { money } ) ^ { x }\), to decide whether or not to bet \(\pounds 1\) on one race. Show that, with \(p = 0.4\), Bill will not bet if \(x = 0.5\), but will bet if \(x = 1.5\).

3 Floyd's algorithm is applied to the following network:
\includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows: \begin{center} \begin{tabular}{ | c | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\)
\hline \(\mathbf { 1 }\) & 6 & 3 & 10 & 5
\hline \(\mathbf { 2 }\) & 3 & 6 & 7 & 2
\hline \(\mathbf { 3 }\) & 10 & 7 & 14 & 1
\hline

\(\mathbf { 4 }\) & 5 & 2 & 1 & 2
\hline \end{tabular} \end{center}

1. Perform the fourth (final) iteration of the algorithm.
2. Explain how to use the final matrices to find the shortest distance and the shortest route from vertex \(\mathbf { 1 }\) to vertex \(\mathbf { 3 }\), and give the distance and route.
3. Draw the complete network of shortest distances.
4. Apply the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.
5. By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.
6. Explain what you can deduce from your answers to parts (iv) and (v). 4 Noel is designing a hotel patio. It will consist of decking and paving.
   Decking costs \(\pounds 4\) per \(\mathrm { m } ^ { 2 }\) and paving costs \(\pounds 2\) per \(\mathrm { m } ^ { 2 }\). He has a budget of \(\pounds 2500\).
   Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking. He wants to have as large a patio as possible.
   Noel's problem is formulated as the following LP.
   Let \(x\) be the number of \(\mathrm { m } ^ { 2 }\) of decking.
   Let \(y\) be the number of \(\mathrm { m } ^ { 2 }\) of paving. $$\begin{aligned} \text { Maximise } \quad P & = x + y
   \text { subject to } 2 x + y & \leqslant 1250
   2 x - y & \leqslant 0
   x & \geqslant 0
   y & \geqslant 0 \end{aligned}$$
7. Use the simplex algorithm to solve this LP. Pivot first on the positive element in the \(y\) column. Noel would like to have at least \(200 \mathrm {~m} ^ { 2 }\) of decking.
8. Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem. Noel finally decides that he will minimise the annual cost of maintenance, which is given by \(\pounds ( 0.75 x + 1.25 y )\), subject to the additional constraint that there is at least \(1000 \mathrm {~m} ^ { 2 }\) of patio.
9. Starting from your solution to part (ii), use simplex to solve this problem.