D2 June 2014 (R) Q6
6. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker.
Worker C cannot do task 4 and worker D cannot do task 1.
The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 29 | 15 | 32 | 30 |
| B | 34 | 26 | 40 | 32 |
| C | 28 | 27 | 35 | – |
| D | – | 21 | 33 | 31 |
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (7)
| Scheme | Marks |
|---|---|
| Let \(x_{ij}\) be 0 or 1 \(\begin{cases}1 & \text{if worker } (i) \text{ does task } (j)\\ 0 & \text{otherwise}\end{cases}\) where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{1, 2, 3, 4\}\) | B1 |
| minimise \[\begin{aligned}C = {}&29x_{A1} + 15x_{A2} + 32x_{A3} + 30x_{A4}\\ &+ 34x_{B1} + 26x_{B2} + 40x_{B3} + 32x_{B4}\\ &+ 28x_{C1} + 27x_{C2} + 35x_{C3} + \text{‘100’}x_{C4}\\ &+ \text{‘100’}x_{D1} + 21x_{D2} + 33x_{D3} + 31x_{D4}\end{aligned}\] | M1 A1 |
| Subject to \(x_{A1} + x_{A2} + x_{A3} + x_{A4} = 1\) or \(\sum x_{Aj} = 1\) \(x_{B1} + x_{B2} + x_{B3} + x_{B4} = 1\) or \(\sum x_{Bj} = 1\) \(x_{C1} + x_{C2} + x_{C3} + x_{C4} = 1\) or \(\sum x_{Cj} = 1\) | M1 |
| \(x_{D1} + x_{D2} + x_{D3} + x_{D4} = 1\) or \(\sum x_{Dj} = 1\) | A1 M1 |
| \(x_{A1} + x_{B1} + x_{C1} + x_{D1} = 1\) or \(\sum x_{i1} = 1\) \(x_{A2} + x_{B2} + x_{C2} + x_{D2} = 1\) or \(\sum x_{i2} = 1\) \(x_{A3} + x_{B3} + x_{C3} + x_{D3} = 1\) or \(\sum x_{i3} = 1\) \(x_{A4} + x_{B4} + x_{C4} + x_{D4} = 1\) or \(\sum x_{i4} = 1\) | A1 |
| 7 marks |
Notes
1B1: Defining variables fully both ‘bits’ values and subscripts. Penalise poor variable choice, (AP etc.) here.
1M1: Attempt at a 16 term expression, coefficients ‘correct’, 2 ‘large’ values included, condone 2 slips.
1A1: CAO + minimise. Penalise reversed subscripts once only per question.
2M1: Four equations, each in four variables, unit coefficients, all 16 variables included, = 1, accept \(\leqslant 1, \geqslant 1\) here for this M only
2A1: Any 4 CAO.
3M1: All 8 equations, each in four variables, unit coefficients, all 16 variables included = 1.
3A1: CAO.