Questions on the stepping-stone method

Question 1

Explain what the improvement index of an unused cell measures, and what a positive index tells you.

Accepted Answer

The index is the cell's cost minus its row shadow cost and its column shadow cost. It is the change in the total cost per unit sent along that route, once the rest of the plan has been adjusted to keep the supplies and demands satisfied. A positive index means using that route would raise the total, so the cell should stay empty. B1 for cost minus the two shadow costs, B1 for what the index measures, B1 for the positive case.

Question 2

A solution has R values A 0, B 3 and K values X 6, Y 4. The unused cell BX costs 8. Find its improvement index and say whether it is a candidate to enter.

Accepted Answer

Index = 8 − 3 − 6 = −1. It is negative, so the route is cheaper than the shadow costs predict and the cell is a candidate. M1 for cost minus the shadow costs, A1 for −1, B1 for the conclusion. Whether it actually enters depends on whether any other unused cell has a more negative index.

Question 3

State how the shadow costs are started, and explain why one of them may be chosen freely.

Accepted Answer

Set the first row's shadow cost R to zero and work outwards through the cells in use, each of which satisfies R + K = cost. B1 for setting one to zero and saying so. The equations fix only the sums R + K on the cells in use, so adding any number to every R and taking the same number off every K satisfies them equally well: the shadow costs are settled only up to that one free choice, and fixing one of them pins all the rest. B1 for the reason.

Question 4

State how the cost of an improved solution is found from the cost before it, and state the condition under which the method stops.

Accepted Answer

New cost = old cost + θ × (the improvement index of the entering cell), where θ is the number of units moved round the loop. B1. Since the entering cell's index is negative, that lowers the total by θ times its size.
The method stops when no improvement index is negative: no unused route would then reduce the total, and the solution is optimal. B1. Recalculating the new cost directly from the allocations is worth doing as well, because the two figures agreeing checks the loop and the index together.

Question 5

A transportation problem has supplies A 40, B 30, C 50 and demands X 35, Y 45, Z 40, with costs per unit AX 8, AY 5, AZ 6, BX 4, BY 9, BZ 7, CX 3, CY 6, CZ 5. Formulate it as a linear programming problem, and state why one of your constraints is redundant.

Accepted Answer

Define x_ij ≥ 0 as the number of units sent from source i to destination j, nine variables in all. The objective is to minimise C = 8x_AX + 5x_AY + 6x_AZ + 4x_BX + 9x_BY + 7x_BZ + 3x_CX + 6x_CY + 5x_CZ.
The constraints are one equation per source and one per destination: x_AX + x_AY + x_AZ = 40, x_BX + x_BY + x_BZ = 30, x_CX + x_CY + x_CZ = 50, x_AX + x_BX + x_CX = 35, x_AY + x_BY + x_CY = 45, x_AZ + x_BZ + x_CZ = 40, with every x_ij ≥ 0.
The problem is balanced, both sides totalling 120, so the three supply equations and the three demand equations add to the same thing: any five of the six force the sixth, and one is redundant. B1 for defining the variables in words, B1 for the objective, M1 for one equation per source and one per destination, A1 for all six correct with the non-negativity stated, B1 for the redundancy argument.

Question 6

During a stepping-stone improvement on a 3 by 4 problem, the two minus cells on the loop each hold 15. State the value moved, and explain what must be recorded before the next round of shadow costs is attempted, and why.

Accepted Answer

The value moved is the smallest minus-cell allocation, here 15, and it empties both minus cells at once. Only one of them may exit: the other stays in the solution with a recorded allocation of zero. The solution has become degenerate, and without the zero cell only five cells would remain against the 3 + 4 − 1 = 6 that the next round needs, too few to determine every shadow cost. B1 for moving 15, B1 for one cell exiting while the other keeps a zero allocation, B1 for the reason: six cells are needed for the shadow costs.

Question 7

A transportation problem has been balanced with a dummy destination D, so the supplies are A 30, B 25, C 35 and the demands are X 20, Y 30, Z 25 and D 15. Costs per unit are AX 7, AY 4, AZ 9, BX 5, BY 8, BZ 6, CX 3, CY 6, CZ 5, and 0 from every source to D. The current plan is AX 20, AY 10, BY 20, BZ 5, CZ 20, CD 15. Find the shadow costs and every improvement index, name the entering cell, and say what it would mean for a cell in the dummy column to enter the solution.

Accepted Answer

