D2 June 2012 Q3

Notes

Notes

EdexcelOld spec12 marksTransportation Problems

3. The table below shows the cost, in pounds, of transporting one tonne of concrete from each of three supply depots, A, B and C, to each of four building sites, D, E, F and G. It also shows the number of tonnes that can be supplied from each depot and the number of tonnes required at each building site. A minimum cost solution is required.

	D	E	F	G	Supply
A	17	19	21	20	18
B	21	20	19	22	23
C	18	17	16	21	29
Demand	15	24	18	13

The north-west corner method gives the following possible solution.

	D	E	F	G	Supply
A	15	3			18
B		21	2		23
C			16	13	29
Demand	15	24	18	13

Taking AG as the first entering cell,

(a) 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. (8)

(b) Determine whether your current solution is optimal. Justify your answer. (4)

Mark scheme (a)

Scheme

Marks

	D	E	F	G	Supply
A	15	3 − \(\theta\)		\(\theta\)	18
B		21 + \(\theta\)	2 − \(\theta\)		23
C			16 + \(\theta\)	13 − \(\theta\)	29
Demand	15	24	18	13	70

Exiting square is BF, (\(\theta\) = 2).

1M1 1A1

2M1 2A1

Improvement indices:
AF = 21 – 0 – 15 = 6
BD = 21 – 1 – 17 = 3
BF = 19 – 1 – 15 = 3
BG = 22 – 1 – 20 = 1
CD = 18 – 1 – 17 = 0
CE = 17 – 1 – 19 = −3

3A1

Entering square CE

	D	E	F	G	Supply
A	15	1 − \(\theta\)		2 + \(\theta\)	18
B		23			23
C		\(\theta\)	18	11 − \(\theta\)	29
Demand	15	24	18	13	70

Exiting square is AE, (\(\theta\) = 1).

3M1 4A1ft

	D	E	F	G	Supply
A	15			3	18
B		23			23
C		1	18	10	29
Demand	15	24	18	13	70

5A1 cso

(8)

Some candidates are starting by confirming that they should use AG as their first entering square. So if the candidate starts by finding initial shadow costs and II’s to confirm that AG has the most negative II, ignore this work and start marking from their first route. Do not credit shadow costs and IIs found here.

a1M1 A valid route, AG used as the empty square, \(\theta\)’s balance. If AG not used mark as a misread.

a1A1 A correct route, correctly stating exiting cell, up to my improved solution with no extra zeros.

a2M1 Finding 7 shadow costs and 6 IIs.

a2A1 Shadow costs CAO [Alt: A(17), B(18), C(18), D(0), E(2), F(−2), G(3)]

a3A1 Improvement indices CAO

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

a4A1ft a correct route, correctly stating entering cell, exiting cell.

a5A1 CSO, my solution no extra zeros.

Mark scheme (b)

Scheme

Marks

1M1 1A1

Improvement indices:
AE = 19 – 0 – 16 = 3
AF = 21 – 0 – 15 = 6
BD = 21 – 4 – 17 = 0
BF = 19 – 4 – 15 = 0
BG = 22 – 4 – 20 = −2
CD = 18 – 1 – 17 = 0

2A1

Not optimal since a negative improvement index

3A1ft

(4)

(12 marks)

Shadow costs

b1M1 Finding 7 shadow costs and all 6 IIs or at least 1 negative II found.

b1A1 Shadow costs CAO [Alt SC: A(17), B(21), C(18), D(0), E(−1), F(−2), G(3)]

b2A1 BG = −2 found as an II.

b3A1ft CAO + conclusion. If candidates go on to perform a third iteration and determine that it is optimal, please allow this final mark. Must make link between negative II and not optimal.

(Some glyphs are missing in the printed scheme’s tables; they are typed here from the working.)