| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2012 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.5 This is a standard textbook dynamic programming question with a straightforward backward pass algorithm. While it requires systematic tabulation and multiple calculations, the method is entirely procedural with no problem-solving insight needed—students simply follow the taught algorithm to fill in the table and trace back the optimal path. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| Stage | State | From | Calculation | Value |
| 1 | G | \(T\) | ||
| H | \(T\) | |||
| I | \(T\) | |||
| 2 | D | G | ||
| \(H\) | ||||
| E | G | |||
| \(H\) | ||||
| I | ||||
| \(F\) | \(H\) | |||
| I | ||||
| 3 | ||||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(G\): from \(T\), value \(= 15\) | B1 | |
| \(H\): from \(T\), value \(= 17\) | B1 | |
| \(I\): from \(T\), value \(= 26\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(D\): from \(G\): \(6+15=21\); from \(H\): \(-3+17=14\); max \(= 21\) (via \(G\)) | M1 | Method for combining edge weight with stage 1 value |
| \(E\): from \(G\): \(3+15=18\); from \(H\): \(-6+17=11\); from \(I\): \(-13+26=13\); max \(= 18\) (via \(G\)) | A1 | |
| \(F\): from \(H\): \(-7+17=10\); from \(I\): \(-14+26=12\); max \(= 12\) (via \(I\)) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A\): from \(D\): \(-4+21=17\); from \(E\): \(12+18=30\); max \(= 30\) (via \(E\)) | M1 | Method for stage 3 calculations |
| \(B\): from \(D\): \(16+21=37\); from \(E\): \(12+18=30\); from \(F\): \(18+12=30\); max \(= 37\) (via \(D\)) | A1 | |
| \(C\): from \(D\): \(12+21=33\); from \(E\): \(14+18=32\); from \(F\): \(13+12=25\); max \(= 33\) (via \(D\)) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(S\): from \(A\): \(12+30=42\); from \(B\): \(-2+37=35\); from \(C\): \(3+33=36\); max \(= 42\) (via \(A\)) | M1A1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Maximum profit is £42 million | B1 | ft from their working |
| Path: \(S \to A \to E \to G \to T\) | B1 | Must be complete path |
| (No alternative paths with value 42) | B1 | All correct paths stated |
# Question 5:
## Part (a):
**Stage 1:**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $G$: from $T$, value $= 15$ | B1 | |
| $H$: from $T$, value $= 17$ | B1 | |
| $I$: from $T$, value $= 26$ | B1 | |
**Stage 2:**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $D$: from $G$: $6+15=21$; from $H$: $-3+17=14$; max $= 21$ (via $G$) | M1 | Method for combining edge weight with stage 1 value |
| $E$: from $G$: $3+15=18$; from $H$: $-6+17=11$; from $I$: $-13+26=13$; max $= 18$ (via $G$) | A1 | |
| $F$: from $H$: $-7+17=10$; from $I$: $-14+26=12$; max $= 12$ (via $I$) | A1 | |
**Stage 3:**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A$: from $D$: $-4+21=17$; from $E$: $12+18=30$; max $= 30$ (via $E$) | M1 | Method for stage 3 calculations |
| $B$: from $D$: $16+21=37$; from $E$: $12+18=30$; from $F$: $18+12=30$; max $= 37$ (via $D$) | A1 | |
| $C$: from $D$: $12+21=33$; from $E$: $14+18=32$; from $F$: $13+12=25$; max $= 33$ (via $D$) | A1 | |
**Stage 4:**
| Answer | Marks | Guidance |
|--------|-------|----------|
| $S$: from $A$: $12+30=42$; from $B$: $-2+37=35$; from $C$: $3+33=36$; max $= 42$ (via $A$) | M1A1 | cao |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum profit is £42 million | B1 | ft from their working |
| Path: $S \to A \to E \to G \to T$ | B1 | Must be complete path |
| (No alternative paths with value 42) | B1 | All correct paths stated |
---5 A firm is considering various strategies for development over the next few years. In the network, the number on each edge is the expected profit, in millions of pounds, moving from one year to the next. A negative number indicates a loss because of building costs or other expenses. Each path from $S$ to $T$ represents a complete strategy.\\
\includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-12_748_1575_559_228}
\begin{enumerate}[label=(\alph*)]
\item By completing the table on the page opposite, or otherwise, use dynamic programming working backwards from $\boldsymbol { T }$ to find the maximum weight of all paths from $S$ to $T$.
\item State the overall maximum profit and the paths from $S$ to $T$ corresponding to this maximum profit.
(a)
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & From & Calculation & Value \\
\hline
1 & G & $T$ & & \\
\hline
& H & $T$ & & \\
\hline
& I & $T$ & & \\
\hline
& & & & \\
\hline
2 & D & G & & \\
\hline
& & $H$ & & \\
\hline
& E & G & & \\
\hline
& & $H$ & & \\
\hline
& & I & & \\
\hline
& $F$ & $H$ & & \\
\hline
& & I & & \\
\hline
& & & & \\
\hline
3 & & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
\end{tabular}
\end{center}
(b)
Maximum profit is £ $\_\_\_\_$ million
Corresponding paths from $S$ to $T$ $\_\_\_\_$
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2012 Q5 [9]}}