D2 June 2012 Q8

EdexcelOld spec12 marksDynamic Programming

8. A company makes industrial robots.

They can make up to four robots in any one month, but if they make more than three they will have to hire additional labour at a cost of £400 per month.

They can store up to two robots at a cost of £150 per robot per month.

The overhead costs are £300 in any month in which work is done.

Robots are delivered to buyers at the end of each month. There are no robots in stock at the beginning of January and there should be none in stock after the April delivery.

The order book for robots is

Month	January	February	March	April
Number of robots required	2	2	3	4

Use dynamic programming to determine the production schedule which minimises the costs, showing your working in the table provided in the answer book. (12)

Mark scheme

Scheme

Marks

E.g.

Stage	State	Action	Dest.	Value
April	0	4	0	400 + 300 = 700*
(4)	1	3	0	150 + 300 = 450*
	2	2	0	300 + 300 = 600*
March	0	3	0	300 + 700 = 1000*
(3)		4	1	400 + 300 + 450 = 1150
	1	2	0	150 + 300 + 700 = 1150
		3	1	150 + 300 + 450 = 900*
		4	2	400 + 150 + 300 + 600 = 1450
	2	1	0	300 + 300 + 700 = 1300
		2	1	300 + 300 + 450 = 1050*
		3	2	300 + 300 + 600 = 1200
Feb.	0	2	0	300 + 1000 = 1300
(2)		3	1	300 + 900 = 1200*
		4	2	400 + 300 + 1050 = 1750
	1	1	0	150 + 300 + 1000 = 1450
		2	1	150 + 300 + 900 = 1350*
		3	2	150 + 300 + 1050 = 1500
	2	0	0	300 + 1000 = 1300*
		1	1	300 + 300 + 900 = 1500
		2	2	300 + 300 + 1050 = 1650
Jan.	0	2	0	300 + 1200 = 1500*
(2)		3	1	300 + 1350 = 1650
		4	2	400 + 300 + 1300 = 2000

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

Month	Jan	Feb	March	April
Number made	2	3	3	3

B1 (1)

(12 marks)

Notes

ALL M marks - Must bring earlier optimal results into calculations. Ignore extra rows. Must have necessary right ‘ingredients’ (– storage costs, overheads, extra worker costs) at least once per stage.

1M1 First stage completed. 3 rows.

1A1 CAO condone missing * here. No extra rows.

2M1 Second stage completed. Expect 3 states.

2A1ft Any 2 states correct. Ft for * values only No missing/extra rows. (Penalise * errors only once in the qn).

3A1 CAO All 3 states correct. No missing rows. (Penalise * errors only once in the question).

3M1 3^rd stage completed. Expect 3 states.

4A1ft Any state correct. Ft on * values only. No missing rows. (Penalise * errors only once in the qn).

5A1ft Any 2 states correct. Ft on * values only. No missing rows. (Penalise * errors only once in the qn).

6A1 CAO All 3 states correct. No missing/extra rows. (Penalise * errors only once in the question).

4M1 4^th stage completed.

7A1 CAO Final, state correct. No missing/extra rows. (Penalise * errors only once in the question).

1B1 CAO. Must have attempted algorithm, getting at least one M mark.

Alt correct solution – adding the storage costs at start of month.

Stage	State	Action	Dest.	Value
April	0	4	0	400 + 300 = 700*	1M1
(4)	1	3	0	300 = 300*	1A1
	2	2	0	300 = 300*
March	0	3	0	300 + 700 = 1000*	2M1
(3)		4	1	400 + 150 + 300 + 300 = 1150
	1	2	0	300 + 700 = 1000
		3	1	150 + 300 + 300 = 750*	2A1ft
		4	2	400 + 300 + 300 + 300 = 1300
	2	1	0	300 + 700 = 1000
		2	1	150 + 300 + 300 = 750*	3A1
		3	2	300 + 300 + 300 = 900
Feb	0	2	0	300 + 1000 = 1300
(2)		3	1	150 + 300 + 750 = 1200*	3M1
		4	2	400 + 300 + 300 + 750 = 1750	4A1ft
	1	1	0	300 + 1000 = 1300
		2	1	150 + 300 + 750 = 1200*	5A1ft
		3	2	300 + 300 + 750 = 1350
	2	0	0	1000 = 1000*
		1	1	150 + 300 + 750 = 1200	6A1
		2	2	300 + 300 + 750 = 1350
Jan	0	2	0	300 + 1200 = 1500*	4M1
(2)		3	1	150 + 300 + 1200 = 1650
		4	2	400 + 300 + 300 + 1000 = 2000	7A1

Month	Jan	Feb	March	April
Number made	2	3	3	3	B1