Edexcel D2 2019 June — Question 7 15 marks

Exam BoardEdexcel
ModuleD2 (Decision Mathematics 2)
Year2019
SessionJune
Marks15
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeDynamic programming order sequencing
DifficultyModerate -0.5 This is a standard D2 dynamic programming question requiring systematic application of the minimax algorithm to find optimal construction order. While it involves multiple stages and careful bookkeeping, it follows a well-practiced algorithmic procedure with no novel problem-solving required, making it slightly easier than average for A-level.
Spec7.06a LP formulation: variables, constraints, objective function

7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year. The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below.
\cline { 2 - 7 } \multicolumn{1}{c|}{}ABCDEF
A-5347393540
B53-32464143
C4732-514737
D394651-3649
E35414736-42
F4043374942-
\begin{table}[h]
1234Supply
A1720231425
B1615192229
C1914111532
Demand28172318
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table} 2. You may not need to use all of these tables \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Table 1}
1234Supply
A25
B29
C32
Demand28172318
\end{table}
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
1234Supply
A25
B29
C32
Demand28172318
3.
ABCDE
Frank50734
Gill538101
Harry43790
Imogen63654
Jiao02732
You may not need to use all of these tables
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
ABCDE
F
G
H
I
J
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
\(A\)\(B\)\(C\)\(D\)\(E\)
\(F\)
\(G\)
\(H\)
\(I\)
\(J\)
Stephen plays 1Stephen plays 2Stephen plays 3
Eugene plays 1450
Eugene plays 2-211
Eugene plays 3-3-43
4. 5. (a)
b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)Value
30
60
80
0
You may not need to use all of these tableaux
b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Ops
\(P\)
b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Ops
\(P\)
b.v.\(x\)\(y\)\(z\)\(r\)\(s\)\(t\)ValueRow Ops
\(P\)
6. (a) Value of initial flow
(b) and (c) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-20_725_1251_404_349} \section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}]{e0c66144-9e34-42fc-9f40-a87a49331483-20_1070_1264_1322_349}
\section*{Diagram 2} (d)
(e) \includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-21_714_1385_1306_283} \section*{Diagram 3} (f)
7. (a)
StageStateActionDest.Value
1ABCDABCD65*
StageStateActionDest.Value
\includegraphics[max width=\textwidth, alt={}]{e0c66144-9e34-42fc-9f40-a87a49331483-24_2642_1833_118_118}

Question 7:
Part (a):
AnswerMarks Guidance
minimaxB1 (1) CAO
Part (b):
AnswerMarks Guidance
Stage 1 values: At least three additional rows for first stage. Value column must contain values of 55, 45 and 55
ABC → ABCD: \(65^*\)M1A1
ABD → ABCD: \(55^*\)
ACD → ABCD: \(45^*\)
BCD → ABCD: \(55^*\) CAO for first stage — entries in all columns must be correct
Stage 2 values:M1 A1 A1 A1 Second stage — at least 12 rows
AB via C → ABC: \(\max(40,65)=65\) Any two states correct
AB via D → ABD: \(\max(35,55)=55^*\) Any four states correct
AC via B → ABC: \(\max(55,65)=65\) Second stage completely correct
AC via D → ACD: \(\max(30,45)=45^*\)
AD via B → ABD: \(\max(55,55)=55^*\)
AD via C → ACD: \(\max(60,45)=60\)
BC via A → ABC: \(\max(45,65)=65\)
BC via D → BCD: \(\max(50,55)=55^*\)
BD via A → ABD: \(\max(65,55)=65\)
BD via C → BCD: \(\max(35,55)=55^*\)
CD via A → ACD: \(\max(55,45)=55^*\)
CD via B → BCD: \(\max(40,55)=55^*\)
Stage 3 values:M1 A1ft A1 Third stage — at least 12 rows
A via B → AB: \(\max(45,55)=55\) Any two states correct in third stage on ft from second stage
A via C → AC: \(\max(50,45)=50^*\) Third stage completely correct
A via D → AD: \(\max(55,55)=55\)
B via A → AB: \(\max(50,55)=55^*\)
B via C → BC: \(\max(45,55)=55^*\)
B via D → BD: \(\max(55,55)=55^*\)
C via A → AC: \(\max(60,45)=60\)
C via B → BC: \(\max(45,55)=55^*\)
C via D → CD: \(\max(50,55)=55^*\)
D via A → AD: \(\max(65,55)=65\)
D via B → BD: \(\max(55,55)=55^*\)
D via C → CD: \(\max(60,55)=60\)
Stage 4 values:M1 A1 Fourth stage — at least 4 rows
None via A → A: \(\max(25,50)=50^*\) Fourth stage completely correct
None via B → B: \(\max(35,55)=55\)
None via C → C: \(\max(35,55)=55\)
None via D → D: \(\max(30,55)=55\)(11)
Part (c):
AnswerMarks Guidance
Order is A, C, D, BDB1 Correct order — dependent on all M marks awarded in (b)
Cost is \(25\,000 + 50\,000 + 30\,000 + 45\,000 = \pounds150\,000\)M1 A1 (3) Correct method for calculating cost for their order; CAO
# Question 7:

