Abstract
This thesis concentrates on sensitivity analysis of the semi-assignment problem (AP). Since there are identical tasks or works to be assigned in a company, the semi-AP can be more practical as a planning tool then classic assignment problem. Due to the high degeneracy of the semi-AP, traditional sensitivity analysis, which decides the perturbed range where the current optimal basis remains optimal, is impractical. Advanced sensitivity analysis of the semi-AP we proposed in this study is concerned with obtaining the perturbed range of cost coefficients that can be perturbed without the current positive variable set changing, but allowing the change of the degenerate basic variables or move to other extreme point when multiple optimal solution occurs. Concerning high degeneracy of the semi-AP, we can broaden the perturbed range by allowing that basis changing, as long as maintaining the same positive variable set of the current problem. In this thesis we propose an algorithm for determining the perturbed range of the assigned and unassigned cell. An illustrative example is presented in order to demonstrate the procedure of the proposed algorithm. Computational results will also provide to demonstrate the efficiency of the proposed algorithm. Keywords:Semi-assignment problem, sensitivity analysis, degeneracy.