Page 143 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes 7.3 Mathematical Model of Assignment Problem

Minimize the total cost which is given by,

 
 
Where, i = 1, 2, 3,………n
j = 1, 2, 3,………n

Subject to restriction
X = 1 (One job is done by one worker)
ij
= 0 (No job is assigned)
X = 1 (only one job be assigned to one person)
ij
Where, j = 1,2, 3, …………………n
X = 1 (only one person can do one job at a time)
ij

Where, i=1, 2, 3,……….n
th
th
C  indicates the cost of assigning i job to j individual or vice versa, Vi = 1 to n.
ij ij
th
th
X  indicates whether i job is assigned to j person or not.
ij
th
th
X = 1 if i job is assigned to j person ‘0’ otherwise.
ij
Theorem Statement
It states that in an assignment problem if we add or subtract a constant to every element of any
row or column of the cost matrix (C ), then an assignment that minimizes the total cost on one
ij
matrix will also minimize the total cost on the other matrix.
Proof:
Let X = X X = elements of first cost matrix.
ij ij ij
X = elements of second cost matrix.
ij
   
 

      
 
X = i = 1.2.3…………….n
ij
j = 1.2.3…………….n
th
U  i row constant taken for reduction.
i
V j column constant taken for reduction.
th
j
Where, U and V are considered to be constant.
i j
       
    

138 LOVELY PROFESSIONAL UNIVERSITY