tailieunhanh - On some aspects of the matrix data perturbation in linear program

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. | Yugoslav Journal of Operations Research 13 (2003), Number 2, 153-164 ON SOME ASPECTS OF THE MATRIX DATA PERTURBATION IN LINEAR PROGRAM* Margita KON-POPOVSKA Department of Informatics, Faculty of Sciences and Mathematics University Ss Cyril and Methodious, Skopje margita@ Communicated by Byron Papathanassiou 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. Keywords: Linear parametric programming, parameter-dependent constraint matrix. 1. INTRODUCTION For the parametric linear programming problems with arbitrary matrix parameterization results of rather theoretical character exist (Finkelstein 1965 [12], Dantzig 1967 [7], Klatte 1979 [26], Schubert and Zimmermann 1985 [37], Pateva 1991 [32]). Parametric linear programs, where the matrix coefficients are polynomial functions of a scalar parameter were investigated in Jodin and Goldstein 1965 [23], Dragan 1966 [9], Weicknmeir 1978 [39], Kon-Popovska 1992 [27], while linear parameterization was investigated in Satty 1959 [35], Valiaho 1979 [38], Freund 1985 [14]. More work, both theoretical and practical, has been done