Linear Parametric Sensitivity Analysis of the Constraint Coefficient Matrix in Linear Programs

Sensitivity analysis is used to quantify the impact of changes in the initial data of linear programs on the optimal value. In particular, parametric sensitivity analysis involves a perturbation analysis in which the effects of small changes of some or all of the initial data on an optimal solution are investigated, and the optimal solution is studied on a so-called critical range of the initial data, in which certain properties such as the optimal basis in linear programming are not changed. Linear one-parameter perturbations of the objective function or of the so-called ”right-hand side” of linear programs and their effect on the optimal value is very well known and can be found in most college textbooks on Management Science or Operations Research. In contrast, no explicit formulas have been established that describe the behavior of the optimal value under linear one-parameter perturbations of the constraint coefficient matrix. In this paper, such explicit formulas are derived in terms of local expressions of the optimal value function and intervals on which these expressions are valid. We illustrate this result using two simple examples.