D2 June 2015 Q5

EdexcelOld spec17 marksTransportation Problems

5. 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 sales points, P, Q and R. It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required.

	P	Q	R	Supply
A	20	5	13	74
B	7	15	8	58
C	9	14	21	63
D	22	16	10	85
Demand	145	57	78

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

	P	Q	R	Supply
A	74			74
B	58			58
C	13	50		63
D		7	78	85
Demand	145	57	78

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

(b) 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) State the cost of the solution you found in (b). (1)

(e) Formulate this problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (7)

Mark scheme (a)

Scheme

Marks

	P	Q
A	74 − \(\theta\)	\(\theta\)
B
C	13 + \(\theta\)	50 − \(\theta\)
D

giving

	P	Q	R
A	24	50
B	58
C	63
D		7	78

M1 A1

(2)

Notes

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

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

Mark scheme (b)

Scheme

Marks

Shadow costs		20	5	−1
		P	Q	R
0	A	X	X	14
−13	B	X	23	22
−11	C	X	20	33
11	D	−9	X	X

M1 A1

	P	Q
A	24 − \(\theta\)	50 + \(\theta\)
B
C
D	\(\theta\)	7 − \(\theta\)

giving

	P	Q	R
A	17	57
B	58
C	63
D	7		78

Entering cell DP, exiting cell DQ

M1 A1

(4)

Notes

b1M1: Finding 7 shadow costs and 6 Improvement indices

b1A1: Shadow costs [Alt: A(20), B(7), C(9), D(31), P(0), Q(−15), R(−21)] and improvement indices CAO

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

b2A1: CSO (for part (b)) (entering DP, and exiting DQ clearly stated)

Mark scheme (c)

Scheme

Marks

Shadow costs		20	5	8
		P	Q	R
0	A	X	X	5
−13	B	X	23	13
−11	C	X	20	24
2	D	X	9	X

Optimal since no negative improvement indices

M1 A1 A1

(3)

Notes

c1M1: Finding 7 shadow costs and all 6 IIs or at least 1 negative II found

c1A1: CAO for the shadow costs [Alt: A(20), B(7), C(9), D(22), P(0), Q(−15), R(−12)] and 6 positive II

c2A1: CSO (for part (c)) + reason + optimal

Scheme	Marks
(£) 2532	B1
	(1)

Mark scheme (e)

Scheme	Marks
Let \(x_{ij}\) be the number of units transported from \(i\) to \(j\)	B1
where \(i \in \{\text{A, B, C, D}\}\), \(j \in \{\text{P, Q, R}\}\) and \(x_{ij} \geqslant 0\)	B1
Minimise (\(C\) =) \(20x_{\text{AP}} + 5x_{\text{AQ}} + 13x_{\text{AR}} + 7x_{\text{BP}} + 15x_{\text{BQ}} + 8x_{\text{BR}} + 9x_{\text{CP}} + 14x_{\text{CQ}} + 21x_{\text{CR}} + 22x_{\text{DP}} + 16x_{\text{DQ}} + 10x_{\text{DR}}\)	M1 A1
Subject to \(x_{\text{AP}} + x_{\text{AQ}} + x_{\text{AR}} \leqslant 74\) or \(\sum x_{\text{A}j} \leqslant 74\) \(x_{\text{BP}} + x_{\text{BQ}} + x_{\text{BR}} \leqslant 58\) or \(\sum x_{\text{B}j} \leqslant 58\) \(x_{\text{CP}} + x_{\text{CQ}} + x_{\text{CR}} \leqslant 63\) or \(\sum x_{\text{C}j} \leqslant 63\) \(x_{\text{DP}} + x_{\text{DQ}} + x_{\text{DR}} \leqslant 85\) or \(\sum x_{\text{D}j} \leqslant 85\) \(x_{\text{AP}} + x_{\text{BP}} + x_{\text{CP}} + x_{\text{DP}} \leqslant 145\) \(\sum x_{i\text{P}} \leqslant 145\) \(x_{\text{AQ}} + x_{\text{BQ}} + x_{\text{CQ}} + x_{\text{DQ}} \leqslant 57\) or \(\sum x_{i\text{Q}} \leqslant 57\) \(x_{\text{AR}} + x_{\text{BR}} + x_{\text{CR}} + x_{\text{DR}} \leqslant 78\) or \(\sum x_{i\text{R}} \leqslant 78\)	M1 A1 A1
	(7)
	17 marks

Notes

e1B1: \(x_{ij}\) (not just \(x\)) defined correctly (must include ‘number of’ (oe) and ‘from \(i\) to \(j\)’ (oe)). Withold this mark if \(x_{ij}\) is further defined as taking the values of either 0 or 1

e2B1: Defining the set of values for \(i\) and \(j\) including non-negativity constraint - withold this mark if definition is inconsistent with their later use in the objective function and constraints (eg A, B,… in the definition but 1, 2,… used in constraints and objective)

e1M1: Objective function (allow one error either in coefficient or variable) – minimise not required for this mark

e1A1: CAO – Correct objective function and minimise

e2M1: At least 3 constraints listed with unit coefficients (accept = or any inequality for the M mark) – rhs values must be correct

e2A1: At least 5 correct constraints (accept consistent use of = or \(\leqslant\) on at least 5)

e3A1: All 7 constraint correct (accept consistent use of = or \(\leqslant\) on all 7)

Note: if there are inconsistencies between the constraints and the objective function then mark to the benefit of the candidate. For example, a candidate who correctly defines \(x_{ij}\) and its set of values and writes down the constraints correctly (based on their definition of \(x_{ij}\)) but in the objective function omits the \(x\) (so uses, for example, AP, AQ, etc.) then this would scored B1B1M0A0M1A1A1