OCR MEI D2 (Decision Mathematics 2) 2005 June

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]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_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.

2 Karl is considering investing in a villa in Greece. It will cost him 56000 euros ( € 56000 ). His alternative is to invest his money, \(\pounds 35000\), in the United Kingdom. He is concerned with what will happen over the next 5 years. He estimates that there is a \(60 \%\) chance that a house currently worth \(€ 56000\) will appreciate to be worth \(€ 75000\) in that time, but that there is a \(40 \%\) chance that it will be worth only \(€ 55000\). If he invests in the United Kingdom then there is a \(50 \%\) chance that there will be \(20 \%\) growth over the 5 years, and a \(50 \%\) chance that there will be \(10 \%\) growth.

1. Given that \(\pounds 1\) is worth \(€ 1.60\), draw a decision tree for Karl, and advise him what to do, using the EMV of his investment (in thousands of euros) as his criterion. In fact the \(\pounds / €\) exchange rate is not fixed. It is estimated that at the end of 5 years, if there has been \(20 \%\) growth in the UK then there is a \(70 \%\) chance that the exchange rate will stand at 1.70 euros per pound, and a \(30 \%\) chance that it will be 1.50 . If growth has been \(10 \%\) then there is a \(40 \%\) chance that the exchange rate will stand at 1.70 and a \(60 \%\) chance that it will be 1.50 .
2. Produce a revised decision tree incorporating this information, and give appropriate advice. A financial analyst asks Karl a number of questions to determine his utility function. He estimates that for \(x\) in cash (in thousands of euros) Karl's utility is \(x ^ { 0.8 }\), and that for \(y\) in property (in thousands of euros), Karl's utility is \(y ^ { 0.75 }\).
3. Repeat your computations from part (ii) using utility instead of the EMV of his investment. Does this change your advice?
4. Using EMVs, find the exchange rate (number of euros per pound) which will make Karl indifferent between investing in the UK and investing in a villa in Greece.
5. Show that, using Karl's utility function, the exchange rate would have to drop to 1.277 euros per pound to make Karl indifferent between investing in the UK and investing in a villa in Greece.

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix \begin{center} \begin{tabular}{ | c | c | c | c | c | } \multicolumn{1}{l}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\)
\hline \(\mathbf { 1 }\) & 4 & 2 & 3 & 9
\hline \(\mathbf { 2 }\) & 2 & 2 & \(\mathbf { 1 }\) & 7
\hline \(\mathbf { 3 }\) & 3 & \(\mathbf { 1 }\) & 2 & 6
\hline

\(\mathbf { 4 }\) & 9 & 7 & 6 & 12
\hline \end{tabular} \end{center} Route Matrix Fig. 3.1 \begin{figure}[h] \end{figure}

1. Draw the complete network of shortest distances.
2. Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \begin{table}[h]

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	1	2	3	4
   5	-	3	-	1

   \captionsetup{labelformat=empty} \caption{Fig. 3.3}
   \end{table}
3. Draw the extended network and the complete 5 -node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.)
4. Produce the shortest distance matrix and the route matrix for the extended 5-node network.
5. Apply the nearest neighbour algorithm to your \(5 \times 5\) distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network.
6. By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm.
7. In the original 5-node network find a shortest route starting at vertex \(\mathbf { 1 }\) and using each of the 6 arcs at least once. Give the length of your route. 4 Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10 ml of oil and between 3 and 6 ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: $$\begin{array} { l c } \text { Maximise } & \frac { x } { x + y }
   \text { subject to } & 0 \leqslant x \leqslant 10 ,
   & 0 \leqslant y \leqslant 6 ,
   & x - 2 y \leqslant 0 . \end{array}$$
8. Explain why this problem is not an LP.
9. Use the simplex method to solve the following LP. $$\begin{array} { l c } \text { Maximise } & x - y
   \text { subject to } & 0 \leqslant x \leqslant 10
   & 0 \leqslant y \leqslant 6
   & x - 2 y \leqslant 0 \end{array}$$
10. Kassi prefers to have more vinegar than oil. She formulates the following LP. $$\begin{array} { l l } \text { Maximise } & y - x
    \text { subject to } & 5 \leqslant x \leqslant 10 ,
    & 3 \leqslant y \leqslant 6 ,
    & x - 2 y \leqslant 0 . \end{array}$$ Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii).
11. Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii).
12. Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed.