A2 June 2022 Q6

EdexcelCurrent spec14 marksDynamic Programming

6. Bernie makes garden sheds. He can build up to four sheds each month.

If he builds more than two sheds in any one month, he must hire an additional worker at a cost of £250 for that month.

In any month in which sheds are made, the overhead costs are £35 for each shed made that month.

A maximum of three sheds can be held in storage at the end of any one month, at a cost of £80 per shed per month.

Sheds must be delivered at the end of the month.

The order schedule for sheds is

Month	January	February	March	April	May
Number ordered	1	3	3	5	2

There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery.

Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided below and state the minimum cost. (14)

Stage	State	Action	Value
May	2	0	160 = 160*
	1	1	80 + 35 = 115*
	0	2	70 = 70*

Month	January	February	March	April	May
Number made

Minimum cost:

Mark scheme

Scheme

Marks

Stage	State	Action	Value
May (2)	2	0	160 = 160*
	1	1	80 + 35 = 115*
	0	2	70 = 70*

Stage	State	Action	Dest	Value
April (5)	3	2	0	240 + 70 + 70 = 380*
		3	1	240 + 105 + 250 + 115 = 710
		4	2	240 + 140 + 250 + 160 = 790
	2	3	0	160 + 105 + 250 + 70 = 585*
		4	1	160 + 140 + 250 + 115 = 665
	1	4	0	80 + 140 + 250 + 70 = 540*

M1
A1
A1

3.1a
1.1b
1.1b

Stage	State	Action	Dest	Value
March (3)	3	1	1	240 + 35 + 540 = 815*
		2	2	240 + 70 + 585 = 895
		3	3	240 + 105 + 250 + 380 = 975
	2	2	1	160 + 70 + 540 = 770*
		3	2	160 + 105 + 250 + 585 = 1100
		4	3	160 + 140 + 250 + 380 = 930
	1	3	1	80 + 105 + 250 + 540 = 975*
		4	2	80 + 140 + 250 + 585 = 1055
	0	4	1	140 + 250 + 540 = 930*

M1
A1ft
A1

3.1a
1.1b
1.1b

Stage	State	Action	Dest	Value
Feb (3)	3	0	0	240 + 930 = 1170
		1	1	240 + 35 + 975 = 1250
		2	2	240 + 70 + 770 = 1080*
		3	3	240 + 105 + 250 + 815 = 1410
	2	1	0	160 + 35 + 930 = 1125*
		2	1	160 + 70 + 975 = 1205
		3	2	160 + 105 + 250 + 770 = 1285
		4	3	160 + 140 + 250 + 815 = 1365
	1	2	0	80 + 70 + 930 = 1080*
		3	1	80 + 105 + 250 + 975 = 1410
		4	2	80 + 140 + 250 + 770 = 1240
	0	3	0	105 + 250 + 930 = 1285*
		4	1	140 + 250 + 975 = 1365

M1
A1ft
A1ft
A1

1.1b
1.1b
1.1b
1.1b

Stage	State	Action	Dest	Value
Jan (1)	0	1	0	35 + 1285 = 1320
		2	1	70 + 1080 = 1150*
		3	2	105 + 250 + 1125 = 1480
		4	3	140 + 250 + 1080 = 1470

M1
A1

1.1b
1.1b

Month	January	February	March	April	May
Number made	2	2	4	4	2

2.2a

Minimum Cost: (£) 1150

1.1b

(14 marks)

Notes

All M marks – must bring earlier optimal results into calculations. Ignore extra rows. Must have right ‘ingredients’ (storage costs, overhead costs and additional workers) at least once per stage. Ingredients may be summed into a single figure. Correct total figure implies correct calculation. Penalise lack of * only once per question.

M1: Second stage completed. 6 rows, something in each cell.

A1: Any two states correct

A1: CAO for second stage

M1: Third stage completed. 9 rows with correct state, action and destination. Something in each cell. Condone at least 8 rows, with correct state, action and destination.

A1ft: Any two states correct – ft their optimal values

A1: CAO for third stage

M1: Fourth stage completed. 13 rows, with correct state, action and destination. Something in each cell. Condone at least 11 rows, with correct state, action and destination.

A1ft: Any two states correct – ft their optimal values

A1ft: Any three states correct – ft their optimal values

A1: CAO for fourth stage

M1: Fifth stage completed. 4 rows, something in each cell.

A1: CAO for fifth stage

B1: Correct allocation (dependent on all previous M marks)

B1: Correct minimum cost (dependent on all previous M marks)