D2 June 2017 Q4
4. 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 only one task and each task must be done by only one worker.
Worker A cannot do task 3 and worker D cannot do task 2
The cost, in pounds, of assigning each worker to each task is shown in the table below.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 53 | 84 | – | 20 |
| B | 87 | 72 | 41 | 38 |
| C | 70 | 51 | 52 | 25 |
| D | 45 | – | 81 | 70 |
The total cost is to be minimised.
Formulate the above situation 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.
| 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}\] | B1 | |||||||||||||||||||||||||
| where \(i \in \{A, B, C, D\}\) and \(j \in \{1, 2, 3, 4\}\) | B1 | |||||||||||||||||||||||||
| minimise \[\begin{aligned} C = {}& 53x_{A1} + 84x_{A2} + \text{'200'}x_{A3} + 20x_{A4} \\ &+ 87x_{B1} + 72x_{B2} + 41x_{B3} + 38x_{B4} \\ &+ 70x_{C1} + 51x_{C2} + 52x_{C3} + 25x_{C4} \\ &+ 45x_{D1} + \text{'200'}x_{D2} + 81x_{D3} + 70x_{D4} \end{aligned}\] | M1 A1 | |||||||||||||||||||||||||
| subject to \[\begin{aligned} x_{A1}+x_{A2}+x_{A3}+x_{A4} &= 1 &&\text{ or } \textstyle\sum x_{Aj} = 1\\x_{B1}+x_{B2}+x_{B3}+x_{B4} &= 1 &&\text{ or } \textstyle\sum x_{Bj} = 1\\x_{C1}+x_{C2}+x_{C3}+x_{C4} &= 1 &&\text{ or } \textstyle\sum x_{Cj} = 1\\x_{D1}+x_{D2}+x_{D3}+x_{D4} &= 1 &&\text{ or } \textstyle\sum x_{Dj} = 1\\x_{A1}+x_{B1}+x_{C1}+x_{D1} &= 1 &&\text{ or } \textstyle\sum x_{i1} = 1\\x_{A2}+x_{B2}+x_{C2}+x_{D2} &= 1 &&\text{ or } \textstyle\sum x_{i2} = 1\\x_{A3}+x_{B3}+x_{C3}+x_{D3} &= 1 &&\text{ or } \textstyle\sum x_{i3} = 1\\x_{A4}+x_{B4}+x_{C4}+x_{D4} &= 1 &&\text{ or } \textstyle\sum x_{i4} = 1 \end{aligned}\] | M1 A1 A1 | |||||||||||||||||||||||||
| 7 marks |
Notes
1B1: Possible values of \(x_{ij}\) (not just \(x\)) defined. Must be clear that \(x_{ij}\) can take only the two values of 0 and 1 and 1 must be attributed to the worker doing the task (i and j do not need to be mentioned here) and 0 otherwise
2B1: Defining the set of values for i and j – { } not required – this mark is not dependent on the first B mark
1M1: Attempt at a ‘16’ term expression, coefficients ‘correct’, 2 ‘large’ values (must be at least 88) included, condone 2 slips (a slip here is an x missing from a term, an incorrect coefficient, ij confused in a single term or a missing/extra term)
1A1: CAO + minimise
2M1: Four equations with four variable terms, unit coefficients, = 1, allow x missing and ij confused but not using \(x_{11}\) etc.
2A1: Any four equations CAO
3A1: All eight equations only CAO (ignore mention of \(x_{ij} \geqslant 0\))