| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2015 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming minimax route |
| Difficulty | Moderate -0.5 This is a standard A-level Decision Mathematics dynamic programming question requiring systematic application of the minimax algorithm working backwards through a network. While it requires careful bookkeeping and understanding of the minimax criterion (minimizing maximum values), it follows a well-practiced algorithmic procedure with no novel problem-solving required. Part (b) adds a minor variation but uses the same technique. Slightly easier than average due to its purely procedural nature. |
| Spec | 7.01d Multiplicative principle: arrangements of n distinct objects |
| Stage | State | From | Value |
| 1 | H | \(K\) | |
| I | \(K\) | ||
| \(J\) | \(K\) | ||
| 2 | |||
| Jose | |||
| \cline { 2 - 4 } | Strategy | C | D |
| \cline { 2 - 4 } Arsene | A | \(x + 3\) | 1 |
| \cline { 2 - 4 } | B | \(x + 1\) | 3 |
| \cline { 2 - 4 } | |||
| \cline { 2 - 4 } | |||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage 1: \(H \to K = 2.7\); \(I \to K = 2.3\); \(J \to K = 2.5\) | B1 | |
| Stage 2 states \(E, F, G\): correct from/value entries | M1 | |
| \(E\): via \(H\): \(\max(2.1, 2.7)=2.7\); via \(I\): \(\max(2.5, 2.3)=2.5^*\); value \(= 2.5\), from \(I\) | A1 | |
| \(F\): via \(H\): \(\max(2.8,2.7)=2.8\); via \(I\): \(\max(2.4,2.3)=2.4^*\); via \(J\): \(\max(2.6,2.5)=2.6\); value \(=2.4\), from \(I\) | A1 | |
| \(G\): via \(I\): \(\max(2.6,2.3)=2.6\); via \(J\): \(\max(2.9,2.5)=2.9\); value \(=2.6\), from \(I\) | A1 | |
| Stage 3 states \(B, C, D\): correct entries | M1 | |
| \(B\): via \(E\): \(\max(2.8,2.5)=2.8\); via \(F\): \(\max(2.8,2.4)=2.8\); value \(=2.8\) | A1 | |
| \(C\): via \(E\): \(\max(2.7,2.5)=2.7\); via \(F\): \(\max(2.4,2.4)=2.4^*\); via \(G\): \(\max(2.8,2.6)=2.8\); value \(=2.4\), from \(F\) | A1 | |
| \(D\): via \(F\): \(\max(2.8,2.4)=2.8\); via \(G\): \(\max(2.7,2.6)=2.7^*\); value \(=2.7\), from \(G\) | A1 | |
| Stage 4 (from \(A\)): via \(B\): \(\max(1.9,2.8)=2.8\); via \(C\): \(\max(1.8,2.4)=2.4^*\); via \(D\): \(\max(2.0,2.7)=2.7\); optimal value \(=2.4\) | B1 | |
| Optimal route: \(A \to C \to F \to I \to K\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| New optimal route: \(A \to C \to E \to I \to K\) or \(A \to D \to G \to I \to K\) | B1 | |
| Maximum altitude \(= 2.7\) (for \(A \to D \to G \to I \to K\)) or \(2.5\) (for \(A \to C \to E \to I \to K\)); best is \(A \to C \to E \to I \to K\) with max altitude \(2.5\) | B1 |
# Question 5:
## Part (a): Dynamic programming table
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage 1: $H \to K = 2.7$; $I \to K = 2.3$; $J \to K = 2.5$ | B1 | |
| Stage 2 states $E, F, G$: correct from/value entries | M1 | |
| $E$: via $H$: $\max(2.1, 2.7)=2.7$; via $I$: $\max(2.5, 2.3)=2.5^*$; value $= 2.5$, from $I$ | A1 | |
| $F$: via $H$: $\max(2.8,2.7)=2.8$; via $I$: $\max(2.4,2.3)=2.4^*$; via $J$: $\max(2.6,2.5)=2.6$; value $=2.4$, from $I$ | A1 | |
| $G$: via $I$: $\max(2.6,2.3)=2.6$; via $J$: $\max(2.9,2.5)=2.9$; value $=2.6$, from $I$ | A1 | |
| Stage 3 states $B, C, D$: correct entries | M1 | |
| $B$: via $E$: $\max(2.8,2.5)=2.8$; via $F$: $\max(2.8,2.4)=2.8$; value $=2.8$ | A1 | |
| $C$: via $E$: $\max(2.7,2.5)=2.7$; via $F$: $\max(2.4,2.4)=2.4^*$; via $G$: $\max(2.8,2.6)=2.8$; value $=2.4$, from $F$ | A1 | |
| $D$: via $F$: $\max(2.8,2.4)=2.8$; via $G$: $\max(2.7,2.6)=2.7^*$; value $=2.7$, from $G$ | A1 | |
| Stage 4 (from $A$): via $B$: $\max(1.9,2.8)=2.8$; via $C$: $\max(1.8,2.4)=2.4^*$; via $D$: $\max(2.0,2.7)=2.7$; optimal value $=2.4$ | B1 | |
| Optimal route: $A \to C \to F \to I \to K$ | B1 | |
## Part (b): CF blocked
| Answer | Marks | Guidance |
|--------|-------|----------|
| New optimal route: $A \to C \to E \to I \to K$ or $A \to D \to G \to I \to K$ | B1 | |
| Maximum altitude $= 2.7$ (for $A \to D \to G \to I \to K$) or $2.5$ (for $A \to C \to E \to I \to K$); best is $A \to C \to E \to I \to K$ with max altitude $2.5$ | B1 | |5 Tom is going on a driving holiday and wishes to drive from $A$ to $K$.\\
The network below shows a system of roads. The number on each edge represents the maximum altitude of the road, in hundreds of metres above sea level.
Tom wants to ensure that the maximum altitude of any road along the route from $A$ to $K$ is minimised.\\
\includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-14_1522_1363_660_342}
\begin{enumerate}[label=(\alph*)]
\item Working backwards from $\boldsymbol { K }$, use dynamic programming to find the optimal route when driving from $A$ to $K$.
You must complete the table opposite as your solution.
\item Tom finds that the road $C F$ is blocked. Find Tom's new optimal route and the maximum altitude of any road on this route.\\[0pt]
[2 marks]
\section*{Answer space for question 5}
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Stage & State & From & Value \\
\hline
1 & H & $K$ & \\
\hline
& I & $K$ & \\
\hline
& $J$ & $K$ & \\
\hline
2 & & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
& & & \\
\hline
\end{tabular}
\end{center}
(a) Optimal route is $\_\_\_\_$\\
(b) Tom's route is $\_\_\_\_$\\
Maximum altitude is $\_\_\_\_$
Figure 4 below shows a network of pipes.\\
The capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{b0f9523e-51dd-495f-99ec-4724243b5619-18_1039_1623_561_191}
\end{center}
\end{figure}
(a) Find the value of the initial flow.\\
(b) (i) Use the initial flow and the labelling procedure on Figure 5 to find the maximum flow through the network. You should indicate any flow-augmenting routes in the table and modify the potential increases and decreases of the flow on the network.\\
(ii) State the value of the maximum flow and, on Figure 6, illustrate a possible flow along each edge corresponding to this maximum flow.
\item Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut.
\item On a particular day, there is a restriction at vertex $G$ which allows a maximum flow through $G$ of 30 .
Find, by inspection, the maximum flow through the network on this day.\\
(a) Initial flow $=$ $\_\_\_\_$\\
(b)(i) Figure 5\\
\includegraphics[max width=\textwidth, alt={}, center]{b0f9523e-51dd-495f-99ec-4724243b5619-19_2158_1559_543_296}\\
$7 \quad$ Arsene and Jose play a zero-sum game. The game is represented by the following pay-off matrix for Arsene, where $x$ is a constant.
The value of the game is 2.5 .
\begin{center}
\begin{tabular}{ l | c | c | c | }
\multicolumn{4}{c}{Jose} \\
\cline { 2 - 4 }
& Strategy & C & D \\
\cline { 2 - 4 }
Arsene & A & $x + 3$ & 1 \\
\cline { 2 - 4 }
& B & $x + 1$ & 3 \\
\cline { 2 - 4 }
& & & \\
\cline { 2 - 4 }
\end{tabular}
\end{center}
(a) Find the optimal mixed strategy for Arsene.\\
(b) Find the value of $x$.
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-22_1636_1707_1071_153}
\end{center}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{b0f9523e-51dd-495f-99ec-4724243b5619-24_2288_1705_221_155}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2015 Q5 [11]}}