OCR MEI D2 (Decision Mathematics 2) 2015 June

1 A furniture manufacturer is planning a production run. He will be making wardrobes, drawer units and desks. All can be manufactured from the same wood. He has available \(200 \mathrm {~m} ^ { 2 }\) of wood for the production run. Allowing for wastage, a wardrobe requires \(5 \mathrm {~m} ^ { 2 }\), a drawer unit requires \(3 \mathrm {~m} ^ { 2 }\), and a desk requires \(2 \mathrm {~m} ^ { 2 }\). He has 200 hours available for the production run. A wardrobe requires 4.5 hours, a drawer unit requires 5.2 hours, and a desk requires 3.8 hours. The completed furniture will have to be stored at the factory for a short while before being shipped. The factory has \(50 \mathrm {~m} ^ { 3 }\) of storage space available. A wardrobe needs \(1 \mathrm {~m} ^ { 3 }\), a drawer unit needs \(0.75 \mathrm {~m} ^ { 3 }\), and a desk needs \(0.5 \mathrm {~m} ^ { 3 }\). The manufacturer needs to know what he should produce to maximise his income. He sells the wardrobes at \(\pounds 80\) each, the drawer units at \(\pounds 65\) each and the desks at \(\pounds 50\) each.

1. Formulate the manufacturer's problem as an LP.
2. Use the Simplex algorithm to solve the LP problem.
3. Interpret the results.
4. An extra \(25 \mathrm {~m} ^ { 2 }\) of wood is found and is to be used. The new optimal solution is to make 44 wardrobes, no drawer units and no desks. However, this leaves some of each resource (wood, hours and space) left over. Explain how this can be possible.
5. Given that \(x\) and \(y\) are propositions, draw a 4-line truth table for \(x \Rightarrow y\), allowing \(x\) and \(y\) to take all combinations of truth values. If \(x\) is false and \(x \Rightarrow y\) is true, what can be deduced about the truth value of \(y\) ? A story has it that, in a lecture on logic, the philosopher Bertrand Russell (1872-1970) mentioned that a false proposition implies any proposition. A student challenged this, saying "In that case, given that \(1 = 0\), prove that you are the Pope."
   Russell immediately replied, "Add 1 to both sides of the equation: then we have \(2 = 1\). The set containing just me and the Pope has 2 members. But \(2 = 1\), so the set has only 1 member; therefore, I am the Pope." Russell's string of statements is an example of a deductive sequence. Let \(a\) represent " \(1 = 0\) ", \(b\) represent " \(2 = 1\) ", \(c\) represent "Russell and the Pope are 2" and \(d\) represent "Russell and the Pope are 1". Then Russell's deductive sequence can be written as \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
6. Assuming that \(a\) is false, \(b\) is false, \(a \Rightarrow b\) is true, \(c\) is true, and that \(d\) can take either truth value, draw a 2-line truth table for \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\).
7. What does the table tell you about \(d\) with respect to the false proposition \(a\) ?
8. Explain why Russell introduced propositions \(b\) and \(c\) into his argument.
9. Russell could correctly have started a deductive sequence:
   \(a \wedge [ a \Rightarrow ( ( 0.5 = - 0.5 ) \Rightarrow ( 0.25 = 0.25 ) ) ]\).
   Had he have done so could he correctly have continued it to end at \(d\) ?
   Justify your answer.
10. Draw a combinatorial circuit to represent \(( a \wedge ( a \Rightarrow b ) \wedge c ) \Rightarrow d\). 3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times.
    \includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \begin{center} \captionsetup{labelformat=empty} \caption{final time matrix} \begin{tabular}{ | l | r | r | r | r | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{\(\mathbf { 1 }\)} & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \multicolumn{1}{c|}{\(\mathbf { 4 }\)}
    \hline \(\mathbf { 1 }\) & 6 & 5 & 3 & 10
    \hline

3 Floyd's algorithm is applied to the incomplete network on 4 nodes drawn below. The weights on the arcs represent journey times.
\includegraphics[max width=\textwidth, alt={}, center]{4b5bc097-1052-4e44-8623-a84ceaab0289-4_400_558_347_751} The final matrices are shown below. \begin{table}[h] \begin{center} \captionsetup{labelformat=empty} \caption{final time matrix} \begin{tabular}{ | l | r | r | r | r | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{\(\mathbf { 1 }\)} & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \multicolumn{1}{c|}{\(\mathbf { 4 }\)}
\hline \(\mathbf { 1 }\) & 6 & 5 & 3 & 10
\hline \(\mathbf { 2 }\) & 5 & 4 & 2 & 5
\hline \(\mathbf { 3 }\) & 3 & 2 & 4 & 7
\hline

\(\mathbf { 4 }\) & 10 & 5 & 7 & 10
\hline \end{tabular} \end{center} \end{table} \begin{table}[h] \end{table}

1. Draw the complete network of shortest times.
2. Explain how to use the final route matrix to find the quickest route from node \(\mathbf { 4 }\) to node \(\mathbf { 1 }\) in the original incomplete network. Give this quickest route. A new node, node 5, is added to the original incomplete network. The new journey times are shown in the table. \begin{center} \begin{tabular}{ | l | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & \(\mathbf { 1 }\) & \(\mathbf { 2 }\) & \(\mathbf { 3 }\) & \(\mathbf { 4 }\)
   \hline

\(\mathbf { 5 }\) & 4 & - & - & 2
\hline \end{tabular} \end{center} (iii) Draw the complete 5-node network of shortest times. (You are not required to use an algorithm to find the shortest times.)
(iv) Write down the final time matrix and the final route matrix for the complete 5 -node network. (You do not need to apply Floyd's algorithm.)
(v) (A) Apply the nearest neighbour algorithm to the complete 5-node network of shortest times, starting at node 1. Give the time for the cycle you produce.
(B) Starting at node 3, a possible cycle in the complete 5-node network of shortest times is \(\mathbf { 3 2 1 5 4 3 . }\) Give the actual cycle to which this corresponds in the incomplete 5-node network of journey times.
(vi) By deleting node 5 and its arcs from the complete 5 -node network of shortest times, and then using Kruskal's algorithm, produce a lower bound for the solution to the associated practical travelling salesperson problem. Show clearly your use of Kruskal's algorithm.
(vii) In the incomplete 5-node network of journey times, find a quickest route starting at node \(\mathbf { 5 }\) and using each of the 7 arcs at least once. Give the time of your route. 4 Helen has a meeting to go to in London. She has to travel from her home in G on the south coast to KC in London. She can drive from G to the west to A to catch a train, or she can drive to the east to W to catch a train on a different line. From both A and W she can travel to mainline terminuses V or LB in London. She will then travel by tube either from V to KC , or from LB to KC . The times for the various steps of her journey are shown in the tables. Both train services and tube services are subject to occasional delays, and these are modelled in the tables. Helen wants to choose the route which will give the shortest expected journey time.
(i) Draw a decision tree to model Helen's decisions and the possible outcomes.
(ii) Calculate Helen's shortest expected journey time and give the route which corresponds to that shortest expected journey time. As she gets into her car, Helen hears a travel bulletin on the radio warning of a broken escalator at V. This means that routes through V will take Helen 10 minutes longer.
(iii) Find the value of the radio information, explaining your calculation.
(iv) Why might the shortest expected journey time not be the best criterion for choosing a route for Helen?