D2 June 2006 Q5

EdexcelOld spec12 marksDynamic Programming

5. Victor owns some kiosks selling ice cream, hot dogs and soft drinks.

The network below shows the choices of action and the profits, in thousands of pounds, they generate over the next four years. The negative numbers indicate losses due to the purchases of new kiosks.

Directed network from S to T through A to K with profits and losses on the arcs

Use a suitable algorithm to determine the sequence of actions so that the profit over the four years is maximised and state this maximum profit. (12)

Mark scheme

Scheme

Marks

Stage	State	Action	Value
1	H	HT	4*
	I	IT	3*
	J	JT	12*
	K	KT	20*
2	D	DH	2 + 4 = 6
		DI	4 + 3 = 7*
	E	EH	3 + 4 = 7*
		EI	4 + 3 = 7*
	F	FJ	10 + 12 = 22*
		FK	−8 + 20 = 12
	G	GJ	10 + 12 = 22
		GK	17 + 20 = 37*
3	A	AD	3 + 7 = 10
		AE	2 + 7 = 9
		AF	−5 + 22 = 17*
	B	BD	3 + 7 = 10
		BE	2 + 7 = 9
		BF	−6 + 22 = 16*
	C	CF	8 + 22 = 30*
		CG	−15 + 37 = 22
4	S	SA	2 + 17 = 19
		SB	3 + 16 = 19
		SC	−10 + 30 = 20*

Stage 1: M1 A1 (2)
Stage 2: M1 A1 A1 (3)
Stage 3: M1 A1ft A1ft (3)
Stage 4: M1 A1ft (2)

Route S C F J T £20 000

M1 A1 (2)

(12 marks)