D2 June 2009 Q7

EdexcelOld spec13 marksDynamic Programming

7. Minty has £250 000 to allocate to three investment schemes. She will allocate the money to these schemes in units of £50 000. The net income generated by each scheme, in £1000s, is given in the table below.

	£50 000	£100 000	£150 000	£200 000	£250 000
Scheme 1	60	120	180	240	300
Scheme 2	65	125	190	235	280
Scheme 3	55	110	170	230	300

Minty wishes to maximise the net income. She decides to use dynamic programming to determine the optimal allocation, and starts the table shown in your answer book.

(a) Complete the table in the answer book to determine the amount Minty should allocate to each scheme in order to maximise the income. State the maximum income and the amount that should be allocated to each scheme. (10)

(b) For this problem give the meaning of the table headings

(i) Stage,

(ii) State,

(iii) Action.

(3)

Mark scheme (a)

Scheme

Marks

Stage	State (in £1000s)	Action (in £1000s)	Dest. (in £1000s)	Value (in £1000s)
	250	250	0	300*
1	200	200	0	240*
	150	150	0	180*
	100	100	0	120*
	50	50	0	60*
	0	0	0	0*
	250	250	0	280 + 0 = 280
		200	50	235 + 60 = 295
		150	100	190 + 120 = 310*
		100	150	125 + 180 = 305
		50	200	65 + 240 = 305
		0	250	0 + 300 = 300
2	200	200	0	235 + 0 = 235
		150	50	190 + 60 = 250*
		100	100	125 + 120 = 245
		50	150	65 + 180 = 245
		0	200	0 + 240 = 240
	150	150	0	190 + 0 = 190*
		100	50	125 + 60 = 185
		50	100	65 + 120 = 185
		0	150	0 + 180 = 180
	100	100	0	125 + 0 = 125*
		50	50	65 + 60 = 125*
		0	100	0 + 120 = 120
	50	50	0	65 + 0 = 65*
		0	50	0 + 60 = 60
	0	0	0	0 + 0 = 0*
3	250	250	0	300 + 0 = 300
		200	50	230 + 65 = 295
		150	100	170 + 125 = 295
		100	150	110 + 190 = 300
		50	200	55 + 250 = 305
		0	250	0 + 310 = 310*

1M1 A1
A1
2M1 A1
A1
3M1 A1ft

Maximum income £310 000

Scheme	1	2	3
Invest (in £1000s)	100	150	0

B1 B1

(10)

Notes

(Corrected from the printed mark scheme: in Stage 2, State 250, the first row is printed with Action 280 and Value 200 + 0 = 280.)

Scheme	Marks
Stage: Scheme being considered	B1
State: Money available to invest	B1
Action: Amount chosen to invest	B1
	(3)
	(13 marks)