D2 June 2012 Q7
7. Four workers, A, B, C and D, are to be assigned to four tasks, P, Q, R and S. Each worker is to be assigned to exactly one task and each task must be assigned to just one worker. The cost, in pounds, of using each worker for each task is given in the table below. The total cost is to be minimised.
| P | Q | R | S | |
|---|---|---|---|---|
| A | 23 | 41 | 34 | 44 |
| B | 21 | 45 | 33 | 42 |
| C | 26 | 43 | 31 | 40 |
| D | 20 | 47 | 35 | 46 |
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 \{\text{P, Q, R, S}\}\) | B1 |
| \[\begin{aligned}\text{minimise } P = {}&23x_{AP} + 41x_{AQ} + 34x_{AR} + 44x_{AS}\\ &+ 21x_{BP} + 45x_{BQ} + 33x_{BR} + 42x_{BS}\\ &+ 26x_{CP} + 43x_{CQ} + 31x_{CR} + 40x_{CS}\\ &+ 20x_{DP} + 47x_{DQ} + 35x_{DR} + 46x_{DS}\end{aligned}\] | 1M1 1A1 |
| Subject to \(x_{AP} + x_{AQ} + x_{AR} + x_{AS} = 1\) or \(\sum x_{Aj} = 1\) \(x_{BP} + x_{BQ} + x_{BR} + x_{BS} = 1\) or \(\sum x_{Bj} = 1\) \(x_{CP} + x_{CQ} + x_{CR} + x_{CS} = 1\) or \(\sum x_{Cj} = 1\) \(x_{DP} + x_{DQ} + x_{DR} + x_{DS} = 1\) or \(\sum x_{Dj} = 1\) \(x_{AP} + x_{BP} + x_{CP} + x_{DP} = 1\) or \(\sum x_{iP} = 1\) \(x_{AQ} + x_{BQ} + x_{CQ} + x_{DQ} = 1\) or \(\sum x_{iQ} = 1\) \(x_{AR} + x_{BR} + x_{CR} + x_{DR} = 1\) or \(\sum x_{iR} = 1\) \(x_{AS} + x_{BS} + x_{CS} + x_{DS} = 1\) or \(\sum x_{iS} = 1\) | 2M1 2A1 3M1 3A1 |
| (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’, but condone 2 slips.
1A1 CAO + minimise. Penalise reversed subscripts once only per question.
2M1 Four eqns, each in four vars, coeffs of 1, all 16 vars included, = 1, accept \(\leqslant 1, \geqslant 1\) here for this M only
2A1 Any 4 CAO. Penalise reversed subscripts once only per question.
3M1 All 8 equations, each in four variables, unitary coefficients, all 16 variables included = 1.
3A1 CAO. Penalise reversed subscripts once only per question.