Six cells are in use against 3 + 4 − 1 = 6, so every shadow cost can be found. Setting R(A) = 0 and working through the cells in use: AX gives K(X) = 7, AY gives K(Y) = 4, BY gives R(B) = 8 − 4 = 4, BZ gives K(Z) = 6 − 4 = 2, CZ gives R(C) = 5 − 2 = 3, and CD gives K(D) = 0 − 3 = −3. M1 for working outwards from R(A) = 0, A1 for R 0, 4, 3 and K 7, 4, 2, −3.
A dummy column of zero costs does not force its shadow cost to be zero; it comes out negative here, and it is used like any other.
Indices, each cost − R − K: AZ = 9 − 0 − 2 = 7, AD = 0 − 0 + 3 = 3, BX = 5 − 4 − 7 = −6, BD = 0 − 4 + 3 = −1, CX = 3 − 3 − 7 = −7, CY = 6 − 3 − 4 = −1. M1 for cost − R − K, A1 for all six.
The most negative is −7, so CX enters. A1.
A cell in the dummy column entering would mean that source keeping some of its goods rather than sending them anywhere: nothing is actually moved and no real cost is met, and the plan records which source's supply goes unused. B1.

Question 8

A two by three problem has supplies A 40 and B 30, demands X 25, Y 30 and Z 15, and costs AX 6, AY 9, AZ 5, BX 4, BY 7, BZ 8. The cells in use are AX 25, AY 15, BY 15 and BZ 15, and setting R(A) = 0 gives R(B) = −2 with K(X) = 6, K(Y) = 9 and K(Z) = 10. Find the shadow costs that setting R(B) = 0 gives instead, and show that both sets give the same improvement indices.

Accepted Answer

Setting R(B) = 0 and working through the cells in use: BY gives K(Y) = 7, BZ gives K(Z) = 8, AY gives R(A) = 9 − 7 = 2, and AX gives K(X) = 6 − 2 = 4. M1 for working outwards from the other row, A1 for R 2 and 0 with K 4, 7 and 8.
Every R has risen by 2 and every K has fallen by 2, which leaves R + K unchanged on every cell.
The unused cells are AZ and BX. From the first set, AZ = 5 − 0 − 10 = −5 and BX = 4 + 2 − 6 = 0. From the second, AZ = 5 − 2 − 8 = −5 and BX = 4 − 0 − 4 = 0. A1 for the two pairs agreeing.
They must agree: the index is cost − R − K, and adding a constant to every R while taking it off every K leaves R + K alone, so nothing in the index moves. B1.

Question 9

Costs are AX 8, AY 5, AZ 6, BX 4, BY 9, BZ 7, CX 3, CY 6, CZ 5. The north-west corner solution is AX 35, AY 5, BY 30, CY 10, CZ 40, costing 835. Find the shadow costs and all four improvement indices.

Accepted Answer

Set R(A) = 0 and work outwards through the cells that are in use, since each of those satisfies R + K = cost. AX gives K(X) = 8 and AY gives K(Y) = 5. BY gives R(B) = 9 − 5 = 4, CY gives R(C) = 6 − 5 = 1, and CZ gives K(Z) = 5 − 1 = 4.
Each unused cell then has index cost − R − K. AZ = 6 − 0 − 4 = 2. BX = 4 − 4 − 8 = −8. BZ = 7 − 4 − 4 = −1. CX = 3 − 1 − 8 = −6.
M1 for setting R(A) = 0 and working outwards, A1 A1 for the R and K values, M1 for cost − R − K, A1 A1 for the four indices.
Write the R values down the side of the table and the K values along the top.

Question 10

Carry out the improvement. Name the entering cell, give the stepping-stone loop, state the value moved and the exiting cell, and give the new cost two ways.

Accepted Answer

The most negative index is −8, so BX enters. The loop turns only at cells that are in use, alternating signs: BX plus, BY minus, AY plus, AX minus, back to BX. The minus cells hold BY 30 and AX 35, so the value moved is 30 and BY exits. New allocations: AX 5, AY 35, BX 30, CY 10, CZ 40. Cost = 835 + 30(−8) = 595, and directly 5(8) + 35(5) + 30(4) + 10(6) + 40(5) = 40 + 175 + 120 + 60 + 200 = 595. B1 for BX entering, M1 for the stepping-stone loop, A1 for the alternating signs, A1 for moving 30, A1 for BY exiting, A1 for 595.

Question 11

In that first table the cell CX had the lowest cost of all nine at 3, yet BX entered. Explain why, without recalculating the indices.

Accepted Answer

The entering cell is chosen by improvement index, not by cost. The index already accounts for what the rest of the plan must give up to accommodate the new route, which the raw cost ignores. Here CX scored −6 against BX's −8, so a unit sent along BX saves more than one sent along CX even though CX looks cheaper on the table. B1 for the index rather than the cost deciding, B1 for what the index allows for, B1 for the comparison of −8 with −6.

Question 12

Continue from the solution costing 595. A second round of indices gives CX = −6 as the only negative one. Complete the problem and justify that your answer is optimal.

Accepted Answer

