Stochastic sensitivity analysis of linear programs by simulation techniques

摘要

Sensitivity analysis is the investigation of the stability of the optimal solution to a linear programming problem. [equation] (1)

rn

Suppose that A is an mxn matrix with rank equal to m and that an mxm submatrix, B, is the optimal basis. Let further SB be the index set of the column vectors forming B. It is well known that the necessary and sufficient conditions for B to be optimal are the conditions of primal and dual feasibility, i.e. [equation] (2a)

rn

where CB is the row vector of objective function co-efficients for JεSB and aj is the j-th column of A. As long as these conditions are maintained the basis is stable---that is, insensitive to variations in the coefficients. The ranges within which these variations may occur can be computed---ceteris paribus--- for any particular component of C, b and aj by well known formulae.1,2