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
Adler, I., Monteiro, R. (1992) A geometric view of parametric linear programming. Algorithmica, 8, 2, 161-176
Arana, R.M. (1977) Programming with parametric elements of the matrix coefficients. RAIRO Recherche Oper., 11, 2, 233-238
Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K. (1982) Nonlinear parametric optimization. Berlin: Akademie Verlag
Barnett, S. (1968) A simple class of parametric linear programming problems. Operations Research Quarterly, 16, 1160-1165
Berkelaar, A.B., Roos, K., Terlaky, A. (1997) The optimal set and optimal partition approach to linear and quadratic programming. u: T.Gal, H.J.Greenberg [ur.] Advances in Sensitivity Analysis and Parametric Programming, Dordrecht, itd: Kluwer Academic
Courtillot, M. (1962) On varying all the parameters in a linear-programming problem and sequential solution of a linear-programming problem. Operations Research, 10, 471-475
Dantzig, G.B., Folkman, J., Shapiro, N. (1967) On the continuity of the minimum sets of a continuous function. Journal of Mathematical Analysis and Applications, 17, 519-548
Dinkelbach, W. (1969) Sensitivitatsanalysen und parametrische programmierung. Berlin, itd: Springer Verlag
Dragan, I. (1967) Sur la structure des domaines d'optimalit'e du param'etre, pour les programmes lin'eaires uniparam'etriques rationnels. An. Stiint. Univ. Al. I. Cuza Iasi Sect. I a Mat., 13, 177-192
Duck, W. (1965) Abänderung der koefifizientenmatrix linearer gleichungssysteme. Wiss. Ztschr. Hochschule fur Okonomie, Sonderheft, 85-96
Fiacco, A.V. (1983) Introduction to sensitivity and stability analysis in non linear programming. New York-San Diego, itd: Academic Press
Finkelstein, B.V. (1965) Obobšcenie parametričeskoi zadači lineinogo programmirovanija. Ekonomika i matematiceskie metodi, 1, 3, 442-450
Finkelstein, B.V., Gumenok, L.P. (1977) Algoritm rešenija zadači parametričeskogo programmirovania v slučae zavisimosti ot parametra matrici uslovii. Ekonomika i matematiceskie metodi, 13, 2, 342-347
Freund, R.M. (1985) Postoptimal analysis of a linear program under simultaneous changes in matrix coefficients. Mathematical Programming Study, 24, 1-13
Gal, T. (1968) Sledovani současno zmeny všech koeficientu a zakladnich i nezakladnich strukturnich promennych simplexove ulohy LP. Ekonomicko Matematicky Obzor, 4, 2, 90-201
Gal, T. (1973) Betriebliche entscheidungsprobleme, sensitivitatsanalyse und parametrishe, programmierung. Berlin, itd: de Gruyter
Gal, T. (1984) Linear parametric programming: A brief survey. Mathematical Programming Study, 21, 43
Gal, T. (1979) Postoptimal analyses: Parametric programming and related topics. New York, itd: McGraw-Hill
Gal, T., Greenberg, H.J., ur. (1997) Advances in sensitivity analysis and parametric programming. Hague-London-Boston: Kluwer Law International
Greenberg, H.J. (1997) Matrix sensitivity analysis from an interior solution of a linear program. Denver, CO: Center for Computational Mathematics, Mathematics Department, University of Colorado at Denver, CCM br. 104
Guddat, J., Guerra, F., Tammer, K., Wendler, K. (1985) Multiobjective and stochastic optimization based on parametric optimization. Berlin: Akademie Verlag
Jansen, B., Roos, B.C., Terlaky, T. (1992) An interior point approach to post optimal and parametric analysis in linear programming. Delft, The Netherlands: Faculty of Technical Mathematics an informatics, Technical report 92-21
Jodin, D.B., Golstein, E.G. (1965) Novie napravlenija v lineinom programmirovanii. Moskva: Sovetskoe radio
Kaška, J. (1973) Prispevek parametriceskom programirovanu. Ekonomicko matematicky obzor, 31-48
Kim, C. (1971) Parametrizing an activity vector in linear programming. Operations Research, 19, 1632-1646
Klatte, D. (1979) Lineare optimierungsprobleme mit Parametern in der koeffizientenmatrix der Restriktionen. u: K.Lommatzsch [ur.] Anwendungen der linearen parametrishen Optimierung, Basel, itd: Birkhaüser
Kon-Popovska, M. (1992) Enoparametricno zvezno linearno programiranje teoretičen in algoritemski pristop. Ljubljana: Ljubljanska Universa, doktorsko delo
Kon-Popovska, M. (1995) Implicit critical regions determination for the solution of parametric linear programming problem with system matrix parameterisation. u: Proceedings of 17th International Conference ITI'95, Pula, 379-384
Levitin, E.S. (1994) Perturbation theory in mathematical programming and its applications. New York, itd: Wiley
Maurin, H. (1964) Parametrization generale d'un programme lineaire. R. A. I. R. O. Recherche Operationnelle, 8, 32, 277-292
Nozicka, F., Guddat, J., Hollatz, H., Bank, B. (1974) Theory der linearen parametrischen optimierung. Berlin: Akademie Verlag
Pateva, D.D. (1991) On the singularities in linear one-parametric optimization problems. Optimization, Berlin, 22, 2, 193-219
Ravi, N., Wendell, R.E. (1989) The tolerance approach to sensitivity analysis of matrix coefficients in linear programming. Management Science, 35, 9, 1106-1119
Saaty, T.L. (1959) Coefficient perturbation of a constrained extremum. Operations Research, 7, 294-302
Schubert, I.S., Zimmermann, U. (1985) Zeitschrift fur Operat. Research, 29, 187-202
Sherman, J., Morrison, W. (1950) Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statist, 21, 124-127
Valiaho, H. (1979) A procedure for one-parametric linear programming. Bit Numerical Mathematics, 19, 2, 256-269
van de Panne, C. (1973) Parameterizing an activity vector in linear programming. Operations Research, 21, 389-390
Weickenmeier, E. (1978) Ein algorithmus zur systematischen und vollständigen Lösung eines parametrischen linearen Programms mit einem Parameter in allen koeffizienten. Zeitschrift fur Operations Research, 22, 131-149
Wendel, R.E. (1984) Using bounds on the data in linear programming: The tolerance approach to sensitivity analysis. Mathematical Programming Series A, 29, 304-322
Wilkinson, J.H. (1965) The algebraic eigenvalue problem. Oxford: Oxford Science Publications
Willner, L.B. (1967) On parametric linear programming. SIAM Journal on Applied Mathematics, 15, 5, 1253- 1257
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.