Page 144 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 7: Assignment Problem – Balanced

Notes
    
 

   
 
Since, terms that are subtracted from ‘Z’ to give ‘Z ’ are independent of x , it follows that ‘Z’ is
1 ij
minimized whenever ‘Z ’ is minimized and it can be proved conversely.
1

Notes In an assignment problem if a constant is added to or subtracted from every element
of any row or column of the cost matrix, an assignment that minimizes the total cost in one
matrix also minimizes the total cost in the other matrix.

Example: Reduction Theorem
Find the minimum cost for the following problem:

Persons
I II III IV
A 10 12 19 11
Tasks
B 5 10 7 8
C 12 14 13 11
D 8 15 11 9

(i) Row-wise reduction (ii) Column-wise reduction

I II III IV I II III IV
A 0 2 9 1 A 0 0 7 1

B 0 5 2 3 B 0 3 0 3
C 1 3 2 0 C 1 1 0 0
D 0 7 3 1 D 0 5 1 1

Hence, the assignment is
A  II 12

B  III 07
C  IV 11
D  I 08
` 38

Here minimized cost =  C X = ` 38
ij ij
Example: Solve the following assignment problem and find the minimum cost.

LOVELY PROFESSIONAL UNIVERSITY 139