\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline
\end{tabular}
\end{center}
Route Matrix
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 3 | 2 | 3 | 3 |
| \(\mathbf { 2 }\) | 1 | 1 | 3 | 3 |
| \(\mathbf { 3 }\) | 1 | 2 | 1 | 4 |
| \(\mathbf { 4 }\) | 3 | 3 | 3 | 3 |
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.
4772
Decision Mathematics 2
\section*{Candidates answer on the Answer Booklet}
\section*{OCR Supplied Materials:}
- Answer Booklet (8 pages)
- Graph paper
- MEI Examination Formulae and Tables (MF2)
\section*{Other Materials Required:}
None
\section*{Wednesday 17 June 2009
Morning}
Duration: 1 hour 30 minutes
|||||||||||||||||||||||
- Write your name clearly in capital letters, your Centre Number and Candidate Number in the spaces provided on the Answer Booklet.
- Use black ink. Pencil may be used for graphs and diagrams only.
- Read each question carefully and make sure that you know what you have to do before starting your answer.
- Answer all the questions.
- You are permitted to use a graphical calculator in this paper.
- Final answers should be given to a degree of accuracy appropriate to the context.
- Do not write in the bar codes.
- The number of marks is given in brackets [ ] at the end of each question or part question.
- You are advised that an answer may receive no marks unless you show sufficient detail of the working to indicate that a correct method is being used.
- The total number of marks for this paper is 72.
- This document consists of \(\mathbf { 4 }\) pages. Any blank pages are indicated.
1 (a) The following was said in a charity appeal on Radio 4 in October 2006.
"It is hard to underestimate the effect that your contribution will make."
Rewrite the comment more simply in your own words without changing its meaning.
(b) A machine has three components, A, B and C, each of which is either active or inactive.
- The machine is active if A and B are both active.
- The machine is active if A is inactive and C is active.
- The machine is active if B is inactive and C is active.
- Otherwise the machine is inactive.
The states (active or inactive) of the components and the machine are to be modelled by a combinatorial circuit in which "active" is represented by "true" and "inactive" is represented by "false".
Draw such a circuit.
(c) Construct a truth table to show the following.
$$[ ( ( \mathrm { a } \wedge \mathrm {~b} ) \vee ( ( \sim \mathrm { a } ) \wedge \mathrm { c } ) ) \vee ( ( \sim \mathrm { b } ) \wedge \mathrm { c } ) ] \Leftrightarrow \sim [ ( ( \sim \mathrm { a } ) \wedge ( \sim \mathrm { c } ) ) \vee ( ( \sim \mathrm { b } ) \wedge ( \sim \mathrm { c } ) ) ]$$
2 Zoe is preparing for a Decision Maths test on two topics, Decision Analysis (D) and Simplex (S). She has to decide whether to devote her final revision session to D or to S .
There will be two questions in the test, one on D and one on S . One will be worth 60 marks and the other will be worth 40 marks. Historically there is a \(50 \%\) chance of each possibility.
Zoe is better at \(D\) than at \(S\). If her final revision session is on \(D\) then she would expect to score \(80 \%\) of the \(D\) marks and \(50 \%\) of the \(S\) marks. If her final session is on \(S\) then she would expect to score \(70 \%\) of the S marks and \(60 \%\) of the D marks.
(i) Compute Zoe's expected mark under each of the four possible circumstances, i.e. Zoe revising \(D\) and the D question being worth 60 marks, etc.
(ii) Draw a decision tree for Zoe.
Michael claims some expertise in forecasting which question will be worth 60 marks. When he forecasts that it will be the D question which is worth 60 , then there is a \(70 \%\) chance that the D question will be worth 60 . Similarly, when he forecasts that it will be the S question which is worth 60 , then there is a \(70 \%\) chance that the S question will be worth 60 . He is equally likely to forecast that the D or the S question will be worth 60.
(iii) Draw a decision tree to find the worth to Zoe of Michael's advice.
3 A farmer has 40 acres of land. Four crops, A, B, C and D are available.
Crop A will return a profit of \(\pounds 50\) per acre. Crop B will return a profit of \(\pounds 40\) per acre.
Crop C will return a profit of \(\pounds 40\) per acre. Crop D will return a profit of \(\pounds 30\) per acre.
The total number of acres used for crops A and B must not be greater than the total number used for crops C and D.
The farmer formulates this problem as:
Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
subject to \(\quad a + b \leqslant 20\),
\(a + b + c + d \leqslant 40\).
(i) Explain what the variables \(a , b , c\) and \(d\) represent.
Explain how the first inequality was obtained.
Explain why expressing the constraint on the total area of land as an inequality will lead to a solution in which all of the land is used.
(ii) Solve the problem using the simplex algorithm.
Suppose now that the farmer had formulated the problem as:
Maximise \(\quad 50 a + 40 b + 40 c + 30 d\),
subject to \(\quad a + b \leqslant 20\),
\(a + b + c + d = 40\).
(iii) Show how to adapt this problem for solution either by the two-stage simplex method or the big-M method. In either case you should show the initial tableau and describe what has to be done next. You should not attempt to solve the problem.
4 The diagram shows routes connecting five cities. Lengths are in km .
\includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-21_442_995_319_534}
(i) Produce the initial matrices for an application of Floyd's algorithm to find the complete network of shortest distances between the five cities.
The following are the distance and route matrices after the third iteration of Floyd's algorithm.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) & \(\mathbf { 5 }\)
\hline
\(\mathbf { 1 }\) & 44 & 22 & 42 & 15 & 15
\hline
\(\mathbf { 2 }\) & 22 & 44 & 20 & 5 & 23
\hline
\(\mathbf { 3 }\) & 42 & 20 & 40 & 25 & 43
\hline
\(\mathbf { 4 }\) & 15 & 5 & 25 & 10 & 16
\hline