Type II sensitivity analysis of cost coefficients in the degenerate transportation problem

This paper focuses on sensitivity analysis of the degenerate transportation problem (DTP) when perturbation occurs on one cost coefficient. The conventional Type I sensitivity analysis of the transportation problem (TP) determines the perturbation ranges for the invariant optimal basis. Due to different degenerate optimal basic solutions yielding different Type I ranges, the Type I range is misleading for the DTP. Type II sensitivity analysis, which determines the perturbation ranges for the invariant shipping pattern, is more practical for the DTP. However, it is too tedious to obtain Type II ranges by enumerating all optimal basic solutions and all primal optimal basic solutions while getting the union of each corresponding Type I ranges. Here, we propose two labeling algorithms to determine the Type II ranges of the cost coefficient. Besides, three lemmas are provided for obtaining the upper bound or lower bound of the Type II ranges of the cost coefficient directly under specific conditions of the DTP. A numerical example is given to demonstrate the procedure of the proposed labeling algorithms and computational results have been provided.