100% Rule

From Glossary

Jump to: navigation, search

This pertains to sensitivity analysis in linear programming. In its original form, it uses the convexity of the set of admissible changes in the rim data to test whether a particular change is admissible: any combination of changes can occur as long as the total percentage deviation from the coordinate extremes does not exceed 100%. (Note: this applies to right-hand sides (b) and costs (c) separately.)

More generally, suppose the optimal value remains constant if the cost coefficient vector LaTeX: c in a linear program is replaced with any of LaTeX: c + d^1, c+d^2, \ldots , \mbox{ or } c + d^k (we could have LaTeX:  k = n and let LaTeX: d^j be the j-th coordinate extreme for LaTeX: c_j, but that is not necessary). Then, the optimal objective value is the same for LaTeX: \textstyle c + \sum_{i=1}^k \mu_i d^i, provided LaTeX: \mu_i \ge 0 and LaTeX: \textstyle \sum_{i=1}^k \mu_i \le 1

The same applies for convex combination of changes in the right-hand side LaTeX: b (maybe with the origin, which is no change). If the objective value remains optimal at if LaTeX: b is replaced with any of LaTeX: b + f^1, b + b^2, \ldots, b + f^q, then it is also optimal for the right-hand side LaTeX: \textstyle b + \sum_{i+1}^q \beta_i f^i so long that LaTeX: \beta_i \ge 0 and LaTeX: \textstyle \sum_{i=1}^q \beta_i \le 1

Personal tools