| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming maximin route |
| Difficulty | Moderate -0.3 This is a standard D2 dynamic programming question requiring straightforward application of the maximin algorithm with tabulation. Part (i) is definitional recall, part (ii) is routine backward recursion through a small network, and part (iii) requires simple inspection rather than formal DP. The question is slightly easier than average A-level because it's methodical application of a taught algorithm with no novel problem-solving required. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| (i) The route for which the minimum weight on the route is greatest | B1, B1, [2] | For identifying route minima; For identifying what has been maximised ('maximises the minimum' ⟹ B0 B1) |
| Answer | Marks | Guidance |
|---|---|---|
| Stage | State | Action |
| 1 | 0, 1, 2 | 0, 0, 0 |
| 0 | 1 | \(\min(16,18) = 16\) |
| 2 | \(\min(13,15) = 13\) | |
| \(\min(14,15) = 14\) | ||
| 2 | 0 | 1 |
| 2 | \(\min(13,15) = 13\) | |
| 1 | 1 | \(\min(18,15) = 15\) |
| 2 | ||
| 3 | 0 | 0 |
| 1 | \(\min(16,18) = 16\) | |
| B1, B1, [2] | Stage and state columns completed correctly; Action column completed correctly | |
| M1, A1 | For calculating minima for stage 2 state 0; For maximin values identified (may be implied from working seen for stage 3) | |
| M1, A1 | For calculating minima for stage 2 state 1; For maximin values identified (may be implied from working seen for stage 3) | |
| M1, A1, [6] | For calculating minima for stage 3; For maximin value identified; (Forwards working scores M0, M0, M0) |
| Answer | Marks | Guidance |
|---|---|---|
| Maximum load = 16 tonnes | —, B1, B1, B1, [3] | For first correct route; For second correct route; For 16 tonnes (with units) |
| Answer | Marks | Guidance |
|---|---|---|
| \((3; 0) - (2; 0) - (2; 1) - (1; 0) - (0; 0)\) | B1, B1, [2] | For 18; For this route |
(i) The route for which the minimum weight on the route is greatest | B1, B1, [2] | For identifying route minima; For identifying what has been maximised ('maximises the minimum' ⟹ B0 B1)
(ii)
| Stage | State | Action | Working | Maximin |
|-------|-------|--------|---------|---------|
| 1 | 0, 1, 2 | 0, 0, 0 | | 18, 15, 15 |
| | 0 | 1 | $\min(16,18) = 16$ | 16 |
| | | 2 | $\min(13,15) = 13$ | |
| | | | $\min(14,15) = 14$ | |
| 2 | 0 | 1 | $\min(19,18) = 18$ | 18 |
| | | 2 | $\min(13,15) = 13$ | |
| | 1 | 1 | $\min(18,15) = 15$ | |
| | | 2 | | |
| 3 | 0 | 0 | $\min(20,16) = 16$ | 16 |
| | | 1 | $\min(16,18) = 16$ | |
| B1, B1, [2] | Stage and state columns completed correctly; Action column completed correctly
| M1, A1 | For calculating minima for stage 2 state 0; For maximin values identified (may be implied from working seen for stage 3)
| M1, A1 | For calculating minima for stage 2 state 1; For maximin values identified (may be implied from working seen for stage 3)
| M1, A1, [6] | For calculating minima for stage 3; For maximin value identified; (Forwards working scores M0, M0, M0)
Maximin routes: $(3; 0) - (2; 0) - (1; 0) - (0; 0)$ or $(3; 0) - (2; 1) - (1; 0) - (0; 0)$
Maximum load = 16 tonnes | —, B1, B1, B1, [3] | For first correct route; For second correct route; For 16 tonnes (with units)
(iii) 18 tonnes
$(3; 0) - (2; 0) - (2; 1) - (1; 0) - (0; 0)$ | B1, B1, [2] | For 18; For this route
---2 A delivery company needs to transport heavy loads from its warehouse to a ferry port. Each of the roads that it can use has a bridge with a maximum weight limit. The directed network below represents the roads that can be used to get from the warehouse to the ferry port. Road junctions are labelled with (stage; state) labels. The weights on the arcs represent weight limits in tonnes.\\
\includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-03_896_1561_468_292}\\
(i) Explain what a maximin route is.\\
(ii) Set up a dynamic programming tabulation, working backwards from stage 1, to find the two maximin routes through the network. What is the maximum load that can be transported in one journey from the warehouse to the ferry port?\\
(iii) A new road is opened connecting ( $2 ; 0$ ) and ( $2 ; 1$ ). There is no bridge on this road so it does not restrict the weight of the load that can be carried. Using the new road, what is the maximum load that can be transported in one journey from the warehouse to the ferry port? State the route that the delivery company should use. (Do not attempt to apply dynamic programming in this part.)
\hfill \mbox{\textit{OCR D2 2006 Q2 [15]}}