| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2008 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm application |
| Difficulty | Standard +0.3 This is a standard application of Floyd's algorithm followed by routine TSP heuristics (nearest neighbour, lower bound via deletion) and route inspection. The question requires executing well-defined algorithms with given data rather than problem-solving or novel insight. While multi-part and requiring careful bookkeeping, these are textbook Decision Maths procedures slightly above average difficulty due to length and multiple algorithmic steps. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 0 | 13 | 10 | 15 |
| \(\mathbf { 2 }\) | 13 | 0 | 12 | 20 |
| \(\mathbf { 3 }\) | 10 | 12 | 0 | 9 |
| \(\mathbf { 4 }\) | 23 | 27 | 12 | 24 |
| \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 |
I've reviewed the content provided, but it appears to contain only formatting metadata, page numbers, and copyright information rather than actual mark scheme content with marking criteria, answers, and annotation codes (M1, A1, B1, etc.).
There is no substantive marking guidance to clean up or convert. To process a mark scheme, I would need content such as:
- Expected answers or solution steps
- Marking annotations (M1, A1, B1, DM1, etc.)
- Mathematical expressions or symbols requiring LaTeX conversion
- Guidance notes for examiners
Could you please provide the actual mark scheme content for Question 4?\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
$\mathbf { 1 }$ & 0 & 13 & 10 & 15 \\
\hline
$\mathbf { 2 }$ & 13 & 0 & 12 & 20 \\
\hline
$\mathbf { 3 }$ & 10 & 12 & 0 & 9 \\
\hline
$\mathbf { 4 }$ & 23 & 27 & 12 & 24 \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
$\mathbf { 1 }$ & 3 & 2 & 3 & 3 \\
\hline
$\mathbf { 2 }$ & 1 & 1 & 3 & 3 \\
\hline
$\mathbf { 3 }$ & 1 & 2 & 1 & 4 \\
\hline
$\mathbf { 4 }$ & 3 & 3 & 3 & 3 \\
\hline
\end{tabular}
\end{center}
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.
\hfill \mbox{\textit{OCR MEI D2 2008 Q4 [20]}}