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 (a)
Scheme
Marks
AO
P
Q
R
A
35
B
22
19
C
12
17
D
45
B1
1.1b
(1)
Notes
B1: CAO for north-west corner method
Mark scheme (b)
Scheme
Marks
AO
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)\)
(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\))
3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, E, F, G and H, to three sales points, A, B and C. It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required.
A
B
C
Supply
E
23
28
22
21
F
26
19
29
32
G
29
24
20
29
H
24
26
19
23
Demand
45
19
23
(a) Explain why it is necessary to add a dummy demand point. (1)
(b) On Table 1 in the answer book, insert appropriate values in the dummy demand column, D. (1)
A
B
C
D
Supply
E
23
28
22
21
F
26
19
29
32
G
29
24
20
29
H
24
26
19
23
Demand
45
19
23
Table 1
After finding an initial feasible solution and applying one iteration of the stepping-stone method, the table becomes
A
B
C
D
E
21
F
19
13
G
6
23
H
5
18
(c) Starting with GD as the next entering cell, perform two further iterations of the stepping-stone method to obtain an improved solution. You must make your method clear by showing your routes and stating the
shadow costs
improvement indices
entering and exiting cells
(6)
(d) State the cost of the solution found in (c). (1)
(e) Determine whether the solution obtained in (c) is optimal, giving a reason for your answer. (3)
Mark scheme (a)
Scheme
Marks
AO
(total) demand \(\neq\) (total) supply
B1
1.2
(1)
Notes
B1: CAO (or to make demand = supply or because (total) supply > (total) demand (oe)) Accept e.g. A dummy demand of 18 is needed to meet supply or there is a total of 105 supply but only 87 demand
Mark scheme (b)
Scheme
Marks
AO
A
B
C
Dummy
Supply
E
23
28
22
0
21
F
26
19
29
0
32
G
29
24
20
0
29
H
24
26
19
0
23
Demand
45
19
23
18
B1
1.1b
(1)
Notes
B1: CAO Check 18 in demand row
Mark scheme (c)
Scheme
Marks
AO
A
B
C
D
E
F
\(19-\theta\)
\(13+\theta\)
G
\(6-\theta\)
\(\theta\)
H
\(5+\theta\)
\(18-\theta\)
A
B
C
D
E
21
F
13
19
G
23
6
H
11
12
Exiting cell is GB
M1 A1
2.1 1.1b
\(23\)
\(16\)
\(19\)
\(-1\)
A
B
C
D
\(0\)
E
X
\(12\)
\(3\)
\(1\)
\(3\)
F
X
X
\(7\)
\(-2\)
\(1\)
G
\(5\)
\(7\)
X
X
\(1\)
H
X
\(9\)
\(-1\)
X
M1 A1
1.1b 1.1b
A
B
C
D
E
F
\(13-\theta\)
\(\theta\)
G
H
\(11+\theta\)
\(12-\theta\)
A
B
C
D
E
21
F
1
19
12
G
23
6
H
23
Entering cell is FD and exiting cell is HD
M1 A1
1.1b 2.2a
(6)
Notes
M1: A valid route, only one empty square (GD) used, \(\theta\)s balance
A1: Correct route, up to an improved solution (seven numbers no zeros)
M1: Finding 8 shadow costs and 9 improvement indices
A1: Shadow costs and II correct (alternatives columns 0 -7 -4 -24 rows 23 26 24 24)
M1: A valid route, their most negative II chosen, only one empty square used, \(\theta\)s balance
A1: CSO (for part (c)) so all previous marks in this part must have been awarded – including exiting cells (GB and HD) and entering cell (FD) stated correctly (seven numbers no zeros)
Mark scheme (d)
Scheme
Marks
AO
(£)1882
B1
1.1b
(1)
Notes
B1: CAO
Mark scheme (e)
Scheme
Marks
AO
\(23\)
\(16\)
\(17\)
\(-3\)
A
B
C
D
\(0\)
E
X
\(12\)
\(5\)
\(3\)
\(3\)
F
X
X
\(9\)
X
\(3\)
G
\(3\)
\(5\)
X
X
\(1\)
H
X
\(9\)
\(1\)
\(2\)
M1 A1
2.1 1.1b
All II are non-negative so solution is optimal
A1
2.4
(3)
(12 marks)
Notes
M1: Finding 8 shadow costs and all 9 improvement indices (or 8 SC and at least 1 negative II)
A1: CAO for shadow costs and the 9 improvement indices (alternatives columns 0 -7 -6 -26 rows 23 26 26 24)
A1: CSO (for part (e)) + reason + optimal) accept positive instead of non-negative
3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point.
Q
R
S
Supply
A
23
18
12
45
B
8
10
14
27
C
11
14
21
34
D
19
15
11
50
Demand
75
37
44
The problem is partially described by the linear programming formulation below.
Let \(x_{ij}\) be the number of units transported from \(i\) to \(j\)
where \(\quad i \in \{\text{A, B, C, D}\}\) \(\qquad\quad\ j \in \{\text{Q, R, S}\}\) and \(x_{ij} \geqslant 0\)
(a) Write down, as inequalities, the constraints of the linear program. (2)
(b) Use the north-west corner method to obtain an initial solution to this transportation problem. (1)
(c) Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear. (2)
(d) Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the
(b) Explain precisely what the constraint \(\sum x_{i\text{R}} \geqslant 44\) means in the transportation problem. (2)
(c) Use the north-west corner method to obtain the cost of an initial solution to this transportation problem. (2)
(d) Perform one iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the
shadow costs
improvement indices
entering cell and exiting cell.
(4)
Mark scheme (a)
Scheme
Marks
AO
\(k = 39\)
B1
2.2a
(1)
Notes
B1: CAO
Mark scheme (b)
Scheme
Marks
AO
To ensure that the total amount transported to destination R from the four supply points cannot be less than the demand of 44
B2, 1, 0
2.4 2.4
(2)
Notes
B1: Partial correct reasoning – must include at least two of ‘destination R’, ‘supply points’, ‘cannot be less’/’must be at least’, ‘demand of 44’ oe (do not accept ‘greater than or equal to’)
B1: Fully correct reasoning – all points covered as stated above. No incorrect statement.
Mark scheme (c)
Scheme
Marks
AO
R
S
T
A
34
B
10
17
C
20
21
D
18
B1
1.1b
2942
B1
2.2a
(2)
Notes
B1: CAO for north-west corner method (six correct figures in correct cells only, no zeros)
B1: CAO for initial solution (2942)
Mark scheme (d)
Scheme
Marks
AO
\(23\)
\(37\)
\(39\)
R
S
T
\(0\)
A
X
\(-20\)
\(-15\)
\(-8\)
B
X
X
\(1\)
\(-12\)
C
\(14\)
X
X
\(-14\)
D
\(10\)
\(-3\)
X
M1 A1
2.1 1.1b
R
S
T
A
\(34-\theta\)
\(\theta\)
B
\(10+\theta\)
\(17-\theta\)
C
D
R
S
T
A
17
17
B
27
C
20
21
D
18
M1
1.1b
Entering cell is AS and exiting cell is BS
A1
2.2a
(4)
(9 marks)
Notes
M1: Finding 7 shadow costs and 6 improvement indices
A1: CAO
M1: A valid route shown, their most negative II chosen, only one empty square used, \(\theta\)’s balance
A1: cao – (no zeros) including deducing entering and exiting cells
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 four sales points, P, Q, R and S. 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
S
Supply
A
18
19
17
13
28
B
16
15
14
19
43
C
21
17
22
23
29
D
16
20
19
21
36
Demand
25
41
40
30
(a) Use the north-west corner method to obtain an initial solution. (1)
(b) Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear. (2)
(c) Perform one further 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)
(d) State the cost of the solution found in (c). (1)
(e) Determine whether the solution obtained in (c) is optimal, giving a reason for your answer. (3)
Mark scheme (a)
Scheme
Marks
AO
P
Q
R
S
A
25
3
B
38
5
C
29
D
6
30
B1
1.1b
(1)
Notes
B1: cao
Mark scheme (b)
Scheme
Marks
AO
P
Q
R
S
A
\(3-\theta\)
\(\theta\)
B
\(38+\theta\)
\(5-\theta\)
C
D
\(6+\theta\)
\(30-\theta\)
P
Q
R
S
A
25
3
B
41
2
C
29
D
9
27
M1 A1
2.1 1.1b
(2)
Notes
M1: A valid route shown, only one empty square used, \(\theta\)’s balance
A1: cao
Mark scheme (c)
Scheme
Marks
AO
\(18\)
\(12\)
\(11\)
\(13\)
P
Q
R
S
\(0\)
A
X
\(7\)
\(6\)
X
\(3\)
B
\(-5\)
X
X
\(3\)
\(11\)
C
\(-8\)
\(-6\)
X
\(-1\)
\(8\)
D
\(-10\)
\(0\)
X
X
M1 A1
1.1b 1.1b
P
Q
R
S
A
\(25-\theta\)
\(3+\theta\)
B
C
D
\(\theta\)
\(27-\theta\)
P
Q
R
S
A
28
B
41
2
C
29
D
25
9
2
M1
1.1b
Entering cell is DP and exiting cell is AP
A1
2.2a
(4)
Notes
M1: Finding all 8 shadow costs and the 9 improvement indices for the correct 9 entries
A1: Shadow costs and II cao
M1: A valid route shown, their most negative II chosen, only one empty square used, \(\theta\)’s balance
A1: cao – including the deduction (and stating) of all entering and exiting cells
Mark scheme (d)
Scheme
Marks
AO
(£)2258
B1
1.1b
(1)
Notes
B1: cao
Mark scheme (e)
Scheme
Marks
AO
\(8\)
\(12\)
\(11\)
\(13\)
P
Q
R
S
\(0\)
A
\(10\)
\(7\)
\(6\)
X
\(3\)
B
\(5\)
X
X
\(3\)
\(11\)
C
\(2\)
\(-6\)
X
\(-1\)
\(8\)
D
X
\(0\)
X
X
M1 A1
2.1 1.1b
A negative II so solution is not optimal
A1
2.4
(3)
(11 marks)
Notes
M1: Finding all 8 shadow costs and all 9 negative improvement indices or sufficient number of shadow costs for at least 1 negative II found – 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 negative II from correct working
A1: cso including the correct reasoning that the solution is not optimal because there is a negative II
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
AO
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
AO
\(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
M1
1.1b
Entering cell is DQ and exiting cell is AP
A1
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
AO
\(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
A1
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)\)
1. 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 each of four demand points, P, Q, R and S. It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.
P
Q
R
S
Supply
A
15
14
17
11
23
B
10
9
16
12
42
C
11
13
8
10
18
D
15
13
16
17
19
Demand
25
45
12
20
Table 1
Table 2 shows an initial solution given by the north-west corner method.
P
Q
R
S
A
23
B
2
40
C
5
12
1
D
19
Table 2
(a) Taking DQ 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 the
shadow costs
improvement indices
route
entering cell and exiting cell.
(4)
(c) Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer. (3)
(d) State the cost of the solution found in (b). (1)
Mark scheme (a)
Scheme
Marks
AO
P
Q
R
S
A
B
C
\(5-\theta\)
\(1+\theta\)
D
\(\theta\)
\(19-\theta\)
P
Q
R
S
A
23
B
2
40
C
12
6
D
5
14
1M1 1A1
2.1 1.1b
(2)
Notes
1M1: A valid route, only one empty square used, \(\theta\)’s balance. Note: If not entering in DQ, allow this mark for a valid route and entry in CP or DP only.
1A1: CAO
Mark scheme (b)
Scheme
Marks
AO
\(15\)
\(14\)
\(16\)
\(18\)
P
Q
R
S
\(0\)
A
X
\(0\)
\(1\)
\(-7\)
\(-5\)
B
X
X
\(5\)
\(-1\)
\(-8\)
C
\(4\)
\(7\)
X
X
\(-1\)
D
\(1\)
X
\(1\)
X
1M1 1A1
1.1b 1.1b
P
Q
R
S
A
\(23-\theta\)
\(\theta\)
B
\(2+\theta\)
\(40-\theta\)
C
D
\(5+\theta\)
\(14-\theta\)
P
Q
R
S
A
9
14
B
16
26
C
12
6
D
19
2M1
1.1b
Entering cell is AS and exiting cell is DS
2A1
2.2a
(4)
Notes
1M1: Finding (exactly) 8 shadow costs and (exactly) 9 improvement indices for their improved solution
1A1: Shadow costs [Alt: A(15), B(10), C(7), D(14), P(0), Q(−1), R(1), S(3)] and II CAO. Please check top table for Shadow Costs.
2M1: A valid route, their most negative II chosen, only one empty square used, \(\theta\)’s balance
2A1: CAO – including the deduction of all entering and exiting cells
Mark scheme (c)
Scheme
Marks
AO
\(15\)
\(14\)
\(9\)
\(11\)
P
Q
R
S
\(0\)
A
X
\(0\)
\(8\)
X
\(-5\)
B
X
X
\(12\)
\(6\)
\(-1\)
C
\(-3\)
\(0\)
X
X
\(-1\)
D
\(1\)
X
\(8\)
\(7\)
1M1 1A1
2.1 1.1b
A negative II so solution is not optimal
2A1
2.4
(3)
Notes
1M1: finding all 8 shadow costs and all 9 negative improvement indices or sufficient number of shadow costs for at least 1 negative II found (May just see SC: A, C, P and S and II: PC). 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
1A1: CAO negative II from correct working
2A1: CSO for (a), (b), (c) including the correct reasoning that the solution is not optimal because there is a negative II. Do not allow for ‘some IIs are not positive’ o.e. [Alt shadow costs: A(15), B(10), C(14), D(14), P(0), Q(−1), R(−6), S(−4)].
