000			02235nam a2200241 4500
001			UPMIN-00000009107
003			UPMIN
005			20230209140838.0
008			230209b |||||||| |||| 00| 0 eng d
040			_aDLC _cUPMin _dupmin
041			_aeng
090			_aLG993.5 2003 _bA64 R59
100	1		_aRivera, Lorelyn R. _92280
245	0	0	_aInterior point approach to postoptimal analysis of the assignment problem / _cLorelyn R. Rivera
260			_c2003
300			_a39 leaves
502			_aThesis (BS Applied Mathematics) -- University of the Philippines Mindanao, 2003
520	3		_aThe 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 {cij : ABTy = cb + c(ej)B, AnTy cn + c(ej)N}. 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 {cij : ABTy = CB + c(ej)B, ANTy cN + c(ej)N}. The sensitivity analysis done with IPM approach is indeed the most effective and efficient way for APs.
658			_aUndergraduate Thesis _cAMAT200, _2BSAM
905			_aFi
905			_aUP
942			_2lcc _cTHESIS
999			_c181 _d181