D2 June 2017 Q2

EdexcelOld spec10 marksTransportation Problems

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

	1	2	3	4	Supply
A	15	17	20	11	33
B	12	11	18	21	21
C	18	13	10	16	25
Demand	21	17	28	13

(a) Use the north-west corner method to obtain an initial solution. (1)

(b) Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear. (2)

(c) Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell. (4)

(d) Determine whether your current solution is optimal, giving a reason for your answer. (3)

Mark scheme (b)

Scheme

Marks

	1	2	3	4
A	(21)	\(12-\theta\)		\(\theta\)
B		\(5+\theta\)	\(16-\theta\)
C			\(12+\theta\)	\(13-\theta\)

giving

	1	2	3	4
A	21			12
B		17	4
C			24	1

M1 A1

(2)

Notes

b1M1: A valid route, only one empty square A4 used, \(\theta\)’s balance – some candidates are verifying that A4 is the entering cell (which is fine). For those that start at an incorrect entering cell then the M marks only are available in subsequent parts (unless recovered to the answers given in the scheme)

b1A1: Correct route, up to an improved solution (six numbers no zeros) – if there is a zero in cell A2 then A0 unless corrected in part (b)

Mark scheme (c)

Scheme

Marks

Shadow costs		15	-2	5	11
		1	2	3	4
0	A	X	19	15	X
13	B	-16	X	X	-3
5	C	-2	10	X	X

M1 A1

	1	2	3	4
A	\(21-\theta\)			\(12+\theta\)
B	\(\theta\)	(17)	\(4-\theta\)
C			\(24+\theta\)	\(1-\theta\)

giving

	1	2	3	4
A	20			13
B	1	17	3
C			25

Entering cell B1, Exiting cell C4

M1 A1

(4)

Notes

c1M1: Finding 7 shadow costs and 6 improvement indices

c1A1: Shadow costs [Alt: A(15), B(28), C(20), 1(0), 2(-17), 3(-10), 4(-4)] and improvement indices CAO

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

c2A1: CSO (for part (c)) – so all previous marks in this part must have been awarded – including exiting and entering cells stated correctly (entering is B1 and exiting is C4) – six numbers no zeros

Mark scheme (d)

Scheme

Marks

Shadow costs		15	14	21	11
		1	2	3	4
0	A	X	3	-1	X
-3	B	X	X	X	13
-11	C	14	10	X	16

M1 A1

Not optimal as there is a negative improvement index (A3)

(3)

10 marks

Notes

d1M1: Finding 7 shadow costs and all 6 IIs or sufficient number of shadow costs for at least 1 negative II found

d1A1: CAO A3 = -1 as an II from correct working

d2A1: CSO (for part (d)) + not optimal + reason [Alt shadow costs: A(15), B(12), C(4), 1(0), 2(-1), 3(6), 4(-4)]