| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.3 This is a standard Floyd's algorithm question with routine route extraction and TSP application. While it has multiple parts, each step follows textbook procedures: performing an iteration, reading matrices, applying nearest neighbour, and calculating lower bounds. The techniques are algorithmic rather than requiring problem-solving insight, making it slightly easier than average for A-level Further Maths. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 0 | 5 | 3 | 4 |
| \(\mathbf { 2 }\) | 5 | 0 | 3 | 1 |
| \(\mathbf { 3 }\) | 3 | 3 | 0 | 1 |
| \(\mathbf { 4 }\) | 5 | 2 | 1 | 2 |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 2 |
| \(\mathbf { 2 }\) | 1 | 1 | 3 | 4 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 |
| \(\mathbf { 4 }\) | 2 | 2 | 3 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Correct initial tableau set up with slack variables | B1 | |
| Pivot on \(y\) column element (most positive / as instructed) | M1 | |
| Correct pivot operation performed | A1 | |
| Second pivot if needed | M1 | |
| Correct optimal tableau | A1 | |
| Optimal solution: \(x=0\), \(y=1250\), \(P=1250\) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Constraint \(x \geq 200\) added correctly as \(x \geq 200\) | B1 | |
| Converted to \(-x \leq -200\) or artificial variable introduced | M1 | |
| Correct big-M or two-stage setup | M1 A1 | |
| Correct pivoting sequence | M2 | |
| Correct solution: \(x=200\), \(y=850\), \(P=1050\) | A2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New objective: minimise \(C = 0.75x + 1.25y\) with \(x+y \geq 1000\) | B1 | |
| Correct tableau modification from part (ii) solution | M1 | |
| Correct pivoting | M1 A1 | |
| Correct optimal solution stated | A1 |
# Question 4:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Correct initial tableau set up with slack variables | B1 | |
| Pivot on $y$ column element (most positive / as instructed) | M1 | |
| Correct pivot operation performed | A1 | |
| Second pivot if needed | M1 | |
| Correct optimal tableau | A1 | |
| Optimal solution: $x=0$, $y=1250$, $P=1250$ | A1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Constraint $x \geq 200$ added correctly as $x \geq 200$ | B1 | |
| Converted to $-x \leq -200$ or artificial variable introduced | M1 | |
| Correct big-M or two-stage setup | M1 A1 | |
| Correct pivoting sequence | M2 | |
| Correct solution: $x=200$, $y=850$, $P=1050$ | A2 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| New objective: minimise $C = 0.75x + 1.25y$ with $x+y \geq 1000$ | B1 | |
| Correct tableau modification from part (ii) solution | M1 | |
| Correct pivoting | M1 A1 | |
| Correct optimal solution stated | A1 | |\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 & 5 & 3 & 4 \\
\hline
$\mathbf { 2 }$ & 5 & 0 & 3 & 1 \\
\hline
$\mathbf { 3 }$ & 3 & 3 & 0 & 1 \\
\hline
$\mathbf { 4 }$ & 5 & 2 & 1 & 2 \\
\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 }$ & 2 & 2 & 2 & 2 \\
\hline
$\mathbf { 2 }$ & 1 & 1 & 3 & 4 \\
\hline
$\mathbf { 3 }$ & 2 & 2 & 2 & 4 \\
\hline
$\mathbf { 4 }$ & 2 & 2 & 3 & 3 \\
\hline
\end{tabular}
\end{center}
(i) Perform the fourth (final) iteration of the algorithm.\\
(ii) Explain how to use the final matrices to find the shortest distance and the shortest route from vertex $\mathbf { 1 }$ to vertex $\mathbf { 3 }$, and give the distance and route.\\
(iii) Draw the complete network of shortest distances.\\
(iv) Apply the nearest neighbour algorithm, starting at vertex $\mathbf { 1 }$, to your complete network of shortest distances. Give the Hamilton cycle it produces, its length, and the corresponding route through the original network.\\
(v) By considering vertex 2 and its arcs, construct a lower bound for the length of the solution to the travelling salesperson problem in the original network.\\
(vi) Explain what you can deduce from your answers to parts (iv) and (v).
4 Noel is designing a hotel patio. It will consist of decking and paving.\\
Decking costs $\pounds 4$ per $\mathrm { m } ^ { 2 }$ and paving costs $\pounds 2$ per $\mathrm { m } ^ { 2 }$. He has a budget of $\pounds 2500$.\\
Noel prefers paving to decking, and he wants the area given to paving to be at least twice that given to decking.
He wants to have as large a patio as possible.\\
Noel's problem is formulated as the following LP.\\
Let $x$ be the number of $\mathrm { m } ^ { 2 }$ of decking.\\
Let $y$ be the number of $\mathrm { m } ^ { 2 }$ of paving.
$$\begin{aligned}
\text { Maximise } \quad P & = x + y \\
\text { subject to } 2 x + y & \leqslant 1250 \\
2 x - y & \leqslant 0 \\
x & \geqslant 0 \\
y & \geqslant 0
\end{aligned}$$
(i) Use the simplex algorithm to solve this LP. Pivot first on the positive element in the $y$ column.
Noel would like to have at least $200 \mathrm {~m} ^ { 2 }$ of decking.\\
(ii) Add a line corresponding to this constraint to your solution tableau from part (i), and modify the resulting table either for two-stage simplex or the big-M method. Hence solve the problem.
Noel finally decides that he will minimise the annual cost of maintenance, which is given by $\pounds ( 0.75 x + 1.25 y )$, subject to the additional constraint that there is at least $1000 \mathrm {~m} ^ { 2 }$ of patio.\\
(iii) Starting from your solution to part (ii), use simplex to solve this problem.
\hfill \mbox{\textit{OCR MEI D2 2007 Q4 [20]}}