| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2013 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming order sequencing |
| Difficulty | Standard +0.8 This is a standard dynamic programming problem requiring backward induction through a 4-stage decision process with clearly defined states and costs. While it requires systematic tabulation and careful bookkeeping of multiple cost components (maintenance, replacement, income, and terminal values), the structure is formulaic and follows textbook D2 methodology. It's moderately challenging due to the multi-stage nature and need for accuracy, but doesn't require novel insight beyond applying the standard DP algorithm. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.07b Simplex iterations: pivot choice and row operations7.07c Interpret simplex: values of variables, slack, and objective7.07d Simplex terminology: basic feasible solution, basic/non-basic variable7.07e Graphical interpretation: iterations as edges of convex polygon7.07f Algebraic interpretation: explain simplex calculations |
| Age of fleet of bicycles | new | 1 year old | 2 years old | 3 years old | 4 years old |
| Cost of keeping (£1000s) | 0 | 1 | 2 | 3 | 8 |
| Cost of replacing (£1000s) | - | 7 | 8 | 9 | 10 |
| Income (£1000s) | 11 | 8 | 5 | 2 | 0 |
|
|
|
|
| ||||||||||
| 6 | 4 | 2 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Stage | State | Action |
| end | 4 | Sell |
| 3 | Sell | - |
| 2 | Sell | - |
| 1 | Sell | - |
| 4 | 3 | K |
| R | 1 | \(6 + 11 - 9 = 8*\) |
| 2 | K | 3 |
| R | 1 | \(6 + 11- 8 = 9*\) |
| 1 | K | 2 |
| R | 1 | \(6 + 11 - 7 = 10\) |
| 3 | 2 | K |
| R | 1 | \(11 + 11 - 8 = 14*\) |
| 1 | K | 2 |
| R | 1 | \(11 + 11 - 7 = 15\) |
| 2 | 1 | K |
| R | 1 | \(16 + 11 - 7 = 20\) |
| 1 | new | K |
| Answer | Marks | Guidance |
|---|---|---|
| His income will be £32 000. | 1M1A1A1 2M1 A1 3M1A1ft A1 4M1 A1ft A1 | (2) B1 B1ft Total 13 |
[Dynamic Programming table with columns: Stage, State, Action, Destination, Value]
| Stage | State | Action | Destination | Value |
|---|---|---|---|---|
| end | 4 | Sell | - | 1* |
| | 3 | Sell | - | 2* |
| | 2 | Sell | - | 4* |
| | 1 | Sell | - | 6* |
| 4 | 3 | K | 4 | $1 + 2 - 3 = 0$ |
| | | R | 1 | $6 + 11 - 9 = 8*$ |
| | 2 | K | 3 | $2 + 5 - 2 = 5$ |
| | | R | 1 | $6 + 11- 8 = 9*$ |
| | 1 | K | 2 | $4 + 8 - 1 = 11*$ |
| | | R | 1 | $6 + 11 - 7 = 10$ |
| 3 | 2 | K | 3 | $8 + 5 - 2 = 11$ |
| | | R | 1 | $11 + 11 - 8 = 14*$ |
| | 1 | K | 2 | $9 + 8 - 1 = 16*$ |
| | | R | 1 | $11 + 11 - 7 = 15$ |
| 2 | 1 | K | 2 | $14 + 8 - 1 = 21*$ |
| | | R | 1 | $16 + 11 - 7 = 20$ |
| 1 | new | K | 1 | $21 + 11 = 32*$ |
The actions Nigel should take are: Keep, Keep, Replace, Keep in years 1, 2, 3 and 4 respectively
His income will be £32 000. | 1M1A1A1 2M1 A1 3M1A1ft A1 4M1 A1ft A1 | (2) B1 B1ft Total 13
1M1 At least 3 columns in Stage 4 completed, something in each cell.
1A1 For stage 4 at least two columns of state, action, destination entries correct
2A1 Two rows in Stage 4 CAO. Penalise * errors only twice in the question on the first occurrences
**All future M marks must bring all optimal results from previous stage into current stage at least once (or three out of four previous results correct).**
2M1 All four rows in stage 4 completed. Bod if something in each cell.
3A1 CAO. Stage 4 correct. (Penalise * errors only twice in the question).
3M1 Stage 3 completed. Bod if something in each cell.
4A1ft Any state correct (Penalise * errors only twice in the question).
4M1 Stage 2 and 1 completed. Bod if something in each cell.
6A1ft CAO Stage 2 correct. (Penalise * errors only twice in the question).
7A1 CAO Stage 1 correct.
1B1 Actions correct. Must have earned all previous M marks
2B1ft Income correct for their table. Must have earned all previous M marks.
**Penalise extra rows for stage 4 with the 3rd A mark, stage 3 with the 5th A mark and stage 2 with the 6th A mark.**7. Nigel has a business renting out his fleet of bicycles to tourists.
At the start of each year Nigel must decide on one of two actions:
\begin{itemize}
\item Keep his fleet of bicycles, incurring maintenance costs.
\item Replace his fleet of bicycles.
\end{itemize}
The cost of keeping the fleet of bicycles, the cost of replacing the fleet of bicycles and the annual income are dependent on the age of the fleet of bicycles.\\
Table 1 shows these amounts, in $\pounds 1000$ s.
\begin{table}[h]
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
Age of fleet of bicycles & new & 1 year old & 2 years old & 3 years old & 4 years old \\
\hline
Cost of keeping (£1000s) & 0 & 1 & 2 & 3 & 8 \\
\hline
Cost of replacing (£1000s) & - & 7 & 8 & 9 & 10 \\
\hline
Income (£1000s) & 11 & 8 & 5 & 2 & 0 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}
Nigel has a new fleet of bicycles now and wishes to maximise his total profit over the next four years.
He is planning to sell his business at the end of the fourth year.\\
The amount Nigel will receive will depend on the age of his fleet of bicycles.\\
These amounts, in £1000s, are shown in Table 2.
\begin{table}[h]
\begin{center}
\begin{tabular}{ | l | c | c | c | c | }
\hline
\begin{tabular}{ l }
Age of fleet of bicycles \\
at end of 4th year \\
\end{tabular} & \begin{tabular}{ c }
1 year \\
old \\
\end{tabular} & \begin{tabular}{ c }
2 years \\
old \\
\end{tabular} & \begin{tabular}{ c }
3 years \\
old \\
\end{tabular} & \begin{tabular}{ c }
4 years \\
old \\
\end{tabular} \\
\hline
\begin{tabular}{ l }
Amount received at end \\
of 4th year $( \pounds 1000 \mathrm {~s} )$ \\
\end{tabular} & 6 & 4 & 2 & 1 \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{center}
\end{table}
Complete the table in the answer book to determine Nigel's best strategy to maximise his total profit over the next four years. You must state the action he should take each year (keep or replace) and his total profit.\\
(Total 13 marks)\\
\hfill \mbox{\textit{Edexcel D2 2013 Q7 [13]}}