D2 June 2011 Q7

EdexcelOld spec13 marksDynamic Programming

7. Patrick is to take orders for his company’s products.
He will visit four countries over the next four weeks.
He will visit just one country each week.
He will leave from his office in London 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 in each week.

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

Table 1

Table 2 shows the value of the orders, in £100s, he expects to take in each country.

Country	A	B	C	D	E	F	G	H	I
Value of expected orders in £100s	22	17	42	41	39	29	27	36	38

Table 2

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

Travel costs in £100s	A	B	C	D	E	F	G	H	I
London	5	3						5	4
A			5	4	2
B			4	4	3
C						6	5
D						6	3
E						4	4
F								6	7
G								5	6

Table 3

The expected income is the value of the expected orders minus the cost of travel.

It is decided to use dynamic programming to find a schedule that maximises the total expected income for these four weeks.

(a) Complete the table in the answer book to determine the optimal expected income. (11)

(b) State Patrick’s two optimal schedules. (2)

Mark scheme (a)

Scheme

Marks

Stage	State	Action	Dest.	Value
0	H	H- London	London	36 – 5 = 31*
	I	I – London	London	38 – 4 = 34*
1	F	FH	H	29 – 6 + 31 = 54
		FI	I	29 – 7 + 34 = 56*
	G	GH	H	27 – 5 + 31 = 53
		GI	I	27 – 6 + 34 = 55*
2	C	CF	F	42 – 6 + 56 = 92*
		CG	G	42 – 5 + 55 = 92*
	D	DF	F	41 – 6 + 56 = 91
		DG	G	41 – 3 + 55 = 93*
	E	EF	F	39 – 4 + 56 = 91*
		EG	G	39 – 4 + 55 = 90
3	A	AC	C	22 – 5 + 92 = 109
		AD	D	22 – 4 + 93 = 111*
		AE	E	22 – 2 + 91 = 111*
	B	BC	C	17 – 4 + 92 = 105
		BD	D	17 – 4 + 93 = 106*
		BE	E	17 – 3 + 91 = 105
4	London	London – A	A	−5 + 111 = 106*
		London – B	B	−3 + 106 = 103

Optimal expected income is £10 600

1M1 1A1 (2)
2M1 2A1 3A1 (3)
3M1 4A1ft 5A1ft (3)
4M1 6A1ft 7A1ft (3)

(11)

Notes

Throughout section (a):

Condone lack of destination column and/or reversed stage numbers throughout.
Only penalise incorrect result in Value – ie 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.

1M1: First stage completed.

1A1: CAO Penalise * errors only once in the question on the first occurrence

2M1: Second stage completed. Penalise reversed states here and at end. Bod if something in each cell.

2A1: Any 2 states correct. (Penalise * errors only once in the question).

3A1: All 3 states correct. (Penalise * errors only once in the question).

3M1: 3^rd stage completed. Bod if something in each cell.

4A1ft: A or B state correct. (Penalise * errors only once in the question).

5A1ft: A and B states correct. (Penalise * errors only once in the question).

4M1: 4^th stage completed. Bod if something in each cell.

6A1ft: Final, state correct. (Penalise * errors only once in the question).

7A1ft: CAO

Mark scheme (b)

Scheme	Marks
Optimal schedules are: London – A – D – G – I – London (or v.v.)	B1ft
London – A – E – F – I – London (or v.v)	B1
	(2)
	(13 marks)

Notes

1B1ft: 1 route correct, consistent with their working penalise reversed states again here. Condone absence of London

2B1: both routes cao. London to London.