Hungarian Method

Q1. Using the following Cost matrix determine (i) Optimal Job Assignment
                                                                       (ii)The cost of the assignment


                                       Jobs
                              1          2           3           4          5
Mechanic    A[     10          3            3           2          8
                   B       9            7           8           2           7
                   C       7            5           6           2           4
                   D       3            5           8           2           4
                   E       9            10          9           6         10


Soln:
STEP I:
Since the given matrix is a square Matrix (5 x 5) its balanced.
STEP II:

Process row wise

[ 8  1   1   0  6
  7  5   6   0  5
  5  3   4   0  2
  1  3   6   0  2
  3  4   3   0  4]

STEP III:

Process  Column wise for the above matrix

[ 7   0   0    0    4
  6   4   5    0    3
  4   2   3    0    0
  0   2   5    0    0
  2   3   2    0    2]

STEP IV:
Now we have drawn horizontal and vertical lines in such a way that most of the zeros are covered.
The number of Straight lines N=4
The order of matrix n=5
N<n

STEP V:
Since N<n
Therefore find out the smallest value from the above matrix .The smallest value is "2". Now subtract 2 fro the remaining values . Add "2" in the intersecting places "&" and "$" in the first row are the intersecting points.

[ 9  0   0  2   6
 6   2   3   0   3
 4   0   1   0   0
 0   0   3   0   0
 2   1   0   0   2]

Here all the columns are striked out as we have to cover most of the zeros.
Number of Straight lines N =5
Order of matrix n=5
Thus we get the optimal solution.

STEP VI:
Now we have to assign the jobs to the persons:
      1       2        3         4          5
A[  9       0        0         2          6
B   6        2        3        0           3
C   4        0        1        0           0
D   0        0        3        0           0
E   2        1        0         0           2]

1--> D ;  2-->A ;  3--->E ;  4--> B; 5--> C

Now we have to consider the original matrix and assign the values (ie., in each row we have "0" the value being assigned to the jobs) find the corresponding value in the original matrix

Minimum Cost= 3+3+9+2+4=Rs.21(this value no need to be unique as each of us will assign in different method)