Find Solution of Assignment problem using Hungarian method (MIN case)
| Work\Job | I | II | III |
| A | 6 | 3 | 5 |
| B | 5 | 9 | 2 |
| C | 5 | 7 | 8 |
Solution:
The number of rows = 3 and columns = 3
| | `I` | `II` | `III` | |
| `A` | 6 | 3 | 5 | |
| `B` | 5 | 9 | 2 | |
| `C` | 5 | 7 | 8 | |
| | | | | |
Here given problem is balanced.
Step-1: Find out the each row minimum element and subtract it from that row
| | `I` | `II` | `III` | |
| `A` | 3 `3=6-3` | 0 `0=3-3` | 2 `2=5-3` | (-3) Minimum element of `1^(st)` row |
| `B` | 3 `3=5-2` | 7 `7=9-2` | 0 `0=2-2` | (-2) Minimum element of `2^(nd)` row |
| `C` | 0 `0=5-5` | 2 `2=7-5` | 3 `3=8-5` | (-5) Minimum element of `3^(rd)` row |
| | | | | |
Step-2: Find out the each column minimum element and subtract it from that column.
| | `I` | `II` | `III` | |
| `A` | 3 `3=3-0` | 0 `0=0-0` | 2 `2=2-0` | |
| `B` | 3 `3=3-0` | 7 `7=7-0` | 0 `0=0-0` | |
| `C` | 0 `0=0-0` | 2 `2=2-0` | 3 `3=3-0` | |
| | (-0) Minimum element of `1^(st)` column | (-0) Minimum element of `2^(nd)` column | (-0) Minimum element of `3^(rd)` column | |
Step-3: Make assignment in the opporunity cost table
a. Identify rows with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same column.
b. Identify columns with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same rows.
c. If a row and/or column has two or more unmarked 0 and one cannot be chosen by inspection, then choose the cell arbitarily.
d. Continue this process until all 0 in rows/columns are either assigned or cross off(
).
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(A,II)` is assigned
(2) Rowwise cell `(B,III)` is assigned
(3) Rowwise cell `(C,I)` is assigned
Rowwise & columnwise assignment shown in table
| | `I` | `II` | `III` | |
| `A` | 3 | [0] (1) Rowwise cell `(A,II)` is assigned | 2 | |
| `B` | 3 | 7 | [0] (2) Rowwise cell `(B,III)` is assigned | |
| `C` | [0] (3) Rowwise cell `(C,I)` is assigned | 2 | 3 | |
| | | | | |
Step-4: Number of assignments = 3, number of rows = 3
Which is equal, so solution is optimal
Optimal assignments are
| | `I` | `II` | `III` | |
| `A` | 3 Original cost 6 | [0] Original cost 3 | 2 Original cost 5 | |
| `B` | 3 Original cost 5 | 7 Original cost 9 | [0] Original cost 2 | |
| `C` | [0] Original cost 5 | 2 Original cost 7 | 3 Original cost 8 | |
| | | | | |
Optimal solution is
| Work | Job | Cost |
| `A` | `II` | 3 |
| `B` | `III` | 2 |
| `C` | `I` | 5 |
| | Total | 10 |
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
