D2 June 2016 Q5

EdexcelOld spec12 marksTransportation Problems

5. The table below shows the cost of transporting one unit of stock from each of four supply points, 1, 2, 3 and 4, to each of three demand points, A, B and C. It also shows the stock held at each supply point and the stock required at each demand point. A minimal cost solution is required.

	A	B	C	Supply
1	18	23	20	15
2	22	17	25	36
3	24	21	19	28
4	21	22	17	20
Demand	40	20	25

(a) Explain why it is necessary to add a dummy demand point. (1)

(b) Add a dummy demand point and appropriate values to Table 1 in the answer book. (1)

After one iteration of the stepping-stone method the table becomes

	A	B	C	D
1	15
2	19	17
3		3	25
4	6			14

(d) Taking D3 as the entering cell, use the stepping-stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells. (6)

(e) Determine whether your solution from (d) is optimal. Justify your answer. (3)

Scheme	Marks
(total) supply > (total) demand	B1
	(1)

Mark scheme (d)

Scheme

Marks

	A	B	C	D
1	15
2	19 − \(\theta\)	17 + \(\theta\)
3		3 − \(\theta\)	25	\(\theta\)
4	6 + \(\theta\)			14 − \(\theta\)

giving

	A	B	C	D
1	15
2	16	20
3			25	3
4	9			11

Exiting cell is B3

M1 A1

Shadow costs		18	13	16	−3
		A	B	C	D
0	1	X	10	4	3
4	2	X	X	5	−1
3	3	3	5	X	X
3	4	X	6	−2	X

Entering cell is C4

M1 A1

	C	D
1
2
3	25 − \(\theta\)	3 + \(\theta\)
4	\(\theta\)	11 − \(\theta\)

giving

	A	B	C	D
1	15
2	16	20
3			14	14
4	9		11

Exiting Cell is D4

M1 A1

(6)

Notes

d1M1: A valid route, only one empty square, D3 used, \(\theta\)’s balance

d1A1: Correct route, up to an improved solution (seven numbers no zeros)

d2M1: Finding 8 shadow costs and 9 improvement indices

d2A1: Shadow costs [Alt: A(0), B(−5), C(−2), D(−21), 1(18), 2(22), 3(21), 4(21)] and II CAO

d3M1: A valid route, their most negative II chosen, only one empty square used, \(\theta\)’s balance

d3A1: CSO (for part d) – so all previous marks in this part must have been awarded - including exiting and entering cells stated correctly

Mark scheme (e)

Scheme

Marks

Shadow costs		18	13	14	−5
		A	B	C	D
0	1	X	10	6	5
4	2	X	X	7	1
5	3	1	3	X	X
3	4	X	6	X	2

M1 A1

Optimal since no negative improvement indices

(3)

12 marks

Notes

e1M1: Finding 8 shadow costs and all 9 improvement indices or at least 1 negative II found

e1A1: CAO for the shadow costs [Alt: A(0), B(−5), C(−4), D(−23), 1(18), 2 (22), 3(23), 4(21)] and the 9 positive IIs

e2A1: CSO (for part e) + reason + optimal