| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2011 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming order sequencing |
| Difficulty | Moderate -0.5 This is a standard textbook dynamic programming problem with a clear 4-stage structure, straightforward state transitions, and simple arithmetic (profit = orders - travel costs). While it requires systematic working through multiple stages, it follows the exact template taught in D2 with no novel insights needed—slightly easier than average due to its mechanical nature and small problem size. |
| Spec | 7.05a Critical path analysis: activity on arc networks |
| Week | Week 1 | Week 2 | Week 3 | Week 4 |
| Possible countries | A or B | C, D or E | F or G | H or I |
| Country | A | B | C | D | E | F | G | H | I |
| Value of expected orders in \(\pounds 100\) s | 22 | 17 | 42 | 41 | 39 | 29 | 27 | 36 | 38 |
| Travel costs in £100s | A | B | C | D | E | F | G | H | I |
| London | 5 | 3 | 5 | 4 | |||||
| A | 5 | 4 | 2 | ||||||
| B | 4 | 4 | 3 | ||||||
| C | 6 | 5 | |||||||
| D | 6 | 3 | |||||||
| E | 4 | 4 | |||||||
| F | 6 | 7 | |||||||
| G | 5 | 6 |
# Question 7: Dynamic Programming
## (a) Complete Table for Optimal Expected Income
**Marks: (11)**
**M1** for correctly structuring dynamic programming table with stages (weeks) and states (countries)
**M1** for calculating expected income values: value of orders minus travel cost
**M1–M4** for correctly completing Week 4 values (4 marks distributed for accuracy)
**M1–M4** for correctly completing Week 3 values with recursive calculations (4 marks distributed for accuracy)
**M1** for correctly completing Week 2 values and identifying optimal choices
**A1** for identifying maximum total expected income
---
## (b) State Patrick's Two Optimal Schedules
**Marks: (2)**
**B1** for first optimal schedule (e.g., London $\to$ A $\to$ C $\to$ F $\to$ H $\to$ London, or equivalent)
**B1** for second optimal schedule (e.g., London $\to$ A $\to$ D $\to$ G $\to$ I $\to$ London, or equivalent)7. Patrick is to take orders for his company's products.
He will visit four countries over the next four weeks.\\
He will visit just one country each week.\\
He will leave from his office in London 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 in each week.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
Week & Week 1 & Week 2 & Week 3 & Week 4 \\
\hline
Possible countries & A or B & C, D or E & F or G & H or I \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
Table 2 shows the value of the orders, in $\pounds 100$ s, he expects to take in each country.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | }
\hline
Country & A & B & C & D & E & F & G & H & I \\
\hline
Value of expected orders in $\pounds 100$ s & 22 & 17 & 42 & 41 & 39 & 29 & 27 & 36 & 38 \\
\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 various countries.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
Travel costs in £100s & A & B & C & D & E & F & G & H & I \\
\hline
London & 5 & 3 & & & & & & 5 & 4 \\
\hline
A & & & 5 & 4 & 2 & & & & \\
\hline
B & & & 4 & 4 & 3 & & & & \\
\hline
C & & & & & & 6 & 5 & & \\
\hline
D & & & & & & 6 & 3 & & \\
\hline
E & & & & & & 4 & 4 & & \\
\hline
F & & & & & & & & 6 & 7 \\
\hline
G & & & & & & & & 5 & 6 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 3}
\end{center}
\end{table}
The expected income is the value of the expected orders minus the cost of travel.
It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.
\begin{enumerate}[label=(\alph*)]
\item Complete the table in the answer book to determine the optimal expected income.
\item State Patrick's two optimal schedules.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2011 Q7 [13]}}