D2 June 2013 Q6
6. Three workers, Harriet, Jason and Katherine, are to be assigned to three tasks, 1, 2 and 3. Each worker must be assigned to just one task and each task must be done by just one worker.
The amount each person would earn, in pounds, while assigned to each task is shown in the table below.
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Harriet | 251 | 243 | 257 |
| Jason | 244 | 247 | 255 |
| Katherine | 249 | 252 | 246 |
The total income is to be maximised.
(a) Modify the table so it can be used to find the maximum income. (1)
(b) Formulate the above situation as a linear programming problem. You must define your decision variables and make your objective function and constraints clear. (7)
| Scheme | Marks |
|---|---|
| Since maximising subtract all elements from some \(n \geqslant 257\), say 260. \(\begin{bmatrix}9 & 17 & 3 \\ 16 & 13 & 5 \\ 11 & 8 & 14\end{bmatrix}\qquad\left(n = 257\ \begin{bmatrix}6 & 14 & 0 \\ 13 & 10 & 2 \\ 8 & 5 & 11\end{bmatrix},\quad n = 258\ \begin{bmatrix}7 & 15 & 1 \\ 14 & 11 & 3 \\ 9 & 6 & 12\end{bmatrix}\right)\) | B1 |
| (1) |
Notes
a1B1 CAO (o.e.)
| Scheme | Marks |
|---|---|
| \(x_{ij} = \begin{cases}1 & \text{if worker } i \text{ does task } j\\ 0 & \text{otherwise}\end{cases}\) | 1B1 |
| Where \(x_{ij}\) indicates worker \(i\) being assigned to task \(j\) \(i \in \{H, K, J\}\) and \(j \in \{1, 2, 3\}\) | 2B1 |
| (2) | |
| E.g. Minimise \(P = 9x_{H1} + 17x_{H2} + 3x_{H3} + 16x_{J1} + 13x_{J2} + 5x_{J3} + 11x_{K1} + 8x_{K2} + 14x_{K3}\) \((P = 6x_{H1} + 14x_{H2} + 13x_{J1} + 10x_{J2} + 2x_{J3} + 8x_{K1} + 5x_{K2} + 11x_{K3})\) \((P = 7x_{H1} + 15x_{H2} + x_{H3} + 14x_{J1} + 11x_{J2} + 3x_{J3} + 9x_{K1} + 6x_{K2} + 12x_{K3})\) OR maximise \(P = 251x_{H1} + 243x_{H2} + 257x_{H3} + 244x_{J1} + 247x_{J2} + 255x_{J3} + 249x_{K1} + 252x_{K2} + 246x_{K3}\) | 3B1 4B1 |
| (2) | |
| Subject to: \(x_{H1} + x_{H2} + x_{H3} = 1\) or \(\sum x_{Hj} = 1\) \(x_{J1} + x_{J2} + x_{J3} = 1\) or \(\sum x_{Jj} = 1\) \(x_{K1} + x_{K2} + x_{K3} = 1\) or \(\sum x_{Kj} = 1\) \(x_{H1} + x_{J1} + x_{K1} = 1\) or \(\sum x_{i1} = 1\) \(x_{H2} + x_{J2} + x_{K2} = 1\) or \(\sum x_{i2} = 1\) \(x_{H3} + x_{J3} + x_{K3} = 1\) or \(\sum x_{i3} = 1\) | M1 1A1 2A1 |
| (3) | |
| (7) | |
| (8 marks) |
Notes
b1B1 possible values of \(x_{ij}\) defined
b2B1 Defining \(x_{ij}\) including the set of values for \(i\) and \(j\)
b3B1 Objective function
b4B1 Minimise/Maximise but consistent with objective function
b1M1 Three equations, unit coefficients, =1
b1A1 Any three equations CAO (condone inconsistent notation)
b2A1 All six equations CAO (consistent notation required)