The purpose of this thesis is to devise an algorithm for solving the Capacitated Facility Location Problem with Single Assignment. We use the Largrangean relaxation method to transform our problem into the Uncapacitated Facility Location Problem. It is well known that the Uncapacitated Facility Location Problem can be easily solved by the dual-based procedure. To select Lagrangean multiplier, we use Multiplier Adjustment Method taking advantage of the special structure of cost-matrix. In case that a facility cannot satisfy capacity constraint, we modify multiplier for assigning the customers which is allocated to the facility to other facilities. It has been proved that Multiplier Adjustment Method is one of the efficient tools for solving the location problem. Finally, it is shown that the proposed algorithm has satisfactory computational performance, compared with the other algorithms in the CPU time.
