A2 June 2025 Q3

EdexcelCurrent spec10 marksTransportation Problems

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, A, B, C and D, to three demand points, P, Q and R. It also shows the stock held at each supply point and the number of units required at each demand point.

A minimum cost solution is required.

	P	Q	R	Supply
A	27	23	25	35
B	29	30	28	41
C	29	33	26	29
D	32	34	36	45
Demand	57	31	62

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

(b) Perform one iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and stating the

shadow costs
improvement indices
entering cell and exiting cell

(4)

(c) Formulate the transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (5)

Mark scheme (b)

Scheme

Marks

		27	28	21
		P	Q	R
0	A	X	\(-5\)	4
2	B	X	X	5
5	C	\(-3\)	X	X
15	D	\(-10\)	\(-9\)	X

M1
A1

2.1
1.1b

	P	Q	R
A
B	\(22-\theta\)	\(19+\theta\)
C		\(12-\theta\)	\(17+\theta\)
D	\(\theta\)		\(45-\theta\)

	P	Q	R
A	35
B	10	31
C			29
D	12		33

Entering cell is DP and exiting cell is CQ

M1
A1

1.1b
2.2a

(4)

Notes

M1: Finding 7 shadow costs and 6 improvement indices

A1: Shadow costs and II correct (Alternative SC rows 27, 29, 32, 42 columns 0, 1, -6)

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

A1: CSO (for (b)) so all previous marks in this part must have been awarded – including exiting and entering cells stated correctly. Improved solution must be 6 numbers only with no additional 0 in CQ

Mark scheme (c)

Scheme	Marks	AO
Let \(x_{ij}\) be the number of units (of stock) transported from (supply point) \(i\) to (demand 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	2.5
Minimise \(27x_{\text{AP}} + 23x_{\text{AQ}} + 25x_{\text{AR}} + 29x_{\text{BP}} + 30x_{\text{BQ}} + 28x_{\text{BR}}\) \(+\, 29x_{\text{CP}} + 33x_{\text{CQ}} + 26x_{\text{CR}} + 32x_{\text{DP}} + 34x_{\text{DQ}} + 36x_{\text{DR}}\)	B1	3.3
\(\sum x_{\text{A}j} \leqslant 35,\ \sum x_{\text{B}j} \leqslant 41,\ \sum x_{\text{C}j} \leqslant 29,\ \sum x_{\text{D}j} \leqslant 45\) accept =	B1	3.3
\(\sum x_{i\text{P}} \geqslant 57,\ \sum x_{i\text{Q}} \geqslant 31,\ \sum x_{i\text{R}} \geqslant 62\) accept =	B1	3.3
	(5)
	(10 marks)

Notes

(c) Check all suffixes carefully for accuracy and consistency

B1: Correct definition of \(x_{ij}\) must clearly state that this is the number of units transported

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

B1: ‘Minimise’ + correct objective function

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

B1: Correct demand constraints with unit coefficients
(allow ‘equals’ or written out in full e.g. \(x_{AP} + x_{BP} + x_{CP} + x_{DP} \geqslant 57\))