CX enters. The loop is CX plus, AX minus, AY plus, CY minus, back to CX. The minus cells hold AX 5 and CY 10, so the value moved is 5 and AX exits. New allocations: AY 40, BX 30, CX 5, CY 5, CZ 40. Cost = 595 + 5(−6) = 565, and directly 200 + 120 + 15 + 30 + 200 = 565. A third round of shadow costs gives R(A) 0, R(B) 2, R(C) 1, K(X) 2, K(Y) 5 and K(Z) 4, so the four remaining indices are AX 6, AZ 2, BY 2 and BZ 1. All are positive, so no unused route would reduce the total and 565 is optimal. B1 for CX entering, M1 for the loop, A1 for moving 5, A1 for AX exiting, A1 for the new allocations, A1 for 565, M1 for the third round of indices, B1 for the optimality statement.

Question 13

Supplies are A 25, B 35, C 20 and demands are X 25, Y 30, Z 25, with costs per unit AX 4, AY 6, AZ 8, BX 5, BY 7, BZ 6, CX 2, CY 8, CZ 5. The north-west corner method gave AX 25, BY 30, BZ 5, CZ 20, costing 440, with a zero allocation recorded in AY. Explain why the zero allocation is needed, find the shadow costs and the improvement indices, and carry out one improvement, giving the new cost.

Accepted Answer

Only four cells hold goods, one short of 3 + 3 − 1 = 5, because row A and column X ran out together. The zero cell AY counts as in use, and without it neither K(Y) nor anything beyond it could be reached from R(A) = 0.
Setting R(A) = 0: AX gives K(X) = 4, the zero cell AY gives K(Y) = 6, BY gives R(B) = 1, BZ gives K(Z) = 5, and CZ gives R(C) = 0.
Indices: AZ = 8 − 0 − 5 = 3, BX = 5 − 1 − 4 = 0, CX = 2 − 0 − 4 = −2, CY = 8 − 0 − 6 = 2. Only CX is negative, so CX enters.
The loop is CX plus, AX minus, AY plus, BY minus, BZ plus, CZ minus, a six-cell loop that turns at the zero cell. The minus cells hold AX 25, BY 30 and CZ 20, so the value moved is 20 and CZ exits.
New allocations: AX 5, AY 20, BY 10, BZ 25, CX 20. New cost = 440 + 20(−2) = 400, and directly 20 + 120 + 70 + 150 + 40 = 400. A further round gives indices AZ 3, BX 0, CY 4 and CZ 2, none negative, so 400 is optimal, and the zero at BX means a second plan achieves it too.
B1 for why the zero allocation is needed, M1 for the shadow costs, A1 for their values, A1 for the four indices, B1 for CX entering, M1 for the six-cell loop with alternating signs, A1 for moving 20 with CZ exiting, A1 for 400 checked both ways.

Question 14

An entering cell in row i and column j has cost c, and its stepping-stone loop runs to the cell in row i and column l, then to row k with column l, then to row k with column j and back, the other three cells all being in use. Show that moving θ units round the loop changes the total cost by θ times the entering cell's improvement index.

Accepted Answer

Round the loop the signs alternate: the entering cell gains θ, the cell in row i with column l loses θ, the cell in row k with column l gains θ and the cell in row k with column j loses θ. The change in total cost is therefore θ(c − c_il + c_kl − c_kj). M1 for the alternating sum of costs, multiplied by θ.
The other three cells are in use, so each of them satisfies R + K = cost: c_il = R_i + K_l, c_kl = R_k + K_l and c_kj = R_k + K_j. M1 for replacing each of them.
Substituting, the bracket is c − (R_i + K_l) + (R_k + K_l) − (R_k + K_j). The two K_l terms cancel and so do the two R_k terms, leaving c − R_i − K_j. A1 for the cancellation.
That is exactly the improvement index of the entering cell, so the change in cost is θ × (index). A1.
The same cancellation happens round a longer loop, because every row and every column the loop touches carries one cell gaining θ and one losing it, so every shadow cost appears once with each sign apart from R_i and K_j. B1 for the general case.

Question 15

A transportation problem has m sources and n destinations. Explain why the shadow costs can be found exactly when the solution uses m + n − 1 cells, saying what goes wrong with fewer and what having more would mean, and state the device that restores the count when a solution is short of cells.

Accepted Answer

There are m row shadow costs and n column shadow costs, so m + n unknowns in all. B1.
They are settled only up to adding a constant to every R and taking it off every K, so one of them is chosen freely, usually by setting the first R to zero, and m + n − 1 remain to be found. B1.
Each cell in use supplies one equation, R + K = cost, so m + n − 1 independent equations are needed, one per cell in use. M1 for counting one equation per cell in use, A1 for matching that against the m + n − 1 unknowns.
With fewer cells in use there are too few equations: some row or column is never reached from the one that was set to zero, its shadow cost stays undetermined, and the indices of the cells in it cannot be computed at all. That is degeneracy, and the device that fixes it is a zero allocation recorded in a suitable unused cell, which counts as in use and supplies the missing equation without moving any goods. B1.
More than m + n − 1 cells in use would mean the cells contained a closed loop, and the equations round that loop would over-determine the shadow costs: a plan with that many cells in use is not one the method produces. B1.