Standard +0.3 This is a straightforward application of the dynamic programming algorithm to find a maximin route. Part (a) tests basic definition recall (2 marks), while part (b) requires systematic table completion following a standard algorithm taught in D2. The method is algorithmic rather than requiring problem-solving insight, making it slightly easier than average but more involved than pure recall.
4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.
(2)
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376}
A maximin route from L to R is to be found through the staged network shown above.
(b) Use dynamic programming to complete a table below and hence find a maximin route.
(10) (Total 12 marks)
(a) For each row the element in column \(x\) must be less than the element in column \(y\).
B2,1,01
2
(b) Row minimum: \([2,4,3]\) row maximum \(= 4\); Column maximum \(\{6,5,6\}\) column minimum \(= 5\); \(4 \neq 5\) so not stable
M1, A1, A1
3
(c) Row 3 dominates row 1, so matrix reduces to:
Answer
Marks
Guidance
M1
M2
M3
L2
4
5
L3
6
4
Let Liz play 2 with probability \(p\) and 3 with probability \((1-p)\)
If Mark plays 1: Liz's gain is \(4p + 6(1-p) = 6 - 2p\)
If Mark plays 2: Liz's gain is \(5p + 4(1-p) = 4 + p\)
If Mark plays 3: Liz's gain is \(6p + 3(1-p) = 3 + 3p\)
Answer
Marks
Guidance
M1
A1
3
Graph shows three lines intersecting. From \(4 + p = 6 - 2p\): \(p = \frac{2}{3}\)
B2,1,0, M1A1
2, 4
(d) Liz should play row 1 – never, row 2 – \(\frac{2}{3}\) of the time, row 3 – \(\frac{1}{3}\) of the time and the value of the game is \(4\frac{2}{3}\) to her. Row 3 no longer dominates row 1 and so row 1 cannot be deleted. Use Simplex (linear programming).
B1, B1
1, 2
**(a)** For each row the element in column $x$ must be less than the element in column $y$. | B2,1,01 | 2 |
**(b)** Row minimum: $[2,4,3]$ row maximum $= 4$; Column maximum $\{6,5,6\}$ column minimum $= 5$; $4 \neq 5$ so not stable | M1, A1, A1 | 3 |
**(c)** Row 3 dominates row 1, so matrix reduces to:
| | M1 | M2 | M3 |
|----|----|----|----|
| L2 | 4 | 5 | 6 |
| L3 | 6 | 4 | 3 |
Let Liz play 2 with probability $p$ and 3 with probability $(1-p)$
If Mark plays 1: Liz's gain is $4p + 6(1-p) = 6 - 2p$
If Mark plays 2: Liz's gain is $5p + 4(1-p) = 4 + p$
If Mark plays 3: Liz's gain is $6p + 3(1-p) = 3 + 3p$
| | M1 | A1 | 3 |
Graph shows three lines intersecting. From $4 + p = 6 - 2p$: $p = \frac{2}{3}$ | B2,1,0, M1A1 | 2, 4 |
**(d)** Liz should play row 1 – never, row 2 – $\frac{2}{3}$ of the time, row 3 – $\frac{1}{3}$ of the time and the value of the game is $4\frac{2}{3}$ to her. Row 3 no longer dominates row 1 and so row 1 cannot be deleted. Use Simplex (linear programming). | B1, B1 | 1, 2 |
4. (a) Explain the difference between a maximin route and a minimax route in dynamic programming.\\
(2)\\
\includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-2_533_1356_667_376}
A maximin route from L to R is to be found through the staged network shown above.\\
(b) Use dynamic programming to complete a table below and hence find a maximin route.\\
(10) (Total 12 marks)\\
\hfill \mbox{\textit{Edexcel D2 2008 Q4 [12]}}