D2 June 2018 Q6

EdexcelOld spec15 marksDynamic Programming

6. Jonathan is an author who is planning his next book tour. He will visit four countries over a period of four weeks. He will visit just one country each week. He will leave from his home, S, and will only return there after visiting the four countries. He will travel directly from one country to the next. He wishes to determine a schedule of four countries to visit.

Table 1 shows the countries he could visit each week.

Week	1	2	3	4
Possible countries	A, B or C	D or E	F, G or H	I or J

Table 1

Table 2 shows the appearance fees, in £100s, he expects to earn in each country.

Country	A	B	C	D	E	F	G	H	I	J
Earnings in £100s	27	29	32	24	22	35	36	38	30	29

Table 2

Table 3 shows the cost, in £100s, of travelling between the countries.

	A	B	C	D	E	F	G	H	I	J
S	3	4	6						5	3
A				6	4
B				5	3
C				6	5
D						7	6	8
E						6	6	4
F									5	7
G									5	7
H									6	7

Table 3

Jonathan’s expected income is the value of the appearance fees minus the cost of travel. He decides to use dynamic programming to find a schedule that maximises his total expected income for these four weeks.

Complete the table in the answer book to solve this dynamic programming problem. Hence write down Jonathan’s optimal expected income and state his possible optimal schedules.

Mark scheme

Scheme

Marks

Stage	State	Action	Dest.	Value
0	I	IS	S	30 – 5 = 25*
	J	JS	S	29 – 3 = 26*
1	F	FI	I	35 – 5 + 25 = 55*
		FJ	J	35 – 7 + 26 = 54
	G	GI	I	36 – 5 + 25 = 56*
		GJ	J	36 – 7 + 26 = 55
	H	HI	I	38 – 6 + 25 = 57*
		HJ	J	38 – 7 + 26 = 57*
2	D	DF	F	24 – 7 + 55 = 72
		DG	G	24 – 6 + 56 = 74*
		DH	H	24 – 8 + 57 = 73
	E	EF	F	22 – 6 + 55 = 71
		EG	G	22 – 6 + 56 = 72
		EH	H	22 – 4 + 57 = 75*
3	A	AD	D	27 – 6 + 74 = 95
		AE	E	27 – 4 + 75 = 98*
	B	BD	D	29 – 5 + 74 = 98
		BE	E	29 – 3 + 75 = 101*
	C	CD	D	32 – 6 + 74 = 100
		CE	E	32 – 5 + 75 = 102*
4	S	SA	A	– 3 + 98 = 95
		SB	B	– 4 + 101 = 97*
		SC	C	– 6 + 102 = 96

B1 (1)

M1 A1 A1 (3)

M1 A1ft A1 (3)

M1 A1ft A1 (3)

M1 A1 (2)

Optimal expected income: (£) 9700

Optimal schedules are:
S – B – E – H – I – S
S – B – E – H – J – S

B1B1

(3)

15 marks

Notes

Condone lack of destination column
Only penalise incorrect result in value – i.e. ignore working values
Penalise absence of state or action column with first two A marks earned only
Penalise empty/errors in stage column with first A mark earned only

For all M marks – must bring optimal results from previous stage into calculation at least once – so from Stage 0 if neither of 25 or their 26 are used in Stage 1 then M0. Ignore extra rows. Must have correct ingredients (appearance fee, cost) at least once per stage. If no working seen then values in the Value column must be correct to imply these marks

1B1: CAO (Stage 0)

1M1: First stage completed. At least six rows. Bod if something in each cell

1A1: Any two states correct with no extra rows for these states

2A1: All 3 states correct with no extra rows for Stage 1

2M1: Second stage completed. At least six rows. Bod if something in each cell

3A1ft: One state correct (ft) from Stage 1 (no extra rows)

4A1: Both states correct for Stage 2 (no extra rows)

3M1: Third stage completed. At least six rows. Bod if something in each column

5A1ft: Two states correct (ft) from Stage 2 (no extra rows)

6A1: All 3 states correct (no extra rows)

4M1: Fourth stage completed. At least three rows. Bod if something in each cell

7A1: Final state correct (no extra rows)

2B1: CAO (dependent on all previous M marks earned) – units not required – but not for 97

3B1: One route correct (dependent on all previous M marks earned) – condone no S’s but not reversed

4B1: Both routes correct (dependent on all previous M marks earned) – no additional routes, S’s present and not reversed