D2 June 2013 Q2

EdexcelOld spec10 marksTransportation Problems

2. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to each of three demand points, 1, 2 and 3. 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	Supply
A	10	11	20	18
B	15	7	13	14
C	24	15	12	21
D	9	21	18	12
Demand	27	18	20

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

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

(c) Perform one further iteration of the stepping stone method 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
A	18
B	9 − \(\theta\)	5 + \(\theta\)
C		13 − \(\theta\)	8 + \(\theta\)
D	\(\theta\)		12 − \(\theta\)

giving

	1	2	3
A	18
B		14
C		4	17
D	9		3

M1 A1

(2)

Notes

b1M1 A valid route, only one empty square, D1, used, \(\theta\)’s balance.

b1A1 Correct route, up to an improved solution (six numbers no zeros)

Mark scheme (c)

Scheme

Marks

Shadow costs		10	22	19
		1	2	3
0	A	X	−11	1
−15	B	20	X	9
−7	C	21	X	X
−1	D	X	0	X

1M1 A1

	1	2	3
A	18 − \(\theta\)	\(\theta\)
B		14
C		4 − \(\theta\)	17 + \(\theta\)
D	9 + \(\theta\)		3 − \(\theta\)

giving

	1	2	3
A	15	3
B		14
C		1	20
D	12

(\(\theta\) = 3) entering cell A2, exiting cell D3

2M1 A1

(4)

Notes

c1M1 Finding 7 shadow costs and 6 Improvement indices

c1A1 Shadow costs [Alt: A(10), B(−5), C(3), D(9), 1(0), 2(12), 3(9)] and improvement indices CAO

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

c2A1 CSO (entering A2, and exiting D3 stated)

Mark scheme (d)

Scheme

Marks

Shadow costs		10	11	8
		1	2	3
0	A	X	X	12
−4	B	9	X	9
4	C	10	X	X
−1	D	X	11	11

M1 A1

Optimal since no negative improvement indices.

(3)

(10 marks)

Notes

d1M1 Finding 7 shadow costs and all 6 IIs or at least1 negative II found.

d1A1 CAO for the shadow costs [Alt: A(10), B(6), C(14), D(9), 1(0), 2(1), 3(−2)] and 6 positive IIs

d2A1 CSO (for part (d)) + optimal.