## Part (a):
| minimax | B1 (1) | CAO |

## Part (b):
| **Stage 1 values:** | | At least three additional rows for first stage. Value column must contain values of 55, 45 and 55 |
| ABC → ABCD: $65^*$ | M1A1 | |
| ABD → ABCD: $55^*$ | | |
| ACD → ABCD: $45^*$ | | |
| BCD → ABCD: $55^*$ | | CAO for first stage — entries in all columns must be correct |
| **Stage 2 values:** | M1 A1 A1 A1 | Second stage — at least 12 rows |
| AB via C → ABC: $\max(40,65)=65$ | | Any two states correct |
| AB via D → ABD: $\max(35,55)=55^*$ | | Any four states correct |
| AC via B → ABC: $\max(55,65)=65$ | | Second stage completely correct |
| AC via D → ACD: $\max(30,45)=45^*$ | | |
| AD via B → ABD: $\max(55,55)=55^*$ | | |
| AD via C → ACD: $\max(60,45)=60$ | | |
| BC via A → ABC: $\max(45,65)=65$ | | |
| BC via D → BCD: $\max(50,55)=55^*$ | | |
| BD via A → ABD: $\max(65,55)=65$ | | |
| BD via C → BCD: $\max(35,55)=55^*$ | | |
| CD via A → ACD: $\max(55,45)=55^*$ | | |
| CD via B → BCD: $\max(40,55)=55^*$ | | |
| **Stage 3 values:** | M1 A1ft A1 | Third stage — at least 12 rows |
| A via B → AB: $\max(45,55)=55$ | | Any two states correct in third stage on ft from second stage |
| A via C → AC: $\max(50,45)=50^*$ | | Third stage completely correct |
| A via D → AD: $\max(55,55)=55$ | | |
| B via A → AB: $\max(50,55)=55^*$ | | |
| B via C → BC: $\max(45,55)=55^*$ | | |
| B via D → BD: $\max(55,55)=55^*$ | | |
| C via A → AC: $\max(60,45)=60$ | | |
| C via B → BC: $\max(45,55)=55^*$ | | |
| C via D → CD: $\max(50,55)=55^*$ | | |
| D via A → AD: $\max(65,55)=65$ | | |
| D via B → BD: $\max(55,55)=55^*$ | | |
| D via C → CD: $\max(60,55)=60$ | | |
| **Stage 4 values:** | M1 A1 | Fourth stage — at least 4 rows |
| None via A → A: $\max(25,50)=50^*$ | | Fourth stage completely correct |
| None via B → B: $\max(35,55)=55$ | | |
| None via C → C: $\max(35,55)=55$ | | |
| None via D → D: $\max(30,55)=55$ | (11) | |

