| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Easy -1.2 This is a straightforward application of the dynamic programming algorithm to find the minimum cost path through a small network. The question requires only mechanical application of the standard backward pass algorithm taught in D2, with no problem-solving insight or novel thinking required. While worth 9 marks, the steps are routine and the network is small enough to manage easily. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage 1 – Catering: | ||
| Marquee \(\to\) Deluxe: 20, Cuisine: 24; minimum = 20 (Deluxe) | B1 | |
| Castle \(\to\) Deluxe: 15, Castle: 21, Cuisine: 22; minimum = 15 (Castle catering) | B1 | |
| Hotel \(\to\) Deluxe: 19, Cuisine: 23, Hotel: 18; minimum = 18 (Hotel catering) | B1 | |
| Stage 2 – Reception: | ||
| Church \(\to\) Marquee: \(2+20=22\), Castle: \(5.5+15=20.5\), Hotel: \(3+18=21\); min = 20.5 (Castle) | M1 A1 | M1 for adding stage 1 minima correctly |
| Castle \(\to\) Marquee: \(3+20=23\), Castle: \(5+15=20\); min = 20 (Castle) | A1 | |
| Registry \(\to\) Marquee: \(3.5+20=23.5\), Castle: \(6+15=21\), Hotel: \(2+18=20\); min = 20 (Hotel) | A1 | |
| Stage 3 – Ceremony: | ||
| Home \(\to\) Castle: \(5+20=25\), Church: \(3+20.5=23.5\), Registry: \(1+20=21\); min = 21 (Registry) | M1 A1 | |
| Optimal route: Home \(\to\) Registry \(\to\) Hotel \(\to\) Hotel catering | A1 | |
| Total minimum cost \(= 21 \times £100 = £2100\) | A1 | Accept 21 (hundreds of pounds) |
# Question 3:
| Answer | Marks | Guidance |
|--------|-------|----------|
| **Stage 1 – Catering:** | | |
| Marquee $\to$ Deluxe: 20, Cuisine: 24; minimum = 20 (Deluxe) | B1 | |
| Castle $\to$ Deluxe: 15, Castle: 21, Cuisine: 22; minimum = 15 (Castle catering) | B1 | |
| Hotel $\to$ Deluxe: 19, Cuisine: 23, Hotel: 18; minimum = 18 (Hotel catering) | B1 | |
| **Stage 2 – Reception:** | | |
| Church $\to$ Marquee: $2+20=22$, Castle: $5.5+15=20.5$, Hotel: $3+18=21$; min = 20.5 (Castle) | M1 A1 | M1 for adding stage 1 minima correctly |
| Castle $\to$ Marquee: $3+20=23$, Castle: $5+15=20$; min = 20 (Castle) | A1 | |
| Registry $\to$ Marquee: $3.5+20=23.5$, Castle: $6+15=21$, Hotel: $2+18=20$; min = 20 (Hotel) | A1 | |
| **Stage 3 – Ceremony:** | | |
| Home $\to$ Castle: $5+20=25$, Church: $3+20.5=23.5$, Registry: $1+20=21$; min = 21 (Registry) | M1 A1 | |
| Optimal route: Home $\to$ Registry $\to$ Hotel $\to$ Hotel catering | A1 | |
| Total minimum cost $= 21 \times £100 = £2100$ | A1 | Accept 21 (hundreds of pounds) |
---3. This question should be answered on the sheet provided.
A couple are making the arrangements for their wedding. They are deciding whether to have the ceremony at their church, a local castle or a nearby registry office. The reception will then be held in a marquee, at the castle or at a local hotel. Both the castle and hotel offer catering services but the couple are also considering using Deluxe Catering or Cuisine, who can both provide the food at any venue.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{f662b4da-12c1-4f30-ab5d-fb132f19e643-3_944_1504_605_258}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{center}
\end{figure}
The network in Figure 1 shows the costs incurred (including transport), in hundreds of pounds, according to the choice the couple make for each stage of the day.
Use dynamic programming to find how the couple can minimise the total cost of their wedding and state the total cost of this arrangement.\\
(9 marks)\\
\hfill \mbox{\textit{Edexcel D2 Q3 [9]}}