| Exam Board | OCR MEI |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2005 |
| Session | June |
| Marks | 20 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Shortest Path |
| Type | Floyd's algorithm with route extraction |
| Difficulty | Standard +0.8 This is a multi-part question requiring systematic application of Floyd's algorithm results, route matrix interpretation, network extension, and multiple algorithms (nearest neighbour, Prim's). While each individual step follows standard procedures taught in D2, the question requires careful bookkeeping across six parts with potential for cumulative errors, and combines several distinct algorithmic techniques in one extended problem. |
| Spec | 7.04a Shortest path: Dijkstra's algorithm |
| \(\mathbf { 1 }\) | \(\mathbf { 2 }\) | \(\mathbf { 3 }\) | \(\mathbf { 4 }\) | |
| \(\mathbf { 1 }\) | 2 | 2 | 2 | 2 |
| \(\mathbf { 2 }\) | \(\mathbf { 1 }\) | 3 | 3 | 3 |
| \(\mathbf { 3 }\) | 2 | 2 | 2 | 4 |
| \(\mathbf { 4 }\) | 3 | 3 | 3 | 3 |
| \cline { 2 - 5 } \multicolumn{1}{c|}{} | 1 | 2 | 3 | 4 |
| 5 | - | 3 | - | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| The objective is nonlinear. | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Initial tableau: \(\begin{pmatrix} 1 & -1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 10 \\ 0 & 0 & 1 & 0 & 1 & 0 & 6 \\ 0 & 1 & -2 & 0 & 0 & 1 & 0 \end{pmatrix}\) | M1 A1 | tableau |
| After first pivot: \(\begin{pmatrix} 1 & 0 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 2 & 1 & 0 & -1 & 10 \\ 0 & 0 & 1 & 0 & 1 & 0 & 6 \\ 0 & 1 & -2 & 0 & 0 & 1 & 0 \end{pmatrix}\) | M1 A1 | pivot choice; pivot |
| After second pivot: \(\begin{pmatrix} 1 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 5 \\ 0 & 0 & 1 & \frac{1}{2} & 0 & -\frac{1}{2} & 5 \\ \cdots \end{pmatrix}\) | M1 A1 | pivot choice; pivot |
| 10 ml of oil and 5 ml of vinegar | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Lines \(x \leq 10\) and \(y \leq 6\) drawn | B1 | \(x \leq 10\) and \(y \leq 6\) |
| Lines \(5 \leq x\) and \(3 \leq y\) drawn | B1 | \(5 \leq x\) and \(3 \leq y\) |
| Proportion line drawn | B1 | proportion line |
| Region 1 correctly shaded/identified | B1 | region 1 |
| Region 2 correctly shaded/identified | B1 | region 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Omitted constraints non-active | B1 | |
| \((0, 0)\) not in feasible region | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(\geq\) constraints correctly handled | B1 | \(>\) constraints |
| Artificial columns \(a_1\), \(a_2\) included correctly | B1 | artificial columns |
| New objective row included | B1 | new objective |
| Full tableau: \(\begin{pmatrix} 1 & 0 & 1 & 1 & 0 & -1 & 0 & -1 & 0 & 0 & 0 & 8 \\ 0 & 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 10 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 5 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 6 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 3 \\ 0 & 0 & 1 & -2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix}\) | B1 B1 | |
| Minimise \(C\), hopefully to zero. Thereafter delete \(C\) row and \(a_1\)/\(a_2\) columns, and proceed as usual. | B1 B1 |
# Question 4:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| The objective is nonlinear. | B1 | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Initial tableau: $\begin{pmatrix} 1 & -1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 10 \\ 0 & 0 & 1 & 0 & 1 & 0 & 6 \\ 0 & 1 & -2 & 0 & 0 & 1 & 0 \end{pmatrix}$ | M1 A1 | tableau |
| After first pivot: $\begin{pmatrix} 1 & 0 & -1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 2 & 1 & 0 & -1 & 10 \\ 0 & 0 & 1 & 0 & 1 & 0 & 6 \\ 0 & 1 & -2 & 0 & 0 & 1 & 0 \end{pmatrix}$ | M1 A1 | pivot choice; pivot |
| After second pivot: $\begin{pmatrix} 1 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 5 \\ 0 & 0 & 1 & \frac{1}{2} & 0 & -\frac{1}{2} & 5 \\ \cdots \end{pmatrix}$ | M1 A1 | pivot choice; pivot |
| 10 ml of oil and 5 ml of vinegar | B1 | |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Lines $x \leq 10$ and $y \leq 6$ drawn | B1 | $x \leq 10$ and $y \leq 6$ |
| Lines $5 \leq x$ and $3 \leq y$ drawn | B1 | $5 \leq x$ and $3 \leq y$ |
| Proportion line drawn | B1 | proportion line |
| Region 1 correctly shaded/identified | B1 | region 1 |
| Region 2 correctly shaded/identified | B1 | region 2 |
## Part (iv)
| Answer | Mark | Guidance |
|--------|------|----------|
| Omitted constraints non-active | B1 | |
| $(0, 0)$ not in feasible region | B1 | |
## Part (v)
| Answer | Mark | Guidance |
|--------|------|----------|
| $\geq$ constraints correctly handled | B1 | $>$ constraints |
| Artificial columns $a_1$, $a_2$ included correctly | B1 | artificial columns |
| New objective row included | B1 | new objective |
| Full tableau: $\begin{pmatrix} 1 & 0 & 1 & 1 & 0 & -1 & 0 & -1 & 0 & 0 & 0 & 8 \\ 0 & 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 10 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 5 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 6 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 3 \\ 0 & 0 & 1 & -2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix}$ | B1 B1 | |
| Minimise $C$, hopefully to zero. Thereafter delete $C$ row and $a_1$/$a_2$ columns, and proceed as usual. | B1 B1 | |$\mathbf { 4 }$ & 9 & 7 & 6 & 12 \\
\hline
Route Matrix
\begin{center}
\begin{tabular}{ | l | l | l | l | l | }
\multicolumn{1}{l}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$ \\
\hline
$\mathbf { 1 }$ & 2 & 2 & 2 & 2 \\
\hline
$\mathbf { 2 }$ & $\mathbf { 1 }$ & 3 & 3 & 3 \\
\hline
$\mathbf { 3 }$ & 2 & 2 & 2 & 4 \\
\hline
$\mathbf { 4 }$ & 3 & 3 & 3 & 3 \\
\hline
\end{tabular}
\end{center}
Fig. 3.1
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-4_296_310_918_904}
\captionsetup{labelformat=empty}
\caption{Fig. 3.2}
\end{center}
\end{figure}
(i) Draw the complete network of shortest distances.\\
(ii) 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]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\cline { 2 - 5 }
\multicolumn{1}{c|}{} & 1 & 2 & 3 & 4 \\
\hline
5 & - & 3 & - & 1 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Fig. 3.3}
\end{center}
\end{table}
(iii) 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.)\\
(iv) Produce the shortest distance matrix and the route matrix for the extended 5-node network.\\
(v) 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.\\
(vi) 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.\\
(vii) 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}$$
(i) Explain why this problem is not an LP.\\
(ii) 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}$$
(iii) 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).\\
(iv) 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).\\
(v) Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem.
Explain briefly how to proceed.
\hfill \mbox{\textit{OCR MEI D2 2005 Q4 [20]}}