## Part (c):
| Order is A, C, D, B | DB1 | Correct order — dependent on all M marks awarded in (b) |
| Cost is $25\,000 + 50\,000 + 30\,000 + 45\,000 = \pounds150\,000$ | M1 A1 (3) | Correct method for calculating cost for their order; CAO |
7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year.

The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\cline { 2 - 7 }
\multicolumn{1}{c|}{} & A & B & C & D & E & F \\
\hline
A & - & 53 & 47 & 39 & 35 & 40 \\
\hline
B & 53 & - & 32 & 46 & 41 & 43 \\
\hline
C & 47 & 32 & - & 51 & 47 & 37 \\
\hline
D & 39 & 46 & 51 & - & 36 & 49 \\
\hline
E & 35 & 41 & 47 & 36 & - & 42 \\
\hline
F & 40 & 43 & 37 & 49 & 42 & - \\
\hline
\end{tabular}
\end{center}

\begin{table}[h]
\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A & 17 & 20 & 23 & 14 & 25 \\
\hline
B & 16 & 15 & 19 & 22 & 29 \\
\hline
C & 19 & 14 & 11 & 15 & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{center}
\end{table}

2.

You may not need to use all of these tables

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Table 1}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}
\end{table}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 25 \\
\hline
B &  &  &  &  & 29 \\
\hline
C &  &  &  &  & 32 \\
\hline
Demand & 28 & 17 & 23 & 18 &  \\
\hline
\end{tabular}
\end{center}

3.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & A & B & C & D & E \\
\hline
Frank & 5 & 0 & 7 & 3 & 4 \\
\hline
Gill & 5 & 3 & 8 & 10 & 1 \\
\hline
Harry & 4 & 3 & 7 & 9 & 0 \\
\hline
Imogen & 6 & 3 & 6 & 5 & 4 \\
\hline
Jiao & 0 & 2 & 7 & 3 & 2 \\
\hline
\end{tabular}
\end{center}

You may not need to use all of these tables

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & A & B & C & D & E \\
\hline
F &  &  &  &  &  \\
\hline
G &  &  &  &  &  \\
\hline
H &  &  &  &  &  \\
\hline
I &  &  &  &  &  \\
\hline
J &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & $A$ & $B$ & $C$ & $D$ & $E$ \\
\hline
$F$ &  &  &  &  &  \\
\hline
$G$ &  &  &  &  &  \\
\hline
$H$ &  &  &  &  &  \\
\hline
$I$ &  &  &  &  &  \\
\hline
$J$ &  &  &  &  &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
 & Stephen plays 1 & Stephen plays 2 & Stephen plays 3 \\
\hline
Eugene plays 1 & 4 & 5 & 0 \\
\hline
Eugene plays 2 & -2 & 1 & 1 \\
\hline
Eugene plays 3 & -3 & -4 & 3 \\
\hline
\end{tabular}
\end{center}

4.

5. (a)

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
 &  &  &  &  &  &  & 30 \\
\hline
 &  &  &  &  &  &  & 60 \\
\hline
 &  &  &  &  &  &  & 80 \\
\hline
 &  &  &  &  &  &  & 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}

6. (a) Value of initial flow\\
(b) and (c)\\
\includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-20_725_1251_404_349}

\section*{Diagram 1}
\begin{center}
\includegraphics[max width=\textwidth, alt={}]{e0c66144-9e34-42fc-9f40-a87a49331483-20_1070_1264_1322_349}
\end{center}

\section*{Diagram 2}

(d)\\

(e)\\
\includegraphics[max width=\textwidth, alt={}, center]{e0c66144-9e34-42fc-9f40-a87a49331483-21_714_1385_1306_283}

\section*{Diagram 3}
(f)\\
7. (a)

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Dest. & Value \\
\hline
1 & ABC & D & ABCD & 65* \\
\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 & Dest. & 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}
\includegraphics[max width=\textwidth, alt={}]{e0c66144-9e34-42fc-9f40-a87a49331483-24_2642_1833_118_118}
\end{center}

\hfill \mbox{\textit{Edexcel D2 2019 Q7 [15]}}