| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2023 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming resource allocation |
| Difficulty | Standard +0.3 This is a straightforward dynamic programming problem with a clear 4-stage structure, small state space (2-3 options per stage), and routine calculations of income minus costs. The problem requires systematic application of the DP algorithm but no novel insight or complex optimization—easier than average A-level questions. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Week | 1 | 2 | 3 | 4 |
| Possible countries to visit | A or B | C, D or E | F or G | H, I or J |
| Country | A | B | C | D | E | F | G | H | I | J |
| Earnings in \(\boldsymbol { \pounds } \mathbf { 1 0 0 s }\) | 47 | 45 | 48 | 47 | 49 | 44 | 45 | 47 | 49 | 48 |
| A | B | C | D | E | F | G | H | I | J | |
| S | 5 | 2 | 7 | 8 | 8 | |||||
| A | 3 | 4 | 5 | |||||||
| B | 5 | 4 | 6 | |||||||
| C | 7 | 5 | ||||||||
| D | 6 | 7 | ||||||||
| E | 7 | 6 | ||||||||
| F | 6 | 7 | 8 | |||||||
| G | 7 | 8 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Stage 1: State H, action HS→S, value \(47-7=40^*\); State I, action IS→S, value \(49-8=41^*\); State J, action JS→S, value \(48-8=40^*\) | B1 | 3.1a |
| Stage 2: State F: FH→H \(44-6+40=78^*\); FI→I \(44-7+41=78^*\); FJ→J \(44-8+40=76\). State G: GH→H \(45-7+40=78\); GI→I \(45-8+41=78\); GJ→J \(45-6+40=79^*\) | M1, A1, A1 | 3.1a, 1.1b, 1.1b |
| Stage 3: State C: CF→F \(48-7+78=119\); CG→G \(48-5+79=122^*\). State D: DF→F \(47-6+78=119^*\); DG→G \(47-7+79=119^*\). State E: EF→F \(49-7+78=120\); EG→G \(49-6+79=122^*\) | M1, A1ft, A1 | 1.1b, 1.1b, 1.1b |
| Stage 4: State A: AC→C \(47-3+122=166^*\); AD→D \(47-4+119=162\); AE→E \(47-5+122=164\). State B: BC→C \(45-5+122=162^*\); BD→D \(45-4+119=160\); BE→E \(45-6+122=161\) | M1, A1ft, A1 | 1.1b, 1.1b, 1.1b |
| Stage 5: State S: SA→A \(-5+166=161^*\); SB→B \(-2+162=160\) | A1 | 1.1b |
| Optimal schedule is SACGJS | B1 | 2.2a |
| Optimal expected income (£) 16 100 | B1 | 3.2a |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(H\): \(-7 = -7^*\), \(I\): \(-8 = -8^*\), \(J\): \(-8 = -8^*\) | B1 | CAO Stage 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(F\): FH \(47-6-7=34^*\), FI \(49-7-8=34^*\), FJ \(48-8-8=32\); \(G\): GH \(47-7-7=33\), GI \(49-8-8=33\), GJ \(48-6-8=34^*\) | M1 | Second stage completed, at least six rows |
| Any one state correct with no extra rows for that state | A1 | |
| Both states correct with no extra rows for Stage 2 | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(C\): CF \(44-7+34=71\), CG \(45-5+34=74^*\); \(D\): DF \(44-6+34=72^*\), DG \(45-7+34=72^*\); \(E\): EF \(44-7+34=71\), EG \(45-6+34=73^*\) | M1 | Third stage completed, at least six rows |
| Any two states correct, ft optimal values from Stage 2, no extra rows | A1ft | |
| All three states correct for Stage 3, no extra rows | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(A\): AC \(48-3+74=119^*\), AD \(47-4+72=115\), AE \(49-5+73=117\); \(B\): BC \(48-5+74=117^*\), BD \(47-4+72=115\), BE \(49-6+73=116\) | M1 | Fourth stage completed, at least six rows |
| Any one state correct, ft optimal values from Stage 3, no extra rows | A1ft | |
| Both states correct, no extra rows | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(S\): SA \(47-5+119=161^*\), SB \(45-2+117=160\) | A1 | Final state correct, no extra rows |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Optimal schedule is SACGJS | B1 | Correct route, dependent on all previous M marks; start/finish at S may not be stated |
| Optimal expected income £16,100 | B1 | CAO, dependent on all M marks; units not required; but not for 161 |
## Question 6:
| Answer/Working | Mark | Guidance |
|---|---|---|
| Stage 1: State H, action HS→S, value $47-7=40^*$; State I, action IS→S, value $49-8=41^*$; State J, action JS→S, value $48-8=40^*$ | B1 | 3.1a |
| Stage 2: State F: FH→H $44-6+40=78^*$; FI→I $44-7+41=78^*$; FJ→J $44-8+40=76$. State G: GH→H $45-7+40=78$; GI→I $45-8+41=78$; GJ→J $45-6+40=79^*$ | M1, A1, A1 | 3.1a, 1.1b, 1.1b |
| Stage 3: State C: CF→F $48-7+78=119$; CG→G $48-5+79=122^*$. State D: DF→F $47-6+78=119^*$; DG→G $47-7+79=119^*$. State E: EF→F $49-7+78=120$; EG→G $49-6+79=122^*$ | M1, A1ft, A1 | 1.1b, 1.1b, 1.1b |
| Stage 4: State A: AC→C $47-3+122=166^*$; AD→D $47-4+119=162$; AE→E $47-5+122=164$. State B: BC→C $45-5+122=162^*$; BD→D $45-4+119=160$; BE→E $45-6+122=161$ | M1, A1ft, A1 | 1.1b, 1.1b, 1.1b |
| Stage 5: State S: SA→A $-5+166=161^*$; SB→B $-2+162=160$ | A1 | 1.1b |
| Optimal schedule is SACGJS | B1 | 2.2a |
| Optimal expected income (£) 16 100 | B1 | 3.2a |
## Question 6:
**Stage 1 (working backwards):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $H$: $-7 = -7^*$, $I$: $-8 = -8^*$, $J$: $-8 = -8^*$ | B1 | CAO Stage 1 |
**Stage 2:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $F$: FH $47-6-7=34^*$, FI $49-7-8=34^*$, FJ $48-8-8=32$; $G$: GH $47-7-7=33$, GI $49-8-8=33$, GJ $48-6-8=34^*$ | M1 | Second stage completed, at least six rows |
| Any one state correct with no extra rows for that state | A1 | |
| Both states correct with no extra rows for Stage 2 | A1 | |
**Stage 3:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $C$: CF $44-7+34=71$, CG $45-5+34=74^*$; $D$: DF $44-6+34=72^*$, DG $45-7+34=72^*$; $E$: EF $44-7+34=71$, EG $45-6+34=73^*$ | M1 | Third stage completed, at least six rows |
| Any two states correct, ft optimal values from Stage 2, no extra rows | A1ft | |
| All three states correct for Stage 3, no extra rows | A1 | |
**Stage 4:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $A$: AC $48-3+74=119^*$, AD $47-4+72=115$, AE $49-5+73=117$; $B$: BC $48-5+74=117^*$, BD $47-4+72=115$, BE $49-6+73=116$ | M1 | Fourth stage completed, at least six rows |
| Any one state correct, ft optimal values from Stage 3, no extra rows | A1ft | |
| Both states correct, no extra rows | A1 | |
**Stage 5:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $S$: SA $47-5+119=161^*$, SB $45-2+117=160$ | A1 | Final state correct, no extra rows |
**Final answers:**
| Answer | Mark | Guidance |
|--------|------|----------|
| Optimal schedule is SACGJS | B1 | Correct route, dependent on all previous M marks; start/finish at S may not be stated |
| Optimal expected income £16,100 | B1 | CAO, dependent on all M marks; units not required; but not for 161 |
---6. Polly is a motivational speaker who is planning her engagements for the next four weeks.
Polly will
\begin{itemize}
\item visit four different countries in these four weeks
\item visit just one country each week
\item leave from her home, S , and return there only after visiting the four countries
\item travel directly from one country to the next
\end{itemize}
Polly wishes to determine a schedule of four countries to visit.\\
Table 1 shows the countries Polly could visit each week.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
Week & 1 & 2 & 3 & 4 \\
\hline
Possible countries to visit & A or B & C, D or E & F or G & H, I or J \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
Table 2 shows the speaker fee, in $\pounds 100$ s, Polly would expect to earn in each country.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | c | }
\hline
Country & A & B & C & D & E & F & G & H & I & J \\
\hline
Earnings in $\boldsymbol { \pounds } \mathbf { 1 0 0 s }$ & 47 & 45 & 48 & 47 & 49 & 44 & 45 & 47 & 49 & 48 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
Table 3 shows the cost, in $\pounds 100$ s, of travelling between the countries.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
& A & B & C & D & E & F & G & H & I & J \\
\hline
S & 5 & 2 & & & & & & 7 & 8 & 8 \\
\hline
A & & & 3 & 4 & 5 & & & & & \\
\hline
B & & & 5 & 4 & 6 & & & & & \\
\hline
C & & & & & & 7 & 5 & & & \\
\hline
D & & & & & & 6 & 7 & & & \\
\hline
E & & & & & & 7 & 6 & & & \\
\hline
F & & & & & & & & 6 & 7 & 8 \\
\hline
G & & & & & & & & 7 & 8 & 6 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 3}
\end{center}
\end{table}
Polly's expected income is the value of the speaker fee minus the cost of travel.\\
She wants to find a schedule that maximises her total expected income for the four weeks.
Use dynamic programming to determine the optimal schedule. Complete the table provided in the answer book and state the maximum expected income.\\
(13)\\
\hfill \mbox{\textit{Edexcel FD2 2023 Q6 [13]}}