OCR MEI D2 (Decision Mathematics 2)

1 The switching circuit in Fig. 1.1 shows switches, \(s\) for a car's sidelights, \(h\) for its dipped headlights and f for its high-intensity rear foglights. It also shows the three sets of lights. \begin{figure}[h] \end{figure} (Note: \(s\) and \(h\) are each "ganged" switches. A ganged switch consists of two connected switches sharing a single switch control, so that both are either on or off together.)

1. 1. Describe in words the conditions under which the foglights will come on. Fig. 1.2 shows a combinatorial circuit. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{83d00f1f-25e5-4a26-bac5-dc2baf965438-02_367_1235_1183_431} \captionsetup{labelformat=empty} \caption{Fig. 1.2}
      \end{figure}
   2. Write the output in terms of a Boolean expression involving \(s , h\) and \(f\).
   3. Use a truth table to prove that \(\mathrm { s } \wedge \mathrm { h } \wedge \mathrm { f } = \sim ( \sim \mathrm { s } \vee \sim \mathrm { h } ) \wedge \mathrm { f }\).
2. A car's first gear can be engaged ( g ) if either both the road speed is low ( r ) and the clutch is depressed ( d ), or if both the road speed is low ( r ) and the engine speed is the correct multiple of the road speed (m).
   1. Draw a switching circuit to represent the conditions under which first gear can be engaged. Use two ganged switches to represent \(r\), and single switches to represent each of \(\mathrm { d } , \mathrm { m }\) and g .
   2. Draw a combinatorial circuit to represent the Boolean expression \(\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g }\).
   3. Use Boolean algebra to prove that \(\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g } = ( ( \mathrm { r } \wedge \mathrm { d } ) \vee ( \mathrm { r } \wedge \mathrm { m } ) ) \wedge \mathrm { g }\).
   4. Draw another switching circuit to represent the conditions under which first gear can be selected, but without using a ganged switch.

\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline \end{tabular} \end{center} Route Matrix 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

