A2 October 2021 Q1
1. Four workers, A, B, C and D, are to be assigned to three tasks, 1, 2 and 3. Each task must be assigned to just one worker and each worker can do one task only.
Worker A cannot do task 2 and worker D cannot do task 3
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 | |
|---|---|---|---|
| A | 53 | – | 62 |
| B | 48 | 57 | 59 |
| C | 55 | 63 | 58 |
| D | 69 | 49 | – |
Formulate the above situation as a linear programming problem. You must define your decision variables and make the objective function and constraints clear. (6)
| Scheme | Marks | AO |
|---|---|---|
| Let \(x_{ij}\) be 0 or 1 \(\begin{cases} 1 & \text{if worker } (i) \text{ does task } (j) \\ 0 & \text{otherwise} \end{cases}\) | B1 | 3.3 |
| where \(i \in \{\text{A, B, C, D}\}\) and \(j \in \{1, 2, 3, 4\}\) | B1 | 2.5 |
| minimise \(C = 53x_{\text{A1}} + \text{‘100’}x_{\text{A2}} + 62x_{\text{A3}} + 48x_{\text{B1}} + 57x_{\text{B2}} + 59x_{\text{B3}}\) \(\qquad + 55x_{\text{C1}} + 63x_{\text{C2}} + 58x_{\text{C3}} + 69x_{\text{D1}} + 49x_{\text{D2}} + \text{‘100’}x_{\text{D3}}\) | M1 A1 | 3.3 1.1b |
| Subject to \(\sum x_{\text{A}j} = 1,\ \sum x_{\text{B}j} = 1,\ \sum x_{\text{C}j} = 1,\ \sum x_{\text{D}j} = 1\) \(\sum x_{i1} = 1,\ \sum x_{i2} = 1,\ \sum x_{i3} = 1,\ \sum x_{i4} = 1\) | M1 A1 | 3.3 1.1b |
| (6) | ||
| (6 marks) |
Notes
B1: Defining \(x_{ij}\) correctly
B1: Correct definition of the values that \(i\) and \(j\) can take
M1: Attempt at 12 term expression, coefficients ‘correct’, 2 ‘large’ values included, condone 2 slips.
A1: cao including ‘minimise’
M1: At least four correct equations, each in three or four variables, unit coefficients, equal to 1
A1: cao (all eight equations)
No dummy column can score a maximum of B1B0M1A1M0A0
No ‘large’ values in A2 and D3 can score a maximum B1B1M0A0M1A1
No ‘large’ values or dummy column can score a maximum of B1B0M0A0M0A0