Determining Type II sensitivity ranges of the fractional assignment problem

摘要

This paper proposes iterative labeling algorithms to determine the Type II sensitivity ranges of the fractional assignment problem. Unlike the traditional sensitivity range which keeps the current optimal basis remaining optimal, the Type II sensitivity range is the range that keeps the current optimal assignment remaining optimal. Focusing only on the non-degenerate basic variables makes the Type II sensitivity range more practical. Three cases of perturbation, each with two kinds, are discussed. An example is presented to demonstrate the proposed algorithms.