OCR MEI D2 (Decision Mathematics 2) 2013 June

1

1. A graph is simple if it contains neither loops nor multiple arcs, ie none of the following:
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_81_134_219_1683}
   or
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_79_589_301_328} In an examination question, students were asked to describe in words when a graph is simple. Mark the following responses as right or wrong, giving reasons for your decisions if you mark them wrong.
   1. A graph is simple if there are no loops and if two nodes are connected by a single arc.
   2. A graph is simple if there are no loops and no two nodes are connected by more than one arc.
   3. A graph is simple if there are no loops and two arcs do not have the same ends.
   4. A graph is simple if there are no loops and there is at most one route from one node to another.
2. The following picture represents a two-way switch
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_149_138_932_1119} It can either be in the up state
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_104_104_1128_790}
   or in the down state • or in the down state . Two switches can be used to construct a circuit in which changing the state of either switch changes the state of a lamp.
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_309_543_1448_762} Georgios tries to connect together three two-way switches so that changing the state of any switch changes the state of the lamp. His circuit is shown below. The switches have been labelled 1,2 and 3.
   \includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-2_496_547_1946_760}
   1. List the possible combination of switch states and determine whether the lamp is on or off for each of them.
   2. Say whether or not Georgios has achieved his objective, justifying your answer.
3. Use a truth table to show that \(( \mathrm { A } \wedge ( \mathrm { B } \vee \mathrm { C } ) ) \vee \sim ( \sim \mathrm { A } \vee ( \mathrm { B } \wedge \mathrm { C } ) ) \Leftrightarrow \mathrm { A }\).

2 Graham skis each year in an Italian resort which shares a ski area with a Swiss resort. He can buy an Italian lift pass, or an international lift pass which gives him access to Switzerland as well as to Italy. For his 6-day holiday the Italian pass costs \(€ 200\) and the international pass costs \(€ 250\). If he buys an Italian pass then he can still visit Switzerland by purchasing day supplements at \(€ 30\) per day. If the weather is good during his holiday, then Graham visits Switzerland three times. If the weather is moderate he goes twice. If poor he goes once. If the weather is windy then the lifts are closed, and he is not able to go at all. In his years of skiing at the resort he has had good weather on \(30 \%\) of his visits, moderate weather on \(40 \%\), poor weather on \(20 \%\) and windy weather on \(10 \%\) of his visits.

1. Draw a decision tree to help Graham decide whether to buy an Italian lift pass or an international lift pass. Give the action he should take to minimize the EMV of his costs. When he arrives at the resort, and before he buys his lift pass, he finds that he has internet access to a local weather forecast, and to records of the past performance of the forecast. The 6-day forecast is limited to "good"/"not good", and the records show the actual weather proportions following those forecasts. It also shows that \(60 \%\) of historical forecasts have been "good" and \(40 \%\) "not good".

   \backslashbox{Forecast}{Actual}	good	moderate	poor	windy	proportion of forecasts
   good	0.4	0.5	0.1	0.0	0.6
   not good	0.15	0.25	0.35	0.25	0.4

2. Draw a decision tree to help Graham decide the worth of consulting the forecast before buying his lift pass. Give the actions he should take to minimize the EMV of his costs.

3 Five towns, 1, 2, 3, 4 and 5, are connected by direct routes as shown. The arc weights represent distances.
\includegraphics[max width=\textwidth, alt={}, center]{a09472cd-8f65-4cca-9683-c386053e66aa-4_632_540_312_744}

1. The printed 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 5 to vertex 2.
   (C) Use the final distance table to produce a complete network with weights representing the shortest distances between vertices.
2. Use the nearest neighbour algorithm, starting at vertex \(\mathbf { 4 }\), to produce a Hamilton cycle in the complete network. Give the length of your cycle.
3. Interpret your Hamilton cycle from part (ii) in terms of towns actually visited.
4. Find an improved Hamilton cycle by applying the nearest neighbour algorithm starting from one of the other vertices.
5. Using the complete network of shortest distances (excluding loops), find a lower bound for the solution to the Travelling Salesperson Problem by deleting vertex 4 and its arcs, and by finding the length of a minimum connector for the remainder. (You may find the minimum connector by inspection.)
6. Given that the sum of the road lengths in the original network is 43 , give a walk of minimum length which traverses every arc on the original network at least once, and which returns to the start. Show your methodology. Give the length of your walk.

4 Colin has a hobby from which he makes a small income. He makes bowls, candle holders and key fobs.
The materials he uses include wood, metal parts, polish and sandpaper. They cost, on average, \(\pounds 15\) per bowl, \(\pounds 6\) per candle holder and \(\pounds 2\) per key fob. Colin has a monthly budget of \(\pounds 100\) for materials. Colin spends no more than 30 hours per month on manufacturing these objects. Each bowl takes 4 hours, each candle holder takes 2 hours and each key fob takes half an hour.

1. Let \(b\) be the number of bowls Colin makes in a month, \(c\) the number of candle holders and \(f\) the number of key fobs. Write out, in terms of these variables, two constraints corresponding to the limit on monthly expenditure on materials, and to the limit on Colin's time. Colin sells the objects at craft fairs. He charges \(\pounds 30\) for a bowl, \(\pounds 15\) for a candle holder and \(\pounds 3\) for a key fob.
2. Set up an initial simplex tableau for the problem of maximising Colin's monthly income subject to your constraints from part (i), assuming that he sells all that he produces.
3. Use the simplex algorithm to solve your LP, and interpret the solution from the simplex algorithm. Over a spell of several months Colin finds it difficult to sell bowls so he stops making them.
4. Modify and solve your LP, using simplex, to find how many candle holders and how many key fobs he should make, and interpret your solution. At the next craft fair Colin takes an order for 4 bowls. He promises to make exactly 4 bowls in the next month.
5. Set up this modified problem either as an application of two-stage simplex, or as an application of the big-M method. You are not required to solve the problem. The solution now is for Colin to produce 4 bowls, \(6 \frac { 2 } { 3 }\) candle holders and no key fobs.
6. What is Colin's best integer solution to the problem?
7. Your answer to part (vi) is not necessarily the integer solution giving the maximum profit for Colin. Explain why.