Interior point approach to postoptimal analysis of the assignment problem /
Lorelyn R. Rivera
- 2003
- 39 leaves
Thesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2003
The assignment problem (AP) is a special case of linear programming with high degree of degeneracy, which can complicate postoptimal (sensitivity) analysis. The interior point method (IPM), in contrast, is not affected by degeneracy. Thus, this study proposed to use the IPM approach in doing sensitivity analysis on Aps. The method comprises the following: (1) formulating the cost-parameterized AP and solving it using the IPM; (2) obtaining the optimal partition from the generated interior solutions; and (3) determining the linearity interval of each perturbation parameters cijs and their corresponding shadow costs. The parametrized AP involves adding cij to one of the cost-coefficients in the objective function. When the AP is solved with IPM, it gives the resulting optimal partition, = (B,N), where B is the set of all optimal assignments (I,j)s; while those belonging in N are not. The associated cij of (i, j) N is a non-transition point with linear interval [LB, ), where LB is obtained by minimizing . its left-side and right-side slopes are all equal to 0. If (i, j) B, a transition point cij has a linearity interval [0,0] and left-side and right-side slopes equal to 1 and 0 respectively. A non-transition point cij has slopes all equal to 1 with linearity interval [-cij UB], where UB is obtained by maximizing . The sensitivity analysis done with IPM approach is indeed the most effective and efficient way for APs.