On some aspects of the matrix data perturbation in linear program
DOI:
https://doi.org/10.2298/YJOR0302153KKeywords:
linear parametric programming, parameter-dependent constraint matrixAbstract
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 tT∈⊆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 neighborhood 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. .References
Arana, R.M., "Programming with parametric elements of the matrix coefficients", R.A.I.R.O. Recherche Operationnelle, 11(2) (1977) 233-238.
Adler, I., and Monteiro, R., "A geometric view of parametric linear programming", Algorithmica, 8 (1992) 161-176.
Bank, B., Guddat, J., Klatte, D., Kummer, B., and Tammer, K., Nonlinear Parametric Optimisation, Akademie-Verlag, Berlin, 1982.
Barnett, S., "A simple class of parametric linear programming problems", Operations Research Quarterly, 16 (1968) 1160-1165.
Berkelaar, A.B., Roos, K., and Terlaky, A., "The optimal set and optimal partition approach to linear and quadratic programming", in: T. Gal, H.J. Greenberg (eds.), Advances in Sensitivity Analysis and Parametric Programming, Kluwer Academic Publishers, Boston/Dordrecht/London, 1997.
Courtillot, M., "On varying all the parameters in a linear programming problem and sequential solution of a linear programming problem", Operations Research, 10 (1962) 471-475.
Dantzig, G.B., Folkman, J., and Shapiro, N., "On the continuity of the minimum set of a continuous function", Journal of Mathematical Analysis and Applications, 17 (1967) 519-548.
Dinkelbach, W., Sensitivitatsanalysen und Parametrische Programmierung, Springer-Verlag, Berlin, 1969.
Dragan, I., "Sur la structure des domaines d'optimalite du parametre, pour les programmes lineaires uniparametriques rationnels", Anale Sciintifique, 13 (1967) 177-192.
Dück, W., "Abänderung der koefifizientenmatrix linearer gleichungssysteme", Wiss. Ztschr. Hochschule fur Okonomie, Sonderheft, Sonderheft, (1965) 85-96.
Fiacco, A.V., Introduction to Sensitivity and Stability Analysis in Non Linear Programming, Academic Press, New York, 1983.
Finkelstein, B.V., "Obobšcenie parametričeskoi zadači lineinogo programmirovanija", Ekonomika i matematiceskie metodi, 1(3) (1965) 442-450.
Finkelstein, B.V., and Gumenok, L.P., "Algoritm rešenija zadači parametričeskogo programmirovania v slučae zavisimosti ot parametra matrici uslovii", Ekonomika i matematiceskie metodi, 13(2) (1977) 342-347.
Freund, R.M., "Postoptimal analysis of a linear program under simultaneus changes in matrix coefficients", Mathematical Programming Study, 24 (1985) 1-13.
Gal, T., "Sledovani současno zmeny všech koeficientu a zakladnich i nezakladnich strukturnich promennych simplexove ulohy LP", Ekonomicko Matematicky Obzor, 4(2) (1968) 90-201.
Gal, T., Betriebliche entscheidungsprobleme, sensitivitatsanalyse und parametrishe, programmierung., De Gruyter, Berlin, 1973.
Gal, T., "Linear parametric programming-A brief survey", Mathematical Programming Study, 21 (1984) 43-68.
Gal, T., Postoptimal Analysis Parametric Programming and Related Topics, McGraw-Hill, 1979, 1995.
Gal, T., and Greenberg H.J. (eds.), Advances in Sensitivity Analysis and Parametric Programming, Kluwer's Academic publishers, 1997.
Greenberg, H.J., "Matrix sensitivity analysis from an interior solution of a linear program", CCM No. 104, Center for Computational Mathematics, Mathematics Department, University of Colorado at Denver, Denver, CO, 1997.
Guddat, J., Guerra Vasquez, F., Tammer, K., and Wendler, K., Multiobjective and Stochastic Optimisation Based on Parametric Optimisation, Mathematical Research band 26, Akademie Verlag, Berlin, 1985.
Jansen, B., Roos, B.C., and Terlaky, T., "An interior point approach to postoptimal and parametric analisys in linear programming", Tecnical report 92-21, Faculty of Technical Mathematics and informatics, TU Delft, NL-2628 CD Delft, The Netherlands 1992.
Jodin, D.B., and Golstein, E.G., Novie napravlenija v lineinom programmirovanii, Sovetskoe radio, Moskva 1965.
Ka{ka, J., "Prispevek parametriceskom programirovanu", Ekonomicko matematicky obzor, (1973) 31-48.
Kim, C., "Parametrizing an activity vector in linear programming", Operations Research, 19 (1971) 1632-1646.
Klatte, D., "Lineare optimierungsprobleme mit parametern in der koeffizientenmatrix der restriktionen", in: K. Lommatzsch (ed.), Anwendungen der linearen parametrishen Optimierung, Birkauser Verlag, Basel, Sttudgart, 1979.
Kon-Popovska, M., "Enoparametricno zvezno linearno programiranje teoreti~en in algoritem ski pristop", doktorsko delo, Ljubljanska Universa, Ljubljana, 1992.
Kon-Popovska, M., "Implicit critical regions determination for the solution of parametric linear programming problem with system matrix parameterisation", Proceedings of 17th International Conference ITI'95, Pula, 1995, 379-384.
Levitin, E.S., Perturbation Theory in Mathematical Programming and its Applications, John Willey & Sons, 1994.
Maurin, H., "Parametrization generale d'un programme lineaire", R.A.I.R.O. Recherche Operationelle, 8(32) (1964) 277-292.
Nozicka, F., Guddat, J., Hollatz, H., and Bank, B., Theory der linearen parametrischen Optimierung, Akademie-Verlag, Berlin 1974.
Pateva, D.D., "On singularities in linear one-parametric optimization problems", Optimization 22(2) (1991) 193-219.
Van de Panne, C., "Parameterizing an activity vector in linear programming", Operations Research, 21 (1973) 389-390.
Ravi, N., and Wendell, R.E., "The tolerance approach too sensitivity analysis of matrix coefficients in linear programming", Management Science, 35(9) (1989) 1106-1119.
Satty, T.L., "Coefficient perturbation of a constrained extremum", Operations Research, 7 (1959) 294-302.
Sherman, J., and Morrison, W., "Adjustmen of an inverse matrix corresponding to a change in one element of a given matrix", An. Math. and Statistics, 21 (1950) 124-127.
Schubert, I.S., and Zimmermann, U., Zeitschrrift f•r Operat. Research, 29 (1985) 187-202.
Valiaho, H., "A procedure for one-parametric linear programming", BIT, 19 (1979) 256-269.
Weickenmeier, E., "Ein algorithmus zur systematischen und vollst⌂ndigen l–sung eines parametrischen linmearen Programms mit einem Parameter in Allen Koeffizienten", Zeitschrift f•r Operations Research, 22 (1978) 131-149.
Wendel, R.E., "Using bounds on the data in linear programming: The tolerance approach to sensitivity analysis", Mathematical Programming, 29 (1984) 304-322.
Willner, L.B., "On parametric linear programming", SIAM J. Appl. Math., 15(5) (1967) 1253-1257.
Wilkinson, J.H., The Algebraic Eigenvalue Problem, Oxford Science Pub., Oxford N.Y., 1965.
Downloads
Published
Issue
Section
License
Copyright (c) 2003 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
