| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | Complete Table by Inspection |
| Difficulty | Easy -1.2 This is a routine application of standard Decision Maths algorithms. Part (a) requires simple inspection of a small network to find shortest distances (likely Floyd-Warshall by eye or direct observation). Parts (b) and (d) are mechanical applications of the nearest-neighbour algorithm, which is a straightforward procedure taught explicitly in D2. The question requires no problem-solving insight, just careful execution of learned procedures on a small network with 6 vertices. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02r Graph modelling: model and solve problems using graphs7.04c Travelling salesman upper bound: nearest neighbour method |
## Question 1: Simplex Method
From the initial tableau given, I can work through the iterations if you'd like a full solution.1.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-002_675_1052_378_485}
\end{center}
\end{figure}
Figure 1 shows a network of roads connecting six villages $A , B , C , D , E$ and $F$. The lengths of the roads are given in km .
\begin{enumerate}[label=(\alph*)]
\item Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection.
The table can now be taken to represent a complete network.
\item Use the nearest-neighbour algorithm, starting at $A$, on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at $A$ and visits every village exactly once.\\
(3)
\item Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.\\
(1)
\item By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 Q1}}