Question 7 - A-Level Maths

Edexcel D2 2017 June — Question 7 13 marks

Exam Board	Edexcel
Module	D2 (Decision Mathematics 2)
Year	2017
Session	June
Marks	13
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Dynamic Programming
Type	Dynamic programming resource allocation
Difficulty	Moderate -0.3 This is a standard transportation problem using the north-west corner method, which is a mechanical algorithm requiring no problem-solving insight. Students follow a prescribed procedure to allocate supplies to demands, making it slightly easier than average for A-level Decision Maths, though the multiple iterations add some computational work.
Spec	7.06a LP formulation: variables, constraints, objective function

7. A clothing manufacturer can export a maximum of five batches of shirts each year. Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts. The table below shows the profit, in £ 1000 s, for the number of each exported batch type.

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	1	2	3	4	Supply
A	15	17	20	11	33
B	12	11	18	21	21
C	18	13	10	16	25
Demand	21	17	28	13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13

1 2 3 4 Supply
A 33
B 21
C 25
Demand 21 17 28 13
3.
B plays 1 B plays 2 B plays 3
A plays 1 0 - 2 6
A plays 2 3 4 1
A plays 3 - 1 1 - 3
4.
1 2 3 4
A 53 84 - 20
B 87 72 41 38
C 70 51 52 25
D 45 - 81 70
5. (a)
You may not need to use all of these tableaux
b.v. \(x\) \(y\) \(z\) \(r\) \(s\) \(t\) Value
\(r\) 15 - 2 3 1 0 0 180
\(s\) 10 1 1 0 1 0 80
\(t\) 1 6 - 2 0 0 1 100
\(P\) - 1 - 2 - 5 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\)

b.v. \(x\) \(y\) \(z\) \(r\) \(s\) \(t\) Value Row Ops
\(P\)

b.v. \(x\) \(y\) \(z\) \(r\) \(s\) \(t\) Value Row Ops
\(P\)
6. (a) Value of initial flow
(b) Capacity of cut \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408} \captionsetup{labelformat=empty} \caption{Diagram 1}
\end{figure} \includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}
7. You may not need to use all the rows of this table
Stage State Action Dest. Value
T-shirt

Stage State Action Dest. Value
Maximum annual profit £ \(\_\_\_\_\)

Show mark scheme Show mark scheme source

Part (a):

Answer	Marks
M1 A1 (stage 1)
M1 A1 A1 (1st 4 states of stage 2)
M1 A1 A1 (last 2 states of stage 2)
M1 A1 A1 (3rd stage)

Part (b):

Answer	Marks
Profit = (£) 315,000	A1 (11)
(T-shirt = 0,) Rugby = 4, Polo = 1 or T-shirt = 3, Rugby = 1, Polo = 1	B1 B1 (2)

Notes for Question 7:

- a1M1: At least five rows for the first stage. Value column must contain the values of 55, 95, 180, 230 and 290. Ignore entries in all other columns and condone an error in one value only

- a1A1: CAO for the first stage (all six rows) – entries in all columns must be correct – candidates may start with state 5 (rather than state 0) which is fine

- a2M1: Second stage – my states 1, 2 and 3 (so at least 9 rows in the first half of the second stage or at least 20 non-zero rows). Value column must be complete with at least one value correct for each state – ignore entries in all other columns

- a2A1: Value column for states 1, 2 and 3 correct for the second stage – ignore entries in all other columns and condone additional rows

- a3A1: CAO for states 0, 1, 2 and 3 of the second stage (no additional rows for these four states) - entries in all columns must be correct

- a3M1: Second stage – my states 4 and 5 (so at least 11 rows in the second half of the second stage or at least 20 non-zero rows). Value column must be complete with at least one value correct for each state – ignore entries in all other columns

- a4A1: Value column for states 4 and 5 correct for the second stage – ignore entries in all other columns and condone additional rows

- a5A1: CAO for states 4 and 5 of the second stage (no additional rows for these two states) - entries in all columns must be correct

- If 9 ≤ non-zero rows < 20 and it is unclear which rows relate to which state but there is one correct value from all five states then award the first M mark for this (2nd stage)

- a4M1: At least 6 rows for the third stage. Value column must be complete with at least 3 values correct – ignore entries in all other columns

- a6A1: CAO for third stage correct (no additional rows for this stage) - entries in all columns must be correct

- a7A1: CAO – must have earned all previous M marks

- b1B1: One correct allocation (dependent on at least three M marks awarded in (a))

- b2B1: Both allocations correct (dependent on at least three M marks awarded in (a))

**Part (a):**
| M1 A1 (stage 1)
| M1 A1 A1 (1st 4 states of stage 2)
| M1 A1 A1 (last 2 states of stage 2)
| M1 A1 A1 (3rd stage)

**Part (b):**
Profit = (£) 315,000 | A1 (11)
(T-shirt = 0,) Rugby = 4, Polo = 1 or T-shirt = 3, Rugby = 1, Polo = 1 | B1 B1 (2)

**Notes for Question 7:**
- **a1M1:** At least five rows for the first stage. Value column must contain the values of 55, 95, 180, 230 and 290. Ignore entries in all other columns and condone an error in one value only
- **a1A1:** CAO for the first stage (all six rows) – **entries in all columns must be correct** – candidates may start with state 5 (rather than state 0) which is fine
- **a2M1:** Second stage – my states 1, 2 and 3 (so at least 9 rows in the first half of the second stage or at least 20 non-zero rows). Value column must be complete with at least one value correct for each state – ignore entries in all other columns
- **a2A1:** Value column for states 1, 2 and 3 correct for the second stage – ignore entries in all other columns and condone additional rows
- **a3A1:** CAO for states 0, 1, 2 and 3 of the second stage (no additional rows for these four states) - **entries in all columns must be correct**
- **a3M1:** Second stage – my states 4 and 5 (so at least 11 rows in the second half of the second stage or at least 20 non-zero rows). Value column must be complete with at least one value correct for each state – ignore entries in all other columns
- **a4A1:** Value column for states 4 and 5 correct for the second stage – ignore entries in all other columns and condone additional rows
- **a5A1:** CAO for states 4 and 5 of the second stage (no additional rows for these two states) - **entries in all columns must be correct**
- **If 9 ≤ non-zero rows < 20 and it is unclear which rows relate to which state but there is one correct value from all five states then award the first M mark for this (2nd stage)**
- **a4M1:** At least 6 rows for the third stage. Value column must be complete with at least 3 values correct – ignore entries in all other columns
- **a6A1:** CAO for third stage correct (no additional rows for this stage) - **entries in all columns must be correct**
- **a7A1:** CAO – must have earned all previous M marks
- **b1B1:** One correct allocation (dependent on at least three M marks awarded in (a))
- **b2B1:** Both allocations correct (dependent on at least three M marks awarded in (a))

Show LaTeX source

7. A clothing manufacturer can export a maximum of five batches of shirts each year.

Each exported batch contains just one type of shirt, the types being T-shirts, Rugby shirts and Polo shirts.

The table below shows the profit, in £ 1000 s, for the number of each exported batch type.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | }
\hline
 & A & B & C & D & E & F \\
\hline
A & - & 83 & 75 & 82 & 69 & 97 \\
\hline
B & 83 & - & 94 & 103 & 77 & 109 \\
\hline
C & 75 & 94 & - & 97 & 120 & 115 \\
\hline
D & 82 & 103 & 97 & - & 105 & 125 \\
\hline
E & 69 & 77 & 120 & 105 & - & 88 \\
\hline
F & 97 & 109 & 115 & 125 & 88 & - \\
\hline
\end{tabular}
\end{center}

2.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A & 15 & 17 & 20 & 11 & 33 \\
\hline
B & 12 & 11 & 18 & 21 & 21 \\
\hline
C & 18 & 13 & 10 & 16 & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item \begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 & Supply \\
\hline
A &  &  &  &  & 33 \\
\hline
B &  &  &  &  & 21 \\
\hline
C &  &  &  &  & 25 \\
\hline
Demand & 21 & 17 & 28 & 13 &  \\
\hline
\end{tabular}
\end{center}

3.

\begin{center}
\begin{tabular}{ | l | c | c | c | }
\hline
 & B plays 1 & B plays 2 & B plays 3 \\
\hline
A plays 1 & 0 & - 2 & 6 \\
\hline
A plays 2 & 3 & 4 & 1 \\
\hline
A plays 3 & - 1 & 1 & - 3 \\
\hline
\end{tabular}
\end{center}

4.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | }
\hline
 & 1 & 2 & 3 & 4 \\
\hline
A & 53 & 84 & - & 20 \\
\hline
B & 87 & 72 & 41 & 38 \\
\hline
C & 70 & 51 & 52 & 25 \\
\hline
D & 45 & - & 81 & 70 \\
\hline
\end{tabular}
\end{center}

5. (a)
\item You may not need to use all of these tableaux

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
b.v. & $x$ & $y$ & $z$ & $r$ & $s$ & $t$ & Value \\
\hline
$r$ & 15 & - 2 & 3 & 1 & 0 & 0 & 180 \\
\hline
$s$ & 10 & 1 & 1 & 0 & 1 & 0 & 80 \\
\hline
$t$ & 1 & 6 & - 2 & 0 & 0 & 1 & 100 \\
\hline
$P$ & - 1 & - 2 & - 5 & 0 & 0 & 0 & 0 \\
\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}

\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}
\item \\
6. (a) Value of initial flow\\
(b) Capacity of cut

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{d5798c81-290a-4e4b-aa46-497b62ca899b-20_1931_1099_507_408}
\captionsetup{labelformat=empty}
\caption{Diagram 1}
\end{center}
\end{figure}

\includegraphics[max width=\textwidth, alt={}, center]{d5798c81-290a-4e4b-aa46-497b62ca899b-21_1874_953_653_589}\\
7. You may not need to use all the rows of this table

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Dest. & Value \\
\hline
T-shirt &  &  &  &  \\
\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 & 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
 &  &  &  &  \\
\hline
 &  &  &  &  \\
\hline
 &  &  &  &  \\
\hline
 &  &  &  &  \\
\hline
 &  &  &  &  \\
\hline
 &  &  &  &  \\
\hline
\end{tabular}
\end{center}

Maximum annual profit £ $\_\_\_\_$
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2 2017 Q7 [13]}}

This paper (7 questions)

View full paper

Q1 7 Q2 10 Q3 13 Q4 7 Q5 13 Q6 12 Q7 13

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	B plays 1	B plays 2	B plays 3
A plays 1	0	- 2	6
A plays 2	3	4	1
A plays 3	- 1	1	- 3

b.v.	\(x\)	\(y\)	\(z\)	\(r\)	\(s\)	\(t\)	Value
\(r\)	15	- 2	3	1	0	0	180
\(s\)	10	1	1	0	1	0	80
\(t\)	1	6	- 2	0	0	1	100
\(P\)	- 1	- 2	- 5	0	0	0	0

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-

	A	B	C	D	E	F
A	-	83	75	82	69	97
B	83	-	94	103	77	109
C	75	94	-	97	120	115
D	82	103	97	-	105	125
E	69	77	120	105	-	88
F	97	109	115	125	88	-