On Some Aspects of the Matrix Data Perturbation in Linear Program

Abstract: Linear program under changes in the system matrix coefficients has proved to be more complex than changes of the coefficients in objective functions and right hand sides. The most of the previous studies deals with problems where only one coefficient, a row (column), or few rows (columns) are linear functions of a parameter. This work considers a more general case, where all the coefficients are polynomial (in the particular case linear) functions of the parameter t∈T ⊆ R. For such problems, assuming that some non-singularity conditions hold and an optimal base matrix is known for some particular value t of the parameter, corresponding explicit optimal basic solution in the neighbourhood of t is determined by solving an augmented LP problem with real system matrix coefficients. Parametric LP can be utilized for example to model the production problem where, technology, resources, costs and similar categories vary with time