Page 162 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 8: Assignment Problem – Unbalanced

Step 4: Using reduction rules. Notes
Row-wise reduction of the matrix.
Territory I II III IV
Salesman A 0 7 14 21
B 0 5 10 15
C 0 5 10 15
D 0 4 8 12

Step 5: Column-wise reduction of the matrix.
Territory I II III IV
Salesman A 0 3 6 9
B 0 1 2 3
C 0 1 2 3
D 0 0 0 0

Note: The above matrix which would have been used for making a trial assignment is not an
effective matrix because all the zeros either fall on a row or a column and further the matrix
cannot be reduced because each row has a zero element and each column has a zero element
respectively. Hence, Hungarian approach is to be used to overcome this limitation.

Hungarian Approach

Step 1:

Territory I II III IV
Salesman A 0 3 6 9
B 0 1 2 3
C 0 1 2 3
D 0 0 0 0
L1 L2

Step 2:
Territory I II III IV
Salesman A 0 2 5 8
B 0 0 1 2
C 0 0 1 2
D 1 0 0 0

Step 3: Further reduction of the matrix.

Territory I II III IV
Salesman A 0 2 5 8
B 0 0 1 2
C 0 0 1 2
D 0 0 0 0
L 1 L 2 L 3

LOVELY PROFESSIONAL UNIVERSITY 157