A2 October 2020 Q3

EdexcelCurrent spec16 marksTransportation Problems

3. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to three sales points, P, Q and R. It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

	P	Q	R	Supply
A	25	24	17	42
B	7	12	14	68
C	13	11	20	25
D	16	15	13	40
Demand	59	72	44

Table 1

Table 2 shows an initial solution given by the north-west corner method.

	P	Q	R
A	42
B	17	51
C		21	4
D			40

Table 2

(a) Taking AR as the entering cell, use the stepping-stone method to find an improved solution. Make your method 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

shadow costs
improvement indices
route
entering cell and exiting cell.

(4)

(c) Determine whether the solution obtained from this second iteration is optimal, giving the reason for your answer. (3)

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

(e) Explain why the Simplex algorithm cannot be used to solve transportation linear programming problems such as that formulated in (d). (1)

Mark scheme (a)

Scheme

Marks

	P	Q	R
A	\(42-\theta\)		\(\theta\)
B	\(17+\theta\)	\(51-\theta\)
C		\(21+\theta\)	\(4-\theta\)
D			(40)

	P	Q	R
A	38		4
B	21	47
C		25
D			40

M1
A1

2.1
1.1b

(2)

Notes

M1: a valid route, only one empty square used, \(\theta\)’s balance

A1: cao

Mark scheme (b)

Scheme

Marks

		\(25\)	\(30\)	\(17\)
		P	Q	R
\(0\)	A	X	\(-6\)	X
\(-18\)	B	X	X	\(15\)
\(-19\)	C	\(7\)	X	\(22\)
\(-4\)	D	\(-5\)	\(-11\)	X

M1
A1

1.1b
1.1b

	P	Q	R
A	\(38-\theta\)		\(4+\theta\)
B	\(21+\theta\)	\(47-\theta\)
C		(25)
D		\(\theta\)	\(40-\theta\)

	P	Q	R
A			42
B	59	9
C		25
D		38	2

1.1b

Entering cell is DQ and exiting cell is AP

2.2a

(4)

Notes

M1: Finding all 7 shadow costs and the 6 improvement indices for the correct 9 entries

A1: Shadow costs and II CAO

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

A1: CAO – including the deduction of all entering and exiting cells

Mark scheme (c)

Scheme

Marks

		\(14\)	\(19\)	\(17\)
		P	Q	R
\(0\)	A	\(11\)	\(5\)	X
\(-7\)	B	X	X	\(4\)
\(-8\)	C	\(7\)	X	\(11\)
\(-4\)	D	\(6\)	X	X

M1
A1

2.1
1.1b

No negative IIs so solution is optimal

2.4

(3)

Notes

M1: finding all 7 shadow costs and the 6 improvement indices – this mark is dependent on the previous M mark in (b) which will therefore indicate a correct mathematical argument leading from the initial solution to the confirmation or not of the optimality of the current solution

A1: CAO (shadow costs and IIs)

A1: CSO including the correct reasoning that the solution is optimal because there are no negative II

Mark scheme (d)

Scheme	Marks	AO
Let \(x_{ij}\) be the number of units (of stock) transported from (supply point) \(i\) to (sales point) \(j\)	B1	3.3
where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{\text{P, Q, R}\}\) \((x_{ij} \geqslant 0)\)	B1	3.3
Minimise \(25x_{\text{AP}} + 24x_{\text{AQ}} + 17x_{\text{AR}} + 7x_{\text{BP}} + 12x_{\text{BQ}} + 14x_{\text{BR}}\) \(\qquad + 13x_{\text{CP}} + 11x_{\text{CQ}} + 20x_{\text{CR}} + 16x_{\text{DP}} + 15x_{\text{DQ}} + 13x_{\text{DR}}\)	B1 B1	2.5 3.3
\(\sum x_{\text{A}j} \leqslant 42,\ \sum x_{\text{B}j} \leqslant 68,\ \sum x_{\text{C}j} \leqslant 25,\ \sum x_{\text{D}j} \leqslant 40\) accept \(=\)	B1	3.3
\(\sum x_{i\text{P}} \geqslant 59,\ \sum x_{i\text{Q}} \geqslant 72,\ \sum x_{i\text{R}} \geqslant 44\) accept \(=\)	B1	3.3
	(6)

Notes

B1: Correct definition of \(x_{ij}\)

B1: Correctly defining the set of values that \(i\) and \(j\) can take

B1: ‘Minimise’ + correct number of terms in objective

B1: Correct objective function

B1: Correct supply constraints (allow ‘equals’ or written out in full e.g. \(x_{\text{AP}} + x_{\text{AQ}} + x_{\text{AR}} \leqslant 42\))

B1: Correct demand constraints (allow ‘equals’ or written out in full)

Mark scheme (e)

Scheme	Marks	AO
The Simplex algorithm cannot be used as not all the constraints are in the form \(\sum x \leqslant k\) where \(k\) is a positive constant	B1	3.5b
	(1)
	(16 marks)

Notes

B1: Correct justification of why the Simplex algorithm cannot be used to solve transportation LP