Assignment Problems – Hungerian Method
S. Y. B. Sc. (Computer Science)
Operation Research – Paper II
Assignment Problems
(Basics)
By- Mr. Sujit Chikurdekar
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
ASSIGNMENT ALGORITHM (THE HUNGARIAN METHOD):
This, method is dependent upon two vital theorems,
stated as below.
THEOREM 1:
If a constant is added (or subtracted) to every element
of any row (or column) of the cost matrix [𝐶𝑖𝑗 ] is an
assignment problem then an assignment which
minimizes the total cost for the new matrix will also
minimize the total cost matrix.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
The procedure of Hungarian Method is given as follows:
Step 1:
First check the given assignment problem is balanced or unbalanced
(i.e. no. of row & columns are equal or unequal)
a) If the given assignment problem is balanced then go to step 2.
b) If the given assignment problem is unbalanced then convert it into
balanced assignment problem by adding a dummy row or column
& go to step 2.
Step 2: Row reduction -
Find the smallest entry from each row & then subtract it from all the
entries from that respective row.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 3: Column reduction -
Find the smallest entry form each column & then subtract
it from all the entries from the respective column.
Step 4: Zero assignment –
a) Starting with first row of the matrix of step 2, examine
the rows one by one until a row containing exactly one
zero is found. Then mark to that zero & cross all the
zeroes in the column in which the assignment is made.
This procedure is repeated to all the rows.
b) Same procedure is repeated for column also.
Continue these successive operations on rows & columns
until all zeroes have either been assigned or crossed-out.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 5: Draw minimum number of line to cover all the zeroes -
To draw the minimum number of lines to cover all the zeroes we adopt
the following procedure.
i) Marks (√) to all rows in which the assignment has not been done.
ii) See the position of crossed zero in marked (√) row and then mark (√)
to the corresponding column.
iii) See the marked column and find the position of assigned zero’s and
mark (√) to the corresponding rows which are not marked till now.
iv) Draw the lines through unmarked rows and marked columns.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Note: If the above method does not work then make an arbitrary
assignment and then follow step 6.
Step 6:
Find the smallest element from all those elements which are
not covered (uncovered) on the line & subtract it from all
uncovered elements & add it to all those elements at the
intersection of two lines.
Now modify the matrix with the help of step 4 and find the
required assignment.
This procedure will be clearer by the following examples.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
EXAMPLES:
Find the optimal assignment for the following assignment problem.
I II III IV V
A 10 5 13 15 16
B 3 9 18 13 6
C 10 7 2 2 2
D 7 11 9 7 12
E 7 9 10 4 12
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Solution:
Step 1:
First check the given assignment problem is for
minimization of maximization and balanced or
unbalanced. (i.e. no. of rows & columns are equal or
not.)
The given assignment problem is for minimization
No. of rows = No. of columns
∴ The given problem assignment problem is balanced
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
I II III IV V
A 10 5 13 15 16
B 3 9 18 13 6
C 10 7 2 2 2
D 7 11 9 7 12
E 7 9 10 4 12
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 2:
Now find the smallest entry from each row & then
subtract it from all the entries from that respective row.
Here 5, 3, 2, 7 & 4 are the smallest elements in each
row resp. subtracting it from respective row we get
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 3:
Similarly, now find the smallest entry from each column & then
subtract it from all the entries from that respective column.
Here 0, 0, 0, 0 & 0 are the smallest elements in each column
resp. subtracting it from respective column we get
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 4:
Examine the rows one by one. If there is a single zero in any row then
assign it (i.e. mark the zero by ) and cross the zeroes in the respective
column. Same procedure is repeated for the column also. This procedure
continues till all the zeroes of the matrix are either assigned or crossed.
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Here we cannot get the assignment in
each and every row. Hence the
assignment is not optimal. We have to
improve the assignment and find the
optimal assignment.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 5:
(i) Tick mark (√) to all rows in which the assignment has not
been done.
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
(ii) See the position of crossed zero in marked (√) row
and then mark (√) to the corresponding column.
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
(iii) See the marked column and find the position of assigned
zero’s and mark (√) .
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
(iv) Draw the lines on unmarked rows and marked
columns.
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Now observe whether all zeroes are covered by the
line or not. If not then draw one more line to
cover that zero.
In the above the table 4th row and 1st column zero
is not covered. Hence draw one more line to cover
that zero.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
I II III IV V
A 5 0 8 10 11
B 0 6 15 10 3
C 8 5 0 0 0
D 0 4 2 0 5
E 3 5 6 0 8
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Find the smallest element from all those elements which are not covered
(uncovered) on the line & subtract it from all uncovered elements & add it
to all those elements at the intersection of two lines.
I II III IV V
A 5 0 8 13 11
B 0 6 15 13 3
C 8 5 0 3 0
D 0 4 2 3 5
E 0 2 3 0 5
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Step 6:
Now repeat the steps 4 and 5 till we get exactly one assignment in each row.
I II III IV V
A 5 0 8 13 11
B 0 6 15 13 3
C 8 5 0 3 0
D 0 4 2 3 5
E 0 2 3 0 5
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
(i) Tick mark (√) to all rows in which the assignment
has not been done.
(ii) See the position of crossed zero in marked (√) row
and then mark (√) to the corresponding column.
(iii) See the marked column and find the position of
assigned zero’s and mark (√) to the corresponding
rows which are not marked till now.
(iv) Draw the lines through unmarked rows and marked
columns.
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
I II III IV V
A 5 0 8 13 11
B 0 6 15 13 3
C 8 5 0 3 0
D 0 4 2 3 5
E 0 2 3 0 5
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Find the smallest element from all those elements which are not covered
(uncovered) on the line & subtract it from all uncovered elements & add it
to all those elements at the intersection of two lines.
I II III IV V
A 7 0 8 13 11
B 0 4 13 11 1
C 10 5 0 3 0
D 0 2 0 1 3
E 2 2 3 0 5
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Repeat the step 4 once again
I II III IV V
A 7 0 8 13 11
B 0 4 13 11 1
C 10 5 0 3 0
D 0 2 0 1 3
E 2 2 3 0 5
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Optimal Assignment:
A → II, B → I, C → 5, D → 3, E → 4
Optimal Cost = 5 + 3 + 2 + 9 + 4
= 23
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
Assignment Problems – Hungerian Method
Thank You
By- Mr. Sujit Chikurdekar, Dr. D. Y. Patil Arts, Commerce & Science College, Pimpri, Pune – 18.
