D2 January 2006 Q3
3. Three depots, F, G and H, supply petrol to three service stations, S, T and U. The table gives the cost, in pounds, of transporting 1000 litres of petrol from each depot to each service station.
| S | T | U | |
|---|---|---|---|
| F | 23 | 31 | 46 |
| G | 35 | 38 | 51 |
| H | 41 | 50 | 63 |
F, G and H have stocks of 540 000, 789 000 and 673 000 litres respectively.
S, T and U require 257 000, 348 000 and 412 000 litres respectively. The total cost of transporting the petrol is to be minimised.
Formulate this problem as a linear programming problem. Make clear your decision variables, objective function and constraints. (8)
| Scheme | Marks |
|---|---|
| Let \(x_{ij}\) be the number of units transported from \(i\) to \(j\), in 1000 litres where \(i \in \{\text{F, G, H}\}\) and \(j \in \{\text{S, T, U}\}\) | B2, 1, 0 (2) |
| Minimise \(C = 23x_{fs} + 31x_{ft} + 46x_{fu} +\) | B1 |
| \(35x_{gs} + 38x_{gt} + 51x_{gu} +\) | B1 (2) |
| \(41x_{hs} + 50x_{ht} + 63x_{hu}\) | |
| Unbalanced | |
| Subject to \(x_{fs} + x_{ft} + x_{fu} \leqslant 540\) \(x_{gs} + x_{gt} + x_{gu} \leqslant 789\) | M1 |
| \(x_{hs} + x_{ht} + x_{hu} \leqslant 673\) | A1 |
| \(x_{fs} + x_{gs} + x_{hs} \geqslant 257\) \(x_{ft} + x_{gt} + x_{ht} \geqslant 348\) \(x_{fu} + x_{gu} + x_{hu} \geqslant 412\) } accept = here | A1 (3) |
| \(x_{ij} \geqslant 0\) | B1 (1) |
| (8 marks) |
Notes
Accepted introduction of a dummy demand methods.
(Corrected from the printed mark scheme: \(x_{ft}\) is printed as \(x_{fft}\) in the objective, and the three demand constraints are printed with \(\leqslant\); with supply greater than demand they must be \(\geqslant\) (or =).)