D2 June 2006 Q6
6.
(a) Explain briefly the circumstances under which a degenerate feasible solution may occur to a transportation problem. (2)
(b) Explain why a dummy location may be needed when solving a transportation problem. (1)
The table below shows the cost of transporting one unit of stock from each of three supply points \(A\), \(B\) and \(C\) to each of two demand points 1 and 2. It also shows the stock held at each supply point and the stock required at each demand point.
| 1 | 2 | Supply | |
|---|---|---|---|
| \(A\) | 62 | 47 | 15 |
| \(B\) | 61 | 48 | 12 |
| \(C\) | 68 | 58 | 17 |
| Demand | 16 | 11 |
(c) Complete the table below to show a possible initial feasible solution generated by the north-west corner method.
| 1 | 2 | 3 | |
|---|---|---|---|
| \(A\) | |||
| \(B\) | 0 | ||
| \(C\) |
(1)
(d) Use the stepping-stone method to obtain an optimal solution and state its cost. You should make your method clear by stating shadow costs, improvement indices, stepping-stone route, and the entering and exiting squares at each stage. (10)
| Scheme | Marks |
|---|---|
| Either e.g. In an \(n \times m\) problem, a degenerate solution occurs when the number of cells used is less than \((n + m - 1)\) or e.g. when all the demand for one destination is satisfied by all the supply from a source, before the final demand and supplies are allocated | B2, 1, 0 |
| (2) |
Notes
B2 cao
B1 cloze “bod” is B1
| Scheme | Marks |
|---|---|
| If the total supply > total demand a dummy is used to absorb the excess | B1 |
| (1) |
Notes
B1 cao must (cannot decipher copy properly)
| Scheme | Marks | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| B1 | |||||||||
| (1) |
Notes
B1 cao total of five numbers
| Scheme | Marks | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Shadow costs \(S_A = 0\quad S_B = -1\quad S_C = -1\) \(D_1 = 62\quad D_2 = 49\quad D_3 = 1\) | |||||||||||||||||||||
| Improvement indices \(I_{A2} = 47 - 0 - 49 = -2^*\) \(I_{A3} = 0 - 0 - 1 = -1\) \(I_{C1} = 68 + 1 - 62 = 7\) \(I_{C2} = 58 + 1 - 49 = 10\) | |||||||||||||||||||||
| M1 A1 A1ft (3) | ||||||||||||||||||||
| Shadow costs \(S_A = 0\quad S_B = -1\quad S_C = -1\) \(D_1 = 62\quad D_2 = 47\quad D_3 = 1\) | |||||||||||||||||||||
| Improvement indices \(I_{A3} = 0 - 0 - 1 = -1^*\) \(I_{B2} = 48 + 1 - 47 = 2\) \(I_{C1} = 68 + 1 - 62 = 7\) \(I_{C2} = 58 + 1 - 47 = 12\) | |||||||||||||||||||||
| M1 A1 A1ft (3) | ||||||||||||||||||||
| |||||||||||||||||||||
| Shadow costs \(S_A = 0\quad S_B = -1\quad S_C = 0\) \(D_1 = 62\quad D_2 = 47\quad D_3 = 0\) | M1 A1 | ||||||||||||||||||||
| Improvement indices \(I_{B2} = 48 + 1 - 47 = 2\) \(I_{B3} = 0 + 1 - 0 = 1\) \(I_{C1} = 68 - 0 - 62 = 6\) \(I_{C2} = 58 - 0 - 47 = 11\) | B1 | ||||||||||||||||||||
| \(\therefore\) Optimal | |||||||||||||||||||||
| Cost 1497 units | B1 (4) | ||||||||||||||||||||
| (10) | |||||||||||||||||||||
| (14 marks) |
Notes
In the tables the shadow costs (ringed in the scheme) are shown in brackets.
(Corrected from the printed mark scheme: at the first stage the scheme prints \(\theta = 0\); the next table shows \(\theta = 11\), the smaller of 15 and 11.)