Abstract
Assignment problem (AP) is one of the well-known and important problems in mathematical programming. Although many studies have been made on algorithms for solving AP efficiently, few are concerning the AP with imprecise coefficients. Sensitivity analysis and fuzzy theory are the approaches mostly used to cope with uncertainty. We then deal with AP with uncertainty from points of sensitivity analysis and fuzzy theory. There are three parts in this dissertation. Firstly, this dissertation studies the traditional allowable range when perturbs exactly one element of the cost matrix of AP. Due to the inherently high degenerate of the optimal basic solution of AP, the traditional allowable range, over which the current optimal basic solution remains optimal, is impractical. This dissertation performs two other types of sensitivity analyses. One is to determine the range in which the current optimal assignment remains optimal. The other is to determine the range in which all the optimal assignments in the optimal set remain optimal. Secondly, we also study the range in which the current optimal assignment remains optimal or all the optimal assignments in the optimal set remain optimal while perturbing elements of one row (or column) of the cost matrix of AP simultaneously but either dependently or independently. Finally, this dissertation proposes a fuzzy AP model of which the elements of the cost matrix are subnormal fuzzy intervals. In addition, the total cost is restricted to a range as a fuzzy goal of the manager. By Bellman-Zadeh’s criterion, which equally emphasizes the performance of workers and manager, we show that the fuzzy AP model can be simplified into a linear fractional programming problem. An efficient algorithm will be developed to solve this model. The computational results show that the proposed l ling algorithm offers an effective and efficient way for handling the fuzzy assignment problem.