| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 10 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Complete Table by Inspection |
| Difficulty | Easy -1.8 This question tests only basic understanding of upper/lower bounds (selecting minimum/maximum from lists) and reading values from a completed table. Part (a) requires no calculation, just identifying which number is smallest/largest. The remaining parts involve straightforward application of standard algorithms with no problem-solving required. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \cline { 2 - 6 } \multicolumn{1}{c|}{} | \(\boldsymbol { B }\) | \(\boldsymbol { E }\) | \(\boldsymbol { L }\) | \(\boldsymbol { M }\) | \(\boldsymbol { N }\) |
| \(\boldsymbol { B }\) | - | 230 | 82 | 102 | 192 |
| \(\boldsymbol { E }\) | 230 | - | 148 | 244 | 258 |
| \(\boldsymbol { L }\) | 82 | 148 | - | 126 | 110 |
| \(\boldsymbol { M }\) | 102 | 244 | 126 | - | 236 |
| \(\boldsymbol { N }\) | 192 | 258 | 110 | 236 | - |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Best upper bound = \(30\) | B1 | Lowest of the upper bounds listed |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Best lower bound = \(20\) | B1 | Highest of the lower bounds listed |
# Question 6:
## Part (a)(i) [1 mark]
| Answer | Mark | Guidance |
|--------|------|----------|
| Best upper bound = $30$ | B1 | Lowest of the upper bounds listed |
## Part (a)(ii) [1 mark]
| Answer | Mark | Guidance |
|--------|------|----------|
| Best lower bound = $20$ | B1 | Highest of the lower bounds listed |
I can see these are exam answer spaces/question papers, but the actual mark scheme is not shown in these images - these pages only contain the questions and blank answer spaces for students.
To extract mark scheme content, I would need images of the actual mark scheme document, which would typically be a separate document showing:
- Model answers
- Mark allocations (M1, A1, B1, etc.)
- Examiner guidance notes
The pages shown contain:
- **Page 17**: Questions 6(b)(i)-(iv) about travelling times and nearest-neighbour algorithm
- **Page 20**: Question 7 about battery factory linear programming formulation
- **Pages 18, 19, 21**: Blank answer spaces
If you have the mark scheme pages, please share those images and I can extract and format the content as requested.
I can see these are answer space pages for Question 8 from what appears to be an AQA Mathematics exam (P/Jun14/MD01), but these pages do not contain a mark scheme — they are blank answer/working space pages provided for students to write their solutions.
To extract mark scheme content, I would need the actual mark scheme document. Here is what I can derive about the expected answers based on the question content shown:
---6
\begin{enumerate}[label=(\alph*)]
\item Sarah is solving a travelling-salesman problem.
\begin{enumerate}[label=(\roman*)]
\item She finds the following upper bounds: $32,33,32,32,30,32,32$.
Write down the best upper bound.
\item She finds the following lower bounds: 17, 18, 17, 20, 18, 17, 20.
Write down the best lower bound.
\end{enumerate}\item Rob is travelling by train to a number of cities. He is to start at $M$ and visit each other city at least once before returning to $M$.
The diagram shows the travelling times, in minutes, between cities. Where no time is shown, there is no direct journey available.\\
\includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-16_959_1122_1059_443}
The table below shows the minimum travelling times between all pairs of cities.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\cline { 2 - 6 }
\multicolumn{1}{c|}{} & $\boldsymbol { B }$ & $\boldsymbol { E }$ & $\boldsymbol { L }$ & $\boldsymbol { M }$ & $\boldsymbol { N }$ \\
\hline
$\boldsymbol { B }$ & - & 230 & 82 & 102 & 192 \\
\hline
$\boldsymbol { E }$ & 230 & - & 148 & 244 & 258 \\
\hline
$\boldsymbol { L }$ & 82 & 148 & - & 126 & 110 \\
\hline
$\boldsymbol { M }$ & 102 & 244 & 126 & - & 236 \\
\hline
$\boldsymbol { N }$ & 192 & 258 & 110 & 236 & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Explain why the minimum travelling time from $M$ to $N$ is not 283 .
\item Find an upper bound for the minimum travelling time by using the tour $M N B E L M$.
\item Write down the actual route corresponding to the tour $M N B E L M$.
\item Use the nearest-neighbour algorithm, starting from $M$, to find another upper bound for the minimum travelling time of Rob's tour.\\[0pt]
[4 marks]
QUESTION
(a)(i) The best upper bound is $\_\_\_\_$\\
(ii) The best lower bound is $\_\_\_\_$
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2014 Q6 [10]}}