| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | January |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.8 This is a standard textbook application of dynamic programming with a partially completed table provided. Students follow a mechanical backward-working algorithm with clear structure. While it requires careful arithmetic with negative numbers and systematic table completion, it demands no problem-solving insight or novel approach—just execution of a learned procedure. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| Stage | State | From | Value | |
| 1 | I | \(T\) | -7 | |
| \(J\) | \(T\) | -6 | ||
| \(K\) | \(T\) | -5 | ||
| 2 | \(E\) | \(I\) | \(- 7 - 4 = - 11\) | |
| F | I | |||
| \(J\) | ||||
| G | I | |||
| \(J\) | ||||
| \(K\) | ||||
| \(H\) | \(K\) | |||
| 3 | ||||
| Answer | Marks | Guidance |
|---|---|---|
| State | From | Value |
| \(I\) | \(T\) | \(-7\) |
| \(J\) | \(T\) | \(-6\) |
| \(K\) | \(T\) | \(-5\) |
| Answer | Marks | Guidance |
|---|---|---|
| State | From | Value |
| \(E\) | \(I\) | \(-7-4=-11\) |
| \(F\) | \(I\) | \(-7-2=-9\) |
| \(J\) | \(-6-2=-8\), choose \(J\), value \(-8\) | |
| \(G\) | \(I\) | \(-7+(-1)=-8\) |
| \(J\) | \(-6+7=1\) | |
| \(K\) | \(-5-1=-6\), choose \(I\), value \(-8\) | B1 |
| \(H\) | \(K\) | \(-5+4=-1\) |
| Answer | Marks | Guidance |
|---|---|---|
| \(A\): from \(E\): \(-11+5=-6\); from \(F\): \(-8-4=-12\); choose \(F\), value \(-12\) | B1 | |
| \(B\): from \(E\): \(-11-2=-13\); from \(F\): \(-8-2=-10\); from \(G\): \(-8+6=-2\); choose \(E\), value \(-13\) | B1 | |
| \(C\): from \(F\): \(-8-3\) or from \(G\): \(-8-3=-11\); from \(H\): \(-1-5=-6\); choose \(G\) (or \(F\)), value \(-11\) | ||
| \(D\): from \(G\): \(-8-5=-13\); from \(H\): \(-1-3=-4\); choose \(G\), value \(-13\) | B1 | (at least 3 correct in stage 3) |
| Answer | Marks |
|---|---|
| \(S\): from \(A\): \(23+(-12)=11\); from \(B\): \(28+(-13)=15\); from \(C\): \(25+(-11)=14\); from \(D\): \(25+(-13)=12\); minimum is \(11\) via \(A\) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Minimum cost = £11 | B1 | |
| Path: \(SBFEJT\) (i.e. \(S \to B \to F \to E \to J \to T\) — accept equivalent correct traceback) | B1 ft | |
| Also accept \(SAFJT\): \(23-12+5-8-6... \) — check traceback gives 11 | B1 | (both paths if two optimal) |
# Question 5:
## Part (a):
**Stage 1:**
| State | From | Value |
|-------|------|-------|
| $I$ | $T$ | $-7$ |
| $J$ | $T$ | $-6$ |
| $K$ | $T$ | $-5$ |
**Stage 2:**
| State | From | Value |
|-------|------|-------|
| $E$ | $I$ | $-7-4=-11$ | B1 | cao |
| $F$ | $I$ | $-7-2=-9$ | B1 | |
| | $J$ | $-6-2=-8$, choose $J$, value $-8$ | | |
| $G$ | $I$ | $-7+(-1)=-8$ | | |
| | $J$ | $-6+7=1$ | | |
| | $K$ | $-5-1=-6$, choose $I$, value $-8$ | B1 | |
| $H$ | $K$ | $-5+4=-1$ | B1 | cao |
**Stage 3 working:**
$A$: from $E$: $-11+5=-6$; from $F$: $-8-4=-12$; choose $F$, value $-12$ | B1 |
$B$: from $E$: $-11-2=-13$; from $F$: $-8-2=-10$; from $G$: $-8+6=-2$; choose $E$, value $-13$ | B1 |
$C$: from $F$: $-8-3$ or from $G$: $-8-3=-11$; from $H$: $-1-5=-6$; choose $G$ (or $F$), value $-11$ | |
$D$: from $G$: $-8-5=-13$; from $H$: $-1-3=-4$; choose $G$, value $-13$ | B1 | (at least 3 correct in stage 3) |
**Stage 4:**
$S$: from $A$: $23+(-12)=11$; from $B$: $28+(-13)=15$; from $C$: $25+(-11)=14$; from $D$: $25+(-13)=12$; minimum is $11$ via $A$ | M1 A1 |
---
## Part (b):
Minimum cost = **£11** | B1 |
Path: $SBFEJT$ (i.e. $S \to B \to F \to E \to J \to T$ — accept equivalent correct traceback) | B1 ft |
Also accept $SAFJT$: $23-12+5-8-6... $ — check traceback gives 11 | B1 | (both paths if two optimal) |
---5 Each path from $S$ to $T$ in the network below represents a possible way of using the internet to buy a ticket for a particular event. The number on each edge represents a charge, in pounds, with a negative value representing a discount. For example, the path SAEIT represents a ticket costing $23 + 5 - 4 - 7 = 17$ pounds.\\
\includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-12_1023_1330_540_350}
\begin{enumerate}[label=(\alph*)]
\item By working backwards from $\boldsymbol { T }$ and completing the table on Figure 4, use dynamic programming to find the minimum weight of all paths from $S$ to $T$.
\item State the minimum cost of a ticket for the event and the paths corresponding to this minimum cost.\\
(3 marks)
(a)
\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & From & Value & \\
\hline
1 & I & $T$ & -7 & \\
\hline
& $J$ & $T$ & -6 & \\
\hline
& $K$ & $T$ & -5 & \\
\hline
& & & & \\
\hline
2 & $E$ & $I$ & $- 7 - 4 = - 11$ & \\
\hline
& F & I & & \\
\hline
& & $J$ & & \\
\hline
& G & I & & \\
\hline
& & $J$ & & \\
\hline
& & $K$ & & \\
\hline
& $H$ & $K$ & & \\
\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}
\end{table}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2011 Q5 [9]}}