\(\mathbf { 5 }\) & 15 & 23 & 43 & 16 & 30
\hline \end{tabular} \end{center} (ii) Perform the fourth iteration. There are no changes on the fifth iteration, so your answer to part (ii) should give the complete network of shortest distances.
(iii) Use your matrices to find the shortest distance and route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 1 }\), and explain how you do it.
(iv) Draw the complete network of shortest distances, not including the loops.
(v) Apply the nearest neighbour algorithm to your network in part (iv), starting at vertex 2. Give the length of the Hamilton cycle that is produced. Interpret the Hamilton cycle in terms of the original diagram and state what the algorithm has achieved. OCR is committed to seeking permission to reproduce all third-party content that it uses in its assessment materials. OCR has attempted to identify and contact all copyright holders whose work is used in this paper. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced in the OCR Copyright Acknowledgements Booklet. This is produced for each series of examinations, is given to all schools that receive assessment material and is freely available to download from our public website (\href{http://www.ocr.org.uk}{www.ocr.org.uk}) after the live examination series.
If OCR has unwittingly failed to correctly acknowledge or clear any third-party content in this assessment material, OCR will be happy to correct its mistake at the earliest possible opportunity.
For queries or further information please contact the Copyright Team, First Floor, 9 Hills Road, Cambridge CB2 1PB.
OCR is part of the Cambridge Assessment Group; Cambridge Assessment is the brand name of University of Cambridge Local Examinations Syndicate (UCLES), which is itself a department of the University of Cambridge. \section*{ADVANCED GCE
MATHEMATICS (MEI)} Decision Mathematics 2 \section*{Candidates answer on the Answer Booklet} \section*{OCR Supplied Materials:}

• 8 page Answer Booklet
• MEI Examination Formulae and Tables (MF2)
• Graph paper

\section*{Other Materials Required:}

• Scientific or graphical calculator

\section*{Tuesday 22 June 2010 Afternoon} 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.
• Do not write in the bar codes.
• 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.

• 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 \(\mathbf { 7 2 }\).
• This document consists of \(\mathbf { 8 }\) pages. Any blank pages are indicated.

1

1. Mickey ate the last of the cheese. Minnie was put out at this. Mickey's defence was "There wasn't enough left not to eat it all". Let "c" represent "there is enough cheese for two" and "e" represent "one person can eat all of the cheese".
   1. Which of the following best captures Mickey's argument? $$\mathrm { c } \Rightarrow \mathrm { e } \quad \mathrm { c } \Rightarrow \sim \mathrm { e } \quad \sim _ { \mathrm { c } } \Rightarrow \mathrm { e } \quad \sim \mathrm { c } \Rightarrow \sim \mathrm { e }$$ In the ensuing argument Minnie concedes that if there's a lot left then one should not eat it all, but argues that this is not an excuse for Mickey having eaten it all when there was not a lot left.
   2. Prove that Minnie is right by writing down a line of a truth table which shows that $$( c \Rightarrow \sim e ) \Leftrightarrow ( \sim c \Rightarrow e )$$ is false.
      (You may produce the whole table if you wish, but you need to indicate a specific line of the table.)
2. 1. Show that the following combinatorial circuit is modelling an implication statement. Say what that statement is, and prove that the circuit and the statement are equivalent.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-23_188_533_1272_767}
   2. Express the following combinatorial circuit as an equivalent implication statement.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-23_314_835_1599_616}
   3. Explain why \(( \sim \mathrm { p } \wedge \sim \mathrm { q } ) \Rightarrow \mathrm { r }\), together with \(\sim \mathrm { r }\) and \(\sim \mathrm { q }\), give p . 2 The network is a representation of a show garden. The weights on the arcs give the times in minutes to walk between the six features represented by the vertices, where paths exist.
      \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-24_483_985_342_539}
   4. Why might it be that the time taken to walk from vertex \(\mathbf { 2 }\) to vertex \(\mathbf { 3 }\) via vertex \(\mathbf { 4 }\) is less than the time taken by the direct route, i.e. the route from \(\mathbf { 2 }\) to \(\mathbf { 3 }\) which does not pass through any other vertices? The matrices shown below are the results of the first iteration of Floyd's algorithm when applied to the network. \begin{center} \begin{tabular}{ | c | c | c | c | c | c | c | } \cline { 2 - 7 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\) & \(\mathbf { 5 }\) & \(\mathbf { 6 }\)
      \hline \(\mathbf { 1 }\) & \(\infty\) & 15 & \(\infty\) & \(\infty\) & 7 & 8
      \hline \(\mathbf { 2 }\) & 15 & 30 & 6 & 2 & 6 & 23
      \hline \(\mathbf { 3 }\) & \(\infty\) & 6 & \(\infty\) & 3 & \(\infty\) & \(\infty\)
      \hline \(\mathbf { 4 }\) & \(\infty\) & 2 & 3 & \(\infty\) & 10 & 17
      \hline \(\mathbf { 5 }\) & 7 & 6 & \(\infty\) & 10 & 14 & 8
      \hline

\(\mathbf { 6 }\) & 8 & 23 & \(\infty\) & 17 & 8 & 16
\hline \end{tabular} \end{center}

1. The teacher suspects that a pupil has copied work from the internet. For each box, state whether the teacher should tick the box or not.
2. The teacher has no suspicions about the work of another pupil, and has no information about how the work was produced. Which boxes should she tick?
3. Explain why the teacher must always tick at least one box.
   (b) Angus, the ski instructor, says that the class will have to have lunch in Italy tomorrow if it is foggy or if the top ski lift is not working. On the next morning Chloe, one of Angus's students, says that it is not foggy, so they can have lunch in Switzerland. Produce a line of a truth table which shows that Chloe's deduction is incorrect. You may produce a complete truth table if you wish, but you must indicate a row which shows that Chloe's deduction is incorrect.
   (c) You are given that the following two statements are true. $$\begin{aligned} & ( \mathrm { X } \vee \sim \mathrm { Y } ) \Rightarrow \mathrm { Z }
   & \sim \mathrm { Z } \end{aligned}$$ Use Boolean algebra to show that Y is true. 2 Adrian is considering selling his house and renting a flat.
   Adrian still owes \(\pounds 150000\) on his house. He has a mortgage for this, for which he has to pay \(\pounds 4800\) annual interest. If he sells he will pay off the \(\pounds 150000\) and invest the remainder of the proceeds at an interest rate of \(2.5 \%\) per annum. He will use the interest to help to pay his rent. His estate agent estimates that there is a \(30 \%\) chance that the house will sell for \(\pounds 225000\), a \(50 \%\) chance that it will sell for \(\pounds 250000\), and a \(20 \%\) chance that it will sell for \(\pounds 275000\). A flat will cost him \(\pounds 7500\) per annum to rent.
