D2 June 2014 Q6
6. Three warehouses, P, Q and R, supply washing machines to four retailers, A, B, C and D. The table gives the cost, in pounds, of transporting a washing machine from each warehouse to each retailer. It also shows the number of washing machines held at each warehouse and the number of washing machines required by each retailer. The total cost of transportation is to be minimised.
| A | B | C | D | Supply | |
|---|---|---|---|---|---|
| P | 11 | 22 | 13 | 17 | 25 |
| Q | 21 | 8 | 19 | 14 | 27 |
| R | 15 | 10 | 9 | 12 | 28 |
| Demand | 18 | 16 | 20 | 26 |
Formulate this transportation problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.
You do not need to solve this problem. (7)
| Scheme | Marks |
|---|---|
| Let \(x_{ij}\) be the number of washing machines transported from \(i\) to \(j\) where \(i \in \{\text{P, Q, R}\}\) and \(j \in \{\text{A, B, C, D}\}\) | B1 |
| The objective is to minimise \[\begin{aligned}C = {}&11x_{PA} + 22x_{PB} + 13x_{PC} + 17x_{PD}\\ &+ 21x_{QA} + 8x_{QB} + 19x_{QC} + 14x_{QD}\\ &+ 15x_{RA} + 10x_{RB} + 9x_{RC} + 12x_{RD}\end{aligned}\] | B1 B1 |
| Subject to \(x_{PA} + x_{PB} + x_{PC} + x_{PD} = 25\) or \(\sum x_{Pj} = 25\) | M1 |
| \(x_{QA} + x_{QB} + x_{QC} + x_{QD} = 27\) or \(\sum x_{Qj} = 27\) | A1 |
| \(x_{RA} + x_{RB} + x_{RC} + x_{RD} = 28\) or \(\sum x_{Rj} = 28\) \(x_{PA} + x_{QA} + x_{RA} = 18\) or \(\sum x_{iA} = 18\) \(x_{PB} + x_{QB} + x_{RB} = 16\) or \(\sum x_{iB} = 16\) \(x_{PC} + x_{QC} + x_{RC} = 20\) or \(\sum x_{iC} = 20\) | A1 |
| \(x_{PD} + x_{QD} + x_{RD} = 26\) or \(\sum x_{iD} = 26\) \(x_{ij} \geqslant 0\) | A1 |
| 7 marks |
Notes
1B1: Variables defined correctly – withhold this mark if definition of \(x_{ij}\) or the elements of sets \(i\) and \(j\) are inconsistent with their later use in the objective function and constraints. Penalise poor variable choice, (AP etc.) here.
2B1: Minimise + an attempt at an objective with at least 5 correct terms.
3B1: Objective function correct (minimised not required for this mark).
1M1: At least 3 ‘correct’ constraints listed with unit coefficients (accept = or any inequality for the M mark) – rhs values must be correct.
1A1: At least 3 correct constraints (accept consistent use of = or \(\leqslant\) on at least 3).
2A1: At least 6 correct constraints (accept consistent use of = or \(\leqslant\) on at least 6).
3A1: All 8 constraints correct (first seven constraints consistently either = or \(\leqslant\) but final constraint must be \(\geqslant 0\)).