Q.5 (B) (ii) Solve the following assignment problem for minimization :
| Men \ Tasks (in hours) | I | II | III | IV |
|---|---|---|---|---|
| A | 7 | 25 | 26 | 10 |
| B | 12 | 27 | 3 | 25 |
| C | 37 | 18 | 17 | 14 |
| D | 18 | 25 | 23 | 9 |
Best answer
Answer: A \(\to\) I, B \(\to\) III, C \(\to\) II, D \(\to\) IV; minimum total time = 37 hours
Step 1 (row minimum): subtract 7, 3, 14, 9 from rows A, B, C, D.
| Men | I | II | III | IV |
|---|---|---|---|---|
| A | 0 | 18 | 19 | 3 |
| B | 9 | 24 | 0 | 22 |
| C | 23 | 4 | 3 | 0 |
| D | 9 | 16 | 14 | 0 |
Step 2 (column minimum): column minima are 0, 4, 0, 0; subtract 4 from column II.
| Men | I | II | III | IV |
|---|---|---|---|---|
| A | 0 | 14 | 19 | 3 |
| B | 9 | 20 | 0 | 22 |
| C | 23 | 0 | 3 | 0 |
| D | 9 | 12 | 14 | 0 |
Step 3: The minimum number of lines covering all zeros is 4 (column I, column III, column IV and row C), which equals the order of the matrix, so an optimal assignment can be made.
Row A has a single zero (A-I), row B has a single zero (B-III), row D has a single zero (D-IV). Then the zero at C-IV is crossed, and C gets II.
| Man | Task | Time (hours) |
|---|---|---|
| A | I | 7 |
| B | III | 3 |
| C | II | 18 |
| D | IV | 9 |
| Total | 37 |
Minimum total time = 37 hours.
Log in or create a free account to answer this question.
