Question 2 - A-Level Maths

OCR MEI D2 2011 June — Question 2 16 marks

Exam Board	OCR MEI
Module	D2 (Decision Mathematics 2)
Year	2011
Session	June
Marks	16
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Travelling Salesman
Type	Floyd's Algorithm Application
Difficulty	Standard +0.3 This is a standard Floyd's algorithm application with routine TSP bounds calculation. While multi-part, each step follows textbook procedures: Floyd's algorithm is mechanical, TSP bounds use standard nearest neighbour/MST methods, and the discussion questions require only basic understanding of practical applications. Slightly above average due to length and the congestion charge modelling question requiring some thought about directed networks.
Spec	7.04a Shortest path: Dijkstra's algorithm 7.04c Travelling salesman upper bound: nearest neighbour method 7.04d Travelling salesman lower bound: using minimum spanning tree

2 A government has just created a new ministry, the Ministry of Administrative Affairs. The ministry is to have four departments:
the Administration
the Bureaucracy
the Certification Service
the Duplication Section.
Each of these departments is to be established in a separate office on one of four existing sites. The diagram shows the direct journey times in minutes between these four sites. \includegraphics[max width=\textwidth, alt={}, center]{52b8153f-e655-4852-a0f8-6f1c1e9c9170-3_342_403_721_829}

Use Floyd's algorithm to find the shortest journey times between the four office sites.
Draw a network showing your shortest times.
Use appropriate algorithms to find upper and lower bounds for the optimum solution to the Travelling Salesperson Problem in the original network, briefly explaining the steps taken.
A van is to be organised to deliver bundles of paperwork between the departments. Why might the optimum solution to the TSP be useful in planning this, and why might it not be?
Journeys to locations 2 and 3, from locations 1 and 4, are subject to a congestion charge which is equivalent in costing terms to 15 minutes of journey time. What sort of network would be needed to model this?

Show mark scheme Show mark scheme source

Question 2:

Part (i)

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct time matrix	B1
Correct route matrix	B1
Replacing an \(\infty\) by a correct value	M1
Correct values after first iteration	A1
Correct after second iteration	A1	ft
Correct after third iteration	A1	ft
Entries other than row 3 col 1 of route matrix correct	A1	ft
Row 3 col 1 of route matrix correct	B1	cao

Part (ii)

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct network drawn with edge weights	B1	ft

Part (iii)

Answer	Marks	Guidance
Answer	Mark	Guidance
Upper bound via nearest neighbour, e.g. \(2+2+2+6=12\)	M1, A1	mention of nearest neighbour or nearest neighbour computation; allow \(2+2+2+7=13\) etc for working in original network
Lower bound via deleting vertex 1, e.g. \((2+2)+2+4=10\)	M1, A1	delete a vertex; needs to be consistent with above

Part (iv)

Answer	Marks	Guidance
Answer	Mark	Guidance
e.g. if requirement is for part loads, delivering to one department en route to another might save time	B1	answer should be valid and refer to specific situation of the DAA
e.g. if requirement is for whole loads then might not be relevant	B1

Part (v)

Answer	Marks	Guidance
Answer	Mark	Guidance
A directed network	B1

# Question 2:

## Part (i)

| Answer | Mark | Guidance |
|--------|------|----------|
| Correct time matrix | B1 | |
| Correct route matrix | B1 | |
| Replacing an $\infty$ by a correct value | M1 | |
| Correct values after first iteration | A1 | |
| Correct after second iteration | A1 | ft |
| Correct after third iteration | A1 | ft |
| Entries other than row 3 col 1 of route matrix correct | A1 | ft |
| Row 3 col 1 of route matrix correct | B1 | cao |

## Part (ii)

| Answer | Mark | Guidance |
|--------|------|----------|
| Correct network drawn with edge weights | B1 | ft |

## Part (iii)

| Answer | Mark | Guidance |
|--------|------|----------|
| Upper bound via nearest neighbour, e.g. $2+2+2+6=12$ | M1, A1 | mention of nearest neighbour or nearest neighbour computation; allow $2+2+2+7=13$ etc for working in original network |
| Lower bound via deleting vertex 1, e.g. $(2+2)+2+4=10$ | M1, A1 | delete a vertex; needs to be consistent with above |

## Part (iv)

| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. if requirement is for part loads, delivering to one department en route to another might save time | B1 | answer should be valid and refer to specific situation of the DAA |
| e.g. if requirement is for whole loads then might not be relevant | B1 | |

## Part (v)

| Answer | Mark | Guidance |
|--------|------|----------|
| A directed network | B1 | |

---

Show LaTeX source

2 A government has just created a new ministry, the Ministry of Administrative Affairs. The ministry is to have four departments:\\
the Administration\\
the Bureaucracy\\
the Certification Service\\
the Duplication Section.\\
Each of these departments is to be established in a separate office on one of four existing sites. The diagram shows the direct journey times in minutes between these four sites.\\
\includegraphics[max width=\textwidth, alt={}, center]{52b8153f-e655-4852-a0f8-6f1c1e9c9170-3_342_403_721_829}\\
(i) Use Floyd's algorithm to find the shortest journey times between the four office sites.\\
(ii) Draw a network showing your shortest times.\\
(iii) Use appropriate algorithms to find upper and lower bounds for the optimum solution to the Travelling Salesperson Problem in the original network, briefly explaining the steps taken.\\
(iv) A van is to be organised to deliver bundles of paperwork between the departments. Why might the optimum solution to the TSP be useful in planning this, and why might it not be?\\
(v) Journeys to locations 2 and 3, from locations 1 and 4, are subject to a congestion charge which is equivalent in costing terms to 15 minutes of journey time. What sort of network would be needed to model this?

\hfill \mbox{\textit{OCR MEI D2 2011 Q2 [16]}}

This paper (4 questions)

View full paper

Q1 16 Q2 16 Q3 20 Q4 20