OCR MEI D2 (Decision Mathematics 2) 2008 June

1

1. The Plain English Society presents an annual "Foot in Mouth" award for "a truly baffling comment". In 2004 it was presented to Boris Johnson MP for a comment on the \(12 ^ { \text {th } }\) December 2003 edition of "Have I Got News For You":
   "I could not fail to disagree with you less."
   1. Explain why this can be rewritten as:
      "I could succeed in agreeing with you more."
   2. Rewrite the comment more simply in your own words without changing its meaning.
2. Two switches are to be wired between a mains electricity supply and a light so that when the state of either switch is changed the state of the light changes (i.e. from off to on, or from on to off). Draw a switching circuit to achieve this. The switches are both 2-way switches, thus:
   \includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-2_127_220_895_1054}
3. Construct a truth table to show the following. $$[ ( a \wedge b ) \vee ( ( \sim a ) \wedge ( \sim b ) ) ] \Leftrightarrow [ ( ( \sim a ) \vee b ) \wedge ( a \vee ( \sim b ) ) ]$$

2 Jane has a house on a Mediterranean island. She spends eight weeks a year there, either visiting twice for four weeks each trip or four times for two weeks each trip. Jane is wondering whether it is best for her to fly out and rent a car, or to drive out.
Flights cost \(\pounds 500\) return and car rental costs \(\pounds 150\) per week.
Driving out costs \(\pounds 900\) for ferries, road tolls, fuel and overnight expenses.

1. Draw a decision tree to model this situation. Advise Jane on the cheapest option. As an alternative Jane considers buying a car to keep at the house. This is a long-term alternative, and she decides to cost it over 10 years. She has to cost the purchase of the car and her flights, and compare this with the other two options. In her costing exercise she decides that she will not be tied to two trips per year nor to four trips per year, but to model this as a random process in which she is equally likely to do either.
2. Draw a decision tree to model this situation. Advise Jane on how much she could spend on a car using the EMV criterion.
3. Explain what is meant by "the EMV criterion" and state an alternative approach.

3 The weights on the network represent distances.
\includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-3_401_702_315_683}

1. 1. Apply Floyd's algorithm to the network to find the complete network of shortest distances, showing that the final 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 }\) & 22 & 14 & 11 & 23
      \hline \(\mathbf { 2 }\) & 14 & 28 & 15 & 27
      \hline \(\mathbf { 3 }\) & 11 & 15 & 22 & 12
      \hline

\(\mathbf { 4 }\) & 23 & 27 & 12 & 24
\hline \end{tabular} \end{center} Draw the complete network of shortest distances.
(ii) Starting at vertex 1, apply the nearest neighbour algorithm to the complete network of shortest distances to find a Hamilton cycle. Give the length of your cycle and interpret it in the original network.
(iii) By temporarily deleting vertex \(\mathbf { 1 }\) and its connecting arcs from the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson's Problem in that network. Say what this implies in the original network.
(b) Solve the route inspection problem in the original network, and say how you can be sure that your solution is optimal. 4 A factory's output includes three products. To manufacture a tonne of product \(\mathrm { A } , 3\) tonnes of water are needed. Product B needs 2 tonnes of water per tonne produced, and product C needs 5 tonnes of water per tonne produced. Product A uses 5 hours of labour per tonne produced, product B uses 6 hours and product C uses 2 hours. There are 60 tonnes of water and 50 hours of labour available for tomorrow's production.
(i) Formulate a linear programming problem to maximise production within the given constraints.
(ii) Use the simplex algorithm to solve your LP, pivoting first on your column relating to product C.
(iii) An extra constraint is imposed by a contract to supply at least 8 tonnes of A . Use either two stage simplex or the big M method to solve this revised problem.