D2 June 2017 Q7

EdexcelOld spec13 marksDynamic Programming

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 £1000s, for the number of each exported batch type.

Number of batches	1	2	3	4	5
T-shirt	55	95	180	230	290
Rugby shirt	65	100	160	245	285
Polo shirt	70	110	175	225	310

The total annual profit is to be maximised.

(a) Use dynamic programming to determine the maximum annual profit. (11)

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

Mark scheme (a)

Scheme

Marks

Stage	State	Action	Dest.	Value
T-shirt	0	0	0	0
	1	1	0	55
	2	2	0	95
	3	3	0	180
	4	4	0	230
	5	5	0	290
Rugby	0	0	0	0
	1	1	0	65 + 0 = 65*
		0	1	0 + 55 = 55
	2	2	0	100 + 0 = 100
		1	1	65 + 55 = 120*
		0	2	0 + 95 = 95
	3	3	0	160 + 0 = 160
		2	1	100 + 55 = 155
		1	2	65 + 95 = 160
		0	3	0 + 180 = 180*
	4	4	0	245 + 0 = 245*
		3	1	160 + 55 = 215
		2	2	100 + 95 = 195
		1	3	65 + 180 = 245*
		0	4	0 + 230 = 230
	5	5	0	285 + 0 = 285
		4	1	245 + 55 = 300*
		3	2	160 + 95 = 255
		2	3	100 + 180 = 280
		1	4	65 + 230 = 295
		0	5	0 + 290 = 290
Polo	5	5	0	310 + 0 = 310
		4	1	225 + 65 = 290
		3	2	175 + 120 = 295
		2	3	110 + 180 = 290
		1	4	70 + 245 = 315*
		0	5	0 + 300 = 300

M1 A1 (stage 1)

M1 A1 A1 (1^st 4 states of stage 2)

M1 A1 A1 (Last 2 states of stage 2)

M1 A1 (3^rd stage)

Profit = (£) 315,000

(11)

Notes

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 \leqslant\) non-zero rows \(\lt 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 (2^nd) 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

Mark scheme (b)

Scheme	Marks
(T-shirt = 0,) Rugby = 4, Polo = 1 or T-shirt = 3, Rugby = 1, Polo = 1	B1 B1
	(2)
	13 marks

Notes

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))