| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 15 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming resource allocation |
| Difficulty | Standard +0.3 This is a standard D2 dynamic programming question requiring systematic application of the minimax algorithm through a network. While it involves multiple stages and careful bookkeeping, it follows a well-practiced procedure with no novel problem-solving required, making it easier than average for A-level. |
| Spec | 7.06a LP formulation: variables, constraints, objective function |
| 1 | 2 | 3 | 4 | |
| A | ||||
| B | ||||
| C | ||||
| D |
| 1 | 2 | 3 | 4 | |
| A | ||||
| B | ||||
| C | ||||
| D |
| 1 | 2 | 3 | 4 | |
| A | ||||
| B | ||||
| C | ||||
| D |
| B plays 1 | B plays 2 | B plays 3 | B plays 4 | |
| A plays 1 | - 3 | 2 | 5 | - 1 |
| A plays 2 | - 5 | 3 | 1 | - 1 |
| A plays 3 | - 2 | 5 | 4 | 2 |
| A plays 4 | 2 | - 3 | - 1 | 4 |
| - 3 | 2 | 5 |
| - 2 | 5 | 4 |
| 2 | - 3 | - 1 |
| 1 | 2 | 3 | 4 | 5 | |
| A | 25 | 31 | 27 | 29 | 35 |
| B | 29 | 33 | 40 | 35 | 37 |
| C | 28 | 29 | 35 | 36 | 37 |
| D | 34 | 35 | 36 | \(x\) | 41 |
| E | 36 | 35 | 32 | 31 | 33 |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| 1 | 2 | 3 | 4 | 5 | |
| A | |||||
| B | |||||
| C | |||||
| D | |||||
| E |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value |
| \(r\) | - 2 | - 6 | 1 | 1 | 0 | 0 | 40 |
| \(s\) | 2 | 3 | 2 | 0 | 1 | 0 | 80 |
| \(t\) | 1 | 2 | 2 | 0 | 0 | 1 | 50 |
| \(P\) | - 4 | - 2 | \(- k\) | 0 | 0 | 0 | 0 |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row Ops |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row Ops |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row Ops |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row Ops |
| \(P\) |
| b.v. | \(x\) | \(y\) | \(z\) | \(r\) | \(s\) | \(t\) | Value | Row Ops |
| \(P\) |
| Stage | State | Action | Destination | Value |
| 0 | I | IS | S | \(30 - 5 = 25 ^ { * }\) |
| Stage | State | Action | Destination | Value |
| END |
| Answer | Marks | Guidance |
|---|---|---|
| Country | Earnings | Travel cost to S |
| I | 30 | 5 |
| J | 29 | 3 |
| Answer | Marks |
|---|---|
| - Best = 55 (via I) | B1 |
| Answer | Marks |
|---|---|
| - Best = 56 (via I) | B1 |
| Answer | Marks |
|---|---|
| - Best = 57 (via I or J) | B1 |
| Answer | Marks |
|---|---|
| - Best = 74 (via G) | M1 A1 |
| Answer | Marks |
|---|---|
| - Best = 75 (via H) | A1 |
| Answer | Marks |
|---|---|
| - Best via A = 95 (A→E) | M1 A1 |
| Answer | Marks |
|---|---|
| - Best via B = 97 (B→E) | A1 |
| Answer | Marks |
|---|---|
| - Best via C = 96 (C→E) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Maximum expected income = £9700 | A1 | |
| Optimal schedule: S → B → E → H → I → S or S → B → E → H → J → S | A1 | Both routes required for full marks |
| Answer | Marks | Guidance |
|---|---|---|
| - The table headers: Stage | State | Action |
# Question 6: Dynamic Programming
## Stage 4 (Week 4): Countries I or J, returning to S
| Country | Earnings | Travel cost to S | Net value |
|---------|----------|-----------------|-----------|
| I | 30 | 5 | 25 |
| J | 29 | 3 | 26 |
**Best from I = 25, Best from J = 26**
---
## Stage 3 (Week 3): Countries F, G or H → to I or J
For each country in week 3, calculate: earnings − travel cost + best onward value
**From F:**
- F→I: 35 − 5 + 25 = 55
- F→J: 35 − 7 + 26 = 54
- Best = 55 (via I) | B1 |
**From G:**
- G→I: 36 − 5 + 25 = 56
- G→J: 36 − 7 + 26 = 55
- Best = 56 (via I) | B1 |
**From H:**
- H→I: 38 − 6 + 25 = 57
- H→J: 38 − 7 + 26 = 57
- Best = 57 (via I or J) | B1 |
---
## Stage 2 (Week 2): Countries D or E → to F, G or H
**From D:**
- D→F: 24 − 7 + 55 = 72
- D→G: 24 − 6 + 56 = 74
- D→H: 24 − 8 + 57 = 73
- Best = 74 (via G) | M1 A1 |
**From E:**
- E→F: 22 − 6 + 55 = 71
- E→G: 22 − 6 + 56 = 72
- E→H: 22 − 4 + 57 = 75
- Best = 75 (via H) | A1 |
---
## Stage 1 (Week 1): S → A, B or C → to D or E
**From A:**
- S→A→D: 27 − 3 − 6 + 74 = 92
- S→A→E: 27 − 3 − 4 + 75 = 95
- Best via A = 95 (A→E) | M1 A1 |
**From B:**
- S→B→D: 29 − 4 − 5 + 74 = 94
- S→B→E: 29 − 4 − 3 + 75 = 97
- Best via B = 97 (B→E) | A1 |
**From C:**
- S→C→D: 32 − 6 − 6 + 74 = 94
- S→C→E: 32 − 6 − 5 + 75 = 96
- Best via C = 96 (C→E) | A1 |
---
## Optimal Solution
**Maximum expected income = £9700** | A1 |
**Optimal schedule: S → B → E → H → I → S or S → B → E → H → J → S** | A1 | Both routes required for full marks |
I can see these are exam question pages, but the mark scheme itself is not shown in these images. What's shown are the **question papers** (the student answer booklet pages), not the mark scheme.
The images contain:
- **Question 2**: A game theory payoff matrix with players A and B each having 4 strategies
- **Question 3**: An assignment problem matrix with workers A–E and tasks 1–5, with an unknown value $x$ in position (D,4)
To provide the mark scheme content you're asking for, I would need the **actual mark scheme document** to be shared. The blank lined pages shown are simply where students write their answers.
If you can share the mark scheme pages, I would be happy to extract and format the content as requested.
I can see these are exam answer booklet pages (response sheets for students), not mark scheme pages. The images show blank answer grids, network flow diagrams, and simplex tableau templates where students write their answers.
I cannot extract a mark scheme from these pages because **no mark scheme content is present** in these images. What is shown includes:
- **Question 3 continued**: Blank 5×5 grids (rows A–E, columns 1–5) for student responses
- **Question 4**: A network flow diagram (Diagram 1) with nodes S, A, B, C, D, E, F, G, H, T and capacities/flows labeled, plus a blank copy (Diagram 2) for students to complete
- **Question 5**: A simplex tableau with initial values and blank tableaux for subsequent iterations
To obtain the actual mark scheme for this paper (which appears to be a Pearson/Edexcel Decision Mathematics paper, paper reference P51572A), you would need to access it directly from **Pearson's website** or **PMT (Physics & Maths Tutor)**, where official mark schemes are published after each exam series.
I can see these are answer/working pages from what appears to be a mathematics or decision mathematics exam paper (reference P51572A), but the pages shown are **blank answer pages** — they contain only the table structure and ruled lines for students to write their answers.
The only content visible is:
- The table headers: **Stage | State | Action | Destination | Value**
- One completed row: Stage 0, State I, Action IS, Destination S, Value $30 - 5 = 25^*$
- "Total 15 marks" and "Total for Paper: 75 marks"
**No mark scheme content is present in these images.** These are student answer booklet pages, not a mark scheme document.
To obtain the mark scheme for this paper (P51572A), you would need to access it through:
- **Pearson/Edexcel** website (qualifications.pearson.com)
- Your school/college's exam resources
- A revision resource provider
6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S , and will only return there after visiting the four countries. He will travel directly from one country to the next. He wishes to determine a schedule of four countries to visit.
Table 1 shows the countries he could visit each week.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & & & & \\
\hline
B & & & & \\
\hline
C & & & & \\
\hline
D & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & & & & \\
\hline
B & & & & \\
\hline
C & & & & \\
\hline
D & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 \\
\hline
A & & & & \\
\hline
B & & & & \\
\hline
C & & & & \\
\hline
D & & & & \\
\hline
\end{tabular}
\end{center}
2.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
& B plays 1 & B plays 2 & B plays 3 & B plays 4 \\
\hline
A plays 1 & - 3 & 2 & 5 & - 1 \\
\hline
A plays 2 & - 5 & 3 & 1 & - 1 \\
\hline
A plays 3 & - 2 & 5 & 4 & 2 \\
\hline
A plays 4 & 2 & - 3 & - 1 & 4 \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
- 3 & 2 & 5 \\
\hline
- 2 & 5 & 4 \\
\hline
2 & - 3 & - 1 \\
\hline
\end{tabular}
\end{center}
3.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & 25 & 31 & 27 & 29 & 35 \\
\hline
B & 29 & 33 & 40 & 35 & 37 \\
\hline
C & 28 & 29 & 35 & 36 & 37 \\
\hline
D & 34 & 35 & 36 & $x$ & 41 \\
\hline
E & 36 & 35 & 32 & 31 & 33 \\
\hline
\end{tabular}
\end{center}
(a) You may not need to use all of these tables
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
& 1 & 2 & 3 & 4 & 5 \\
\hline
A & & & & & \\
\hline
B & & & & & \\
\hline
C & & & & & \\
\hline
D & & & & & \\
\hline
E & & & & & \\
\hline
\end{tabular}
\end{center}
4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-18_1056_1572_1450_185}
\captionsetup{labelformat=empty}
\caption{Diagram 1}
\end{center}
\end{figure}
Maximum flow along SBET: $\_\_\_\_$
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-19_1043_1572_1505_187}
\captionsetup{labelformat=empty}
\caption{Diagram 2}
\end{center}
\end{figure}
5.
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & - 2 & - 6 & 1 & 1 & 0 & 0 & 40 \\
\hline
$s$ & 2 & 3 & 2 & 0 & 1 & 0 & 80 \\
\hline
$t$ & 1 & 2 & 2 & 0 & 0 & 1 & 50 \\
\hline
$P$ & - 4 & - 2 & $- k$ & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
You may not need to use all of these tableaux
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row Ops \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row Ops \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row Ops \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row Ops \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value & Row Ops \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
& & & & & & & & \\
\hline
$P$ & & & & & & & & \\
\hline
\end{tabular}
\end{center}
6.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Destination & Value \\
\hline
0 & I & IS & S & $30 - 5 = 25 ^ { * }$ \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Destination & Value \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{|l|l|}
\hline
\hline
END & \\
\hline
\end{tabular}
\end{center}
\hfill \mbox{\textit{Edexcel D2 2018 Q6 [15]}}