Hungarian Method for Solving Assignment Problems
Person
Mathematics formulation of assignment problem
Step 2:-
Search for an optimal assignment in the finally modified cost matrix
as follows:-
(i)
Examine the first row. If there is only one zero in it , then “enclose” this zero
is a box and “cross”(×) all the zeros in the column passing through the
enclosed zero. Next, examine the second row, third row, ... and repeat the 5am
e procedure as for the first row for each row having exactly one zero. If any row
has more than one zero, then do not touch that row and pass on to the next
row.
(ii)
Repeat the procedure of(i) above successively for the columns, starting ·
from the first column of the matrix obtained after step (i). It is quite likely that
there is no row or column having only one zero. In this case, arbitrarily select a
row or column having. the minimum number of zeros. In the row or column thus
chosen, enclose one zero and cross the remaining zeros in the column and row
passing through the enclosed zero. Continue steps (i) and (ii) alternately until
all the zeros have been enclosed or crossed.
Step 3:-
If each row and each column of the reduced matrix has exactly one
enclosed zero (so that the number of enclosed zeros is n), then the enclosed
zeros yield an optimal assignment. If not, then go to the next step.
Step 4:-
Draw minimum number of horizontal and/or vertical lines to cover all
the zeros (enclosed as-well-as crossed) of the reduced matrix. Since the
assignment is not optimal, the number of these lines will be less than n. In order
to move towards optimality, generate more zeros as follows : (i) Find the
smallest of the elements of the reduced matrix not covered by any of the lines
above. Let this element be a. (ii) Subtract a from each of the elements not
covered by the lines and add a to the element(s) at the intersection of these
lines. Do not change the remaining elements.
Step 5:-
Go to Step 2 and repeat the procedure till an optimal assignment is
achieved
.
A Rule to Draw Minimum Number of Lines
A convenient procedure to draw minimum number of lines to cover all the zeros
of the reduced matrix is as follows :-
rows.
(i)
Tick
(
✓
)
rows which do not have any enclosed zero.
(ii) Tick
(
✓
)
columns which have zeros (enclosed or crossed) in ticked
(iii) Tick
(
✓
)
rows which have enclosed zeros in ticked columns.
(iv) Repeat Steps (ii) and (iii) until the chain of ticking is completed.
(v)
Draw lines through all un ticked rows and ticked columns.
Thus the system of minimum number of lines covering all the zeros is obtained.
Note.
The operation in (ii) of step 4 is equivalent to :
(1)
subtracting a from all the elements of the cost matrix,
(2) adding a to all the elements of the covered rows,
(3) adding a to all the elements of the covered columns
Examples
Q
u
e
s
1
:
-
S
o
l
v
e
t
h
e
f
o
l
l
o
w
i
n
g
m
i
n
i
m
a
l
a
s
s
i
g
n
m
e
n
t
p
r
o
b
l
e
m
;
-
-
Man 1 2 3 4
Job
I
II
III
IV
Step 1
:-Subtracting the smallest element of each row from all the elements
given in that row, we obtain the reduced matrix (a) given below:
1 2 3 4 1 2 3 4
I I
II II
III III
IV IV
M
a
t
r
i
x
(
a
)
M
a
t
r
i
x
(
b
)
further, subtracting the smallest element of each column from all the elements t
of that column, we get the reduced matrix (b) given above.
Step 2
:-
Now we search an optimal assignment in the reduced matrix (b) follows:
starling with the first row, we examine the rows successively until a row with
exactly one zero is found. Row 1 has exactly one zero, we enclose it in a box.
Row 2 also has exactly one zero, we enclose it in a box. Then row 4 has
exactly ,, zero, we . enclosed it also m a box and cross the other zero in its
column. Thus we get matrix (c) given below;
1
2
3
4
1
2
3
4
I
I
I
I
I
I
I
I
I
I
I
I
I
V
I
V
M
a
t
r
i
x
(
c
)
M
a
t
r
i
x
(
d
)
Further, column 2 of matrix (c) has exactly one unmarked zero, we enclose
zero in a box. Thus we obtain matrix (d) given above.
Step 3
. Since each row and each column in matrix (d) has exactly one
inclosed zero, we have attained the optimal assignment schedule. The optimal
assignment schedule is :
I
➔
l, II
➔
3, III
➔
2 IV
➔
4.
The mininum total cost for this assignment schedule is :
z = 12 + 9 + 25 + 14 = 60
.
Q
u
e
s
2
:
-
A
d
e
p
a
r
t
m
e
n
t
h
a
s
f
o
u
r
s
u
b
o
r
d
i
n
a
t
e
s
a
n
d
f
o
u
r
t
a
s
k
s
t
o
b
e
p
e
r
f
o
r
m
e
d
.
T
h
e
s
u
b
o
r
d
i
n
a
t
e
s
d
i
f
f
e
r
i
n
e
f
f
i
c
i
e
n
c
y
a
n
d
t
h
e
t
a
s
k
s
d
i
f
f
e
r
i
n
t
h
e
i
r
i
n
t
r
i
n
s
i
c
d
i
f
f
i
c
u
l
t
i
e
s
.
T
h
e
e
s
t
i
m
a
t
e
o
f
t
i
m
e
(
i
n
m
a
n
-
h
o
u
r
s
)
e
a
c
h
m
a
n
w
o
u
l
d
t
o
p
e
r
f
o
r
m
e
a
c
h
t
a
s
k
i
s
g
i
v
e
n
b
y
:
Subordinates
I
I
I
I
I
I
I
V
A
1
8
2
6
1
7
1
1
B
1
3
2
8
1
4
2
6
C
3
8
1
9
1
8
1
5
D
2
9
2
6
2
4
1
0
Solution:-
Step 1
. Subtracting the smallest element of each row from all the elements of
that row, we obtain the reduced matrix (a) given below:
I
I
I
I
I
I
I
V
A
7
1
5
6
0
B
0
1
5
1
1
3
M
a
t
r
i
x
(
a
)
C
2
3
4
3
0
D
1
9
1
6
1
4
0
I
I
I
I
I
I
I
V
A
7
1
1
5
0
B
0
1
1
0
1
3
C
2
3
0
2
0
D
1
9
1
2
1
3
0
M
a
t
r
i
x
(
b
)
Step 2:-
We examine the rows of matrix (b) successively until a row with exactly
one zero is found . Row I has exactly one zero, we enclose it in a box and tl8 all
the other zeros m its column. Then row 3 has exactly one unmarked cross we
enclose it in a box. Thus we obtain matrix (c) given below.
I
I
I
I
I
I
I
V
I
I
I
I
I
I
I
V
A
7
1
1
5
0
A
7
1
1
5
0
B
0
1
1
0
1
3
B
0
1
1
0
1
3
C
2
3
0
2
0
C
2
3
0
2
0
D
1
9
1
2
1
3
0
D
1
9
1
2
1
3
0
M
a
t
r
i
x
(
c
)
M
a
t
r
i
x
(
d
)
Step 3
. Matrix (d) does not provide an optimal solution, since the fourth row as-
well-as the third column do not have an enclosed zero.
Step 4.
We draw the minimum number of horizontal and/or vertical ruies to
cover all the zeros of the reduced matrix (d) as follows :
(i) Since the fourth row does not have an enclosed zero, we tick
(
✓
)
this row :
(ii) Now there is a zero in the fourth column of the ticked row. So we tick the
fourth column.
(iii) There is an enclosed zero in the first row of the ticked column. So we tick
the first row. , al] Since the chain of ticking has been completed, we draw lines
through / un ticked rows and ticked columns as shown m the matrix (e) below
I
I
I
I
I
I
I
V
A
7
1
1
5
0
✓
B
-
-
-
-
-
0
-
-
-
-
-
-
-
-
-
1
1
-
-
-
-
-
-
-
-
-
0
-
-
-
-
-
-
-
-
-
-
1
3
-
-
-
-
C
-
-
-
-
-
2
3
-
-
-
-
-
-
-
-
0
-
-
-
-
-
-
-
-
-
2
-
-
-
-
-
-
-
-
-
-
-
0
-
-
-
-
-
-
D
1
9
1
2
1
3
0
✓
M
a
t
r
i
x
(
e
)
✓
The smallest elements in matrix (e) not covered by any of the lines above is 5.
Subtracting this elements from all the uncovered elements and adding the
same to the elements lying at the intersection of these lines , we obtain matrix
(f) given below.
3
2
1
I
I
I
I
I
I
I
V
I
I
I
I
I
I
I
V
A
2
6
0
0
A
2
6
0
0
B
0
1
1
0
1
8
B
0
1
1
0
1
8
C
2
3
0
2
5
C
2
3
0
2
5
D
1
4
7
8
0
D
1
4
7
8
0
M
a
t
r
i
x
(
f
)
M
a
t
r
i
x
(
g
)
S
t
e
p
5
.
F
o
l
l
o
w
i
n
g
t
h
e
p
r
o
c
e
d
u
r
e
o
f
e
n
c
l
o
s
i
n
g
a
n
d
c
r
o
s
s
i
n
g
t
h
e
z
e
r
o
s
(
a
s
i
n
S
t
e
p
2
)
i
n
m
a
t
r
i
x
(
f
)
,
w
e
o
b
t
a
i
n
m
a
t
r
i
x
(
g
)
g
i
v
e
n
a
b
o
v
e
.
S
t
e
p
6
.
S
i
n
c
e
e
a
c
h
r
o
w
a
n
d
e
a
c
h
c
o
l
u
m
n
i
n
m
a
t
r
i
x
(
g
)
h
a
s
e
x
a
c
t
l
y
o
n
e
e
n
c
l
o
s
e
d
z
e
r
o
,
w
e
h
a
v
e
a
t
t
a
i
n
e
d
t
h
e
f
o
l
l
o
w
i
n
g
o
p
t
i
m
a
l
a
s
s
i
g
n
m
e
n
t
s
c
h
e
d
u
l
e
:
A
➔
I
l
l
,
B
➔
I
,
C
➔
I
I
,
D
➔
I
V
.
T
h
e
m
i
n
i
m
u
m
t
o
t
a
l
t
i
m
e
f
o
r
t
h
i
s
a
s
s
i
g
n
m
e
n
t
s
c
h
e
d
u
l
e
i
s
:
z
=
1
7
+
1
3
+
1
9
+
1
0
=
5
9
m
a
n
-
h
o
u
r
s
.
ANSWER.
The Hungarian method is a computational procedure used to minimize the total cost of assigning n jobs to n persons with varying efficiencies. It involves modifying the cost matrix, searching for optimal assignments, and iteratively improving the solution until an optimal assignment is found. The method helps in achieving an efficient and cost-effective assignment solution for various job scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Lecture-1/2 ASSIGNMENT PROBLEMS Suppose there are n jobs to be performed and n persons are available for doing there jobs. Assume that each persons can do each job at a time , though with varying degree of efficiency. ijc thi thj Let be the cost if the person is assigned to the jobs. The problem is to find an assignment (which job should be assigned to which person , on a one to one basis) so that total cost of performing all the jobs is minimum. An assignment problem can be started in the form of m n cost matrix of real numbers as given in the following table-
Person 1 2 j n 1 C C C C 11 12 1 1 j n 2 C C C C 21 22 2 2 j n i C C C C 1 2 i i ij in n C C C C 1 2 n n nj nn Mathematics formulation of assignment problem n n = = Minimize Z C ijC ij = i 1 j 1
ASSIGNMENT ALGORITHMS HUNGARIAN METHOD FOR SOLVING ASSIGNMENT PROBLEMS: The computational procedure of the assignment algorithm consists of the following steps:- Step 1:-Modify the cost matrix by subtracting the smallest elements in each row from all the elements in that row. Similarly , modify the resulting cost matrix by subtracting the smallest elements in each column from all the elements in that column. The reduced cost matrix will than have non-negative elements with at least one zero in each row and each column. Obviously , any cell with zero entry is considered to be a candidate for an assignment.
Step 2:- Search for an optimal assignment in the finally modified cost matrix as follows:- (i) Examine the first row. If there is only one zero in it , then enclose this zero is a box and cross ( ) all the zeros in the column passing through the enclosed zero. Next, examine the second row, third row, ... and repeat the 5am e procedure as for the first row for each row having exactly one zero. If any row has more than one zero, then do not touch that row and pass on to the next row. (ii) Repeat the procedure of(i) above successively for the columns, starting from the first column of the matrix obtained after step (i). It is quite likely that there is no row or column having only one zero. In this case, arbitrarily select a row or column having. the minimum number of zeros. In the row or column thus chosen, enclose one zero and cross the remaining zeros in the column and row passing through the enclosed zero. Continue steps (i) and (ii) alternately until all the zeros have been enclosed or crossed.
Step 3:-If each row and each column of the reduced matrix has exactly one enclosed zero (so that the number of enclosed zeros is n), then the enclosed zeros yield an optimal assignment. If not, then go to the next step. Step 4:-Draw minimum number of horizontal and/or vertical lines to cover all the zeros (enclosed as-well-as crossed) of the reduced matrix. Since the assignment is not optimal, the number of these lines will be less than n. In order to move towards optimality, generate more zeros as follows : (i) Find the smallest of the elements of the reduced matrix not covered by any of the lines above. Let this element be a. (ii) Subtract a from each of the elements not covered by the lines and add a to the element(s) at the intersection of these lines. Do not change the remaining elements. Step 5:-Go to Step 2 and repeat the procedure till an optimal assignment is achieved.
A Rule to Draw Minimum Number of Lines A convenient procedure to draw minimum number of lines to cover all the zeros of the reduced matrix is as follows :- rows. (i) Tick ( ) rows which do not have any enclosed zero. (ii) Tick ( ) columns which have zeros (enclosed or crossed) in ticked (iii) Tick ( ) rows which have enclosed zeros in ticked columns. (iv) Repeat Steps (ii) and (iii) until the chain of ticking is completed. (v) Draw lines through all un ticked rows and ticked columns. Thus the system of minimum number of lines covering all the zeros is obtained. Note. The operation in (ii) of step 4 is equivalent to : (1) subtracting a from all the elements of the cost matrix, (2) adding a to all the elements of the covered rows, (3) adding a to all the elements of the covered columns
Examples Ques 1:-Solve the following minimal assignment problem;-- Man 1 2 3 4 Job I II 12 30 21 15 18 33 9 31 44 25 24 21 III 23 30 28 14 IV Step 1:-Subtracting the smallest element of each row from all the elements given in that row, we obtain the reduced matrix (a) given below:
1 2 3 4 1 2 3 4 I I 9 0 18 9 3 0 14 9 3 24 0 22 9 20 0 22 II II 23 4 3 0 23 0 3 0 III III 9 16 14 0 9 12 14 0 IV IV Matrix(a) Matrix(b) further, subtracting the smallest element of each column from all the elements t of that column, we get the reduced matrix (b) given above.
Step 2:-Now we search an optimal assignment in the reduced matrix (b) follows: starling with the first row, we examine the rows successively until a row with exactly one zero is found. Row 1 has exactly one zero, we enclose it in a box. Row 2 also has exactly one zero, we enclose it in a box. Then row 4 has exactly ,, zero, we . enclosed it also m a box and cross the other zero in its column. Thus we get matrix (c) given below; 1 2 3 4 1 2 3 4 I I II II 9 O 14 9 3 0 14 9 3 20 0 22 9 20 0 22 III III 23 0 3 0 23 0 3 0 IV IV 9 12 14 0 9 12 14 0 Matrix (c) Matrix (d) Further, column 2 of matrix (c) has exactly one unmarked zero, we enclose zero in a box. Thus we obtain matrix (d) given above.
Step 3. Since each row and each column in matrix (d) has exactly one inclosed zero, we have attained the optimal assignment schedule. The optimal assignment schedule is : I l, II 3, III 2 IV 4. The mininum total cost for this assignment schedule is : z = 12 + 9 + 25 + 14 = 60. Ques 2:-A department has four subordinates and four tasks to be performed. The subordinates differ in efficiency and the tasks differ in their intrinsic difficulties. The estimate of time (in man-hours) each man would to perform each task is given by :
Subordinates I II III IV A 18 26 17 11 B 13 28 14 26 C 38 19 18 15 D 29 26 24 10 Solution:- Step 1. Subtracting the smallest element of each row from all the elements of that row, we obtain the reduced matrix (a) given below: I II III IV A 7 15 6 0 B 0 15 1 13 Matrix(a) C 23 4 3 0 D 19 16 14 0
I II III IV A 7 11 5 0 B 0 11 0 13 C 23 0 2 0 D 19 12 13 0 Matrix (b) Step 2:-We examine the rows of matrix (b) successively until a row with exactly one zero is found . Row I has exactly one zero, we enclose it in a box and tl8 all the other zeros m its column. Then row 3 has exactly one unmarked cross we enclose it in a box. Thus we obtain matrix (c) given below.
I II III IV I II III IV A 7 11 5 0 A 7 11 5 0 B 0 11 0 13 B 0 11 0 13 C 23 0 2 0 C 23 0 2 0 D 19 12 13 0 D 19 12 13 0 Matrix (c) Matrix (d) Step 3. Matrix (d) does not provide an optimal solution, since the fourth row as- well-as the third column do not have an enclosed zero. Step 4. We draw the minimum number of horizontal and/or vertical ruies to cover all the zeros of the reduced matrix (d) as follows : (i) Since the fourth row does not have an enclosed zero, we tick ( ) this row : (ii) Now there is a zero in the fourth column of the ticked row. So we tick the fourth column. (iii) There is an enclosed zero in the first row of the ticked column. So we tick the first row. , al] Since the chain of ticking has been completed, we draw lines through / un ticked rows and ticked columns as shown m the matrix (e) below
I II III IV 3 0 A 7 11 5 B ----- 0 --------- 11 --------- 0 ---------- 13 ---- C ----- 23 -------- 0 --------- 2 ----------- 0 ------ 1 D 19 12 13 0 Matrix (e) 2 The smallest elements in matrix (e) not covered by any of the lines above is 5. Subtracting this elements from all the uncovered elements and adding the same to the elements lying at the intersection of these lines , we obtain matrix (f) given below.
I II III IV I II III IV A 2 6 0 0 A 2 6 0 0 B 0 11 0 18 B 0 11 0 18 C 23 0 2 5 C 23 0 2 5 D 14 7 8 0 D 14 7 8 0 Matrix (f) Matrix (g) Step 5. Following the procedure of enclosing and crossing the zeros (as in Step 2) in matrix ( f), we obtain matrix (g) given above. Step 6. Since each row and each column in matrix (g) has exactly one enclosed zero, we have attained the following optimal assignment schedule : A Ill, B I, C II, D IV. The minimum total time for this assignment schedule is : z = 17 + 13 + 19 + 10 = 59 man-hours. ANSWER.