4. Draw a decision tree to help Adrian to decide whether to keep his house, or to sell it and rent a flat. Compare the EMVs of Adrian's annual outgoings, and ignore the costs of selling.
5. Would the analysis point to a different course of action if Adrian were to use a square root utility function, instead of EMVs? Adrian's circumstances change so that he has to decide now whether to sell or not in one year's time. Economic conditions might then be less favourable for the housing market, the same, or more favourable, these occurring with probabilities \(0.3,0.3\) and 0.4 respectively. The possible selling prices and their probabilities are shown in the table.

   Economic conditions and probabilities		Selling prices ( £) and probabilities
   less favourable	0.3	200000	0.2	225000	0.3	250000	0.5
   unchanged	0.3	225000	0.3	250000	0.5	275000	0.2
   more favourable	0.4	250000	0.3	300000	0.5	350000	0.2

6. Draw a decision tree to help Adrian to decide what to do. Compare the EMVs of Adrian's annual outgoings. Assume that he will still owe \(\pounds 150000\) in one year's time, and that the cost of renting and interest rates do not change. 3 The weights on the network represent distances.
   \includegraphics[max width=\textwidth, alt={}, center]{83d00f1f-25e5-4a26-bac5-dc2baf965438-36_451_544_324_740}
7. The answer book shows the initial tables and the results of iterations \(1,2,3\) and 5 when Floyd's algorithm is applied to the network.
   (A) Complete the two tables for iteration 4.
   (B) Use the final route table to give the shortest route from vertex \(\mathbf { 3 }\) to vertex \(\mathbf { 5 }\).
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
8. Using the complete network of shortest distances, find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 5 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
9. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 1 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
10. Interpret your Hamilton cycle in part (iii) in terms of the original network.
11. Give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Give the length of your walk. 4 A publisher is considering producing three books over the next week: a mathematics book, a novel and a biography. The mathematics book will sell at \(\pounds 10\) and costs \(\pounds 4\) to produce. The novel will sell at \(\pounds 5\) and costs \(\pounds 2\) to produce. The biography will sell at \(\pounds 12\) and costs \(\pounds 5\) to produce. The publisher wants to maximise profit, and is confident that all books will be sold. There are constraints on production. Each copy of the mathematics book needs 2 minutes of printing time, 1 minute of packing time, and \(300 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the novel needs 1.5 minutes of printing time, 0.5 minutes of packing time, and \(200 \mathrm {~cm} ^ { 3 }\) of temporary storage space. Each copy of the biography needs 2.5 minutes of printing time, 1.5 minutes of packing time, and \(400 \mathrm {~cm} ^ { 3 }\) of temporary storage space. There are 10000 minutes of printing time available on several printing presses, 7500 minutes of packing time, and \(2 \mathrm {~m} ^ { 3 }\) of temporary storage space.
12. Explain how the following initial feasible tableau models this problem.

    P	\(x\)	\(y\)	\(z\)	\(s 1\)	\(s 2\)	\(s 3\)	RHS
    1	- 6	- 3	- 7	0	0	0	0
    0	2	1.5	2.5	1	0	0	10000
    0	1	0.5	1.5	0	1	0	7500
    0	300	200	400	0	0	1	2000000

13. Use the simplex algorithm to solve your LP, and interpret your solution.
14. The optimal solution involves producing just one of the three books. By how much would the price of each of the other books have to be increased to make them worth producing? There is a marketing requirement to provide at least 1000 copies of the novel.
15. Show how to incorporate this constraint into the initial tableau ready for an application of the two-stage simplex method. Briefly describe how to use the modified tableau to solve the problem. You are NOT required to perform the iterations.