A2 October 2020 Q7

EdexcelCurrent spec12 marksDynamic Programming

7. A manufacturer can export five batches of footwear each year. Each exported batch contains just one type of footwear. The types of footwear are trainers, sandals or high heels.

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

Number of batches	1	2	3	4	5
Trainers	50	90	170	225	295
Sandals	70	110	165	245	300
High heels	75	115	\(x\)	235	305

The total annual profit is to be maximised.

(a) Use dynamic programming to determine the two possible values of the maximum total annual profit, giving one of these values in terms of \(x\). (10)

Given that the maximum total annual profit is £320 000

(b) advise the manufacturer on the possible ways in which the five batches should be allocated. (2)

Mark scheme (a)

Scheme

Marks

Stage	State	Action	Value
Trainers	0	0	0
	1	1	50
	2	2	90
	3	3	170
	4	4	225
	5	5	295

3.1a

Stage	State	Action	Dest.	Value
Sandals	0	0	0	0
	1	1	0	70 + 0 = 70*
		0	1	0 + 50 = 50
	2	2	0	110 + 0 = 110
		1	1	70 + 50 = 120*
		0	2	0 + 90 = 90
	3	3	0	165 + 0 = 165
		2	1	110 + 50 = 160
		1	2	70 + 90 = 160
		0	3	0 + 170 = 170*

M1
A1
A1

3.1a
1.1b
1.1b

State	Action	Dest.	Value
4	4	0	245 + 0 = 245*
	3	1	165 + 50 = 215
	2	2	110 + 90 = 200
	1	3	70 + 170 = 240
	0	4	0 + 225 = 225
5	5	0	300 + 0 = 300*
	4	1	245 + 50 = 295
	3	2	165 + 90 = 255
	2	3	110 + 170 = 280
	1	4	70 + 225 = 295
	0	5	0 + 295 = 295

M1
A1
A1

1.1b
1.1b
1.1b

Stage	State	Action	Dest.	Value
High heels	5	5	0	305 + 0 = 305
		4	1	235 + 70 = 305
		3	2	\(x + 120\)
		2	3	115 + 170 = 285
		1	4	75 + 245 = 320
		0	5	0 + 300 = 300

M1
A1ft

1.1b
1.1b

320 and \(x + 120\)

A1ft

1.1b

(10)

Notes

B1: 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

M1: 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

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

A1: 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

M1: 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

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

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

M1: 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

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

A1ft: Must have earned all previous M marks from their completed dynamic programming but ft their result

Mark scheme (b)

Scheme	Marks	AO
Trainers: 0 Sandals: 4 High heels: 1	B1	1.1b
Trainers: 1 Sandals: 1 High heels: 3	B1	2.2a
	(2)
	(12 marks)

Notes

B1: One correct allocation (dependent on first three M marks in (a))

B1: For both correct (dependent on first three M marks in (a))