Research ArticleOpen AccessGoogle Scholar indexed
Solution Building for Arbitrary System of Linear Inequalities in an Explicit Form
Energy Research Institute, Russian Academy of Sciences, Moscow, Russia
Energy Research Institute, Russian Academy of Sciences, Moscow, Russia
- 1 Energy Research Institute, Russian Academy of Sciences, Moscow, Russia
- 2 Energy Research Institute, Russian Academy of Sciences, Moscow, Russia
American Journal of Computational Mathematics·Volume 02 (2012)·Pages 1–11·Published 21 March 2012·DOI10.4236/ajcm.2012.21001
Copy link · social · email
Abstract
The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequalities is defined and an algorithm for further reducing the system by deletion of these is considered. The concluding algorithm makes it possible to hold actual-time convolution of a general inequality system containing up to 50 variables with the rigorous method of dependent inequalities deletion and up to 100 variables with the approximate method of one. The main application of such an approach consists in solving linear inequality system in an explicit form. These results are illustrated with a series of computer experiments.
KeywordsLinear InequalitiesConvolutionVariable EliminationOrthogonal Projection MethodFourier AlgorithmChernikov RulesDependent InequalitiesRedundant InequalitiesAlmost Dependent InequalitiesMatrix CleanupCoarsening
- J. B. Fourier, “Solution d’une Question Particulière du Calcul des Inégalités,” Nouvean Bulletin des Sciences par la Société Philomatique de Paris, 1826, p. 99.
- D. V. Shapot, “On the Construction of Orthogonal Projections of Point Sets Defined by a System of Inequalities,” Journal Computational Mathematics and Mathematical Physics, Vol. 11, 1971, pp. 1113-1126.
- S. N. Chernikov, “Linear Inequalities,” Nauka, Мoscow, 1968.
- V. A. Bushenkov and A. V. Lotov, “An Algorithm for Analysis of Inequality Dependences in a Linear System,” Journal Computational Mathematics and Mathematical Physics, Vol. 20, 1980, pp. 562-572.
- A. V. Lotov, “On the Estimate of Stability and the Condition Number of the Solution Set of a System of Linear Inequalities,” Journal Computational Mathematics and Mathematical Physics, Vol. 24, 1984, pp. 1763-1774.
- I. I. Eremin and A. A. Makhnev, “International Workshop on Algebra and Linear optimization dedicated to the 90th Anniversary of the Birth of S. N. Chernikov,” Ural State University Bulletin, Vol. 30, 2004, pp. 183-184.
- D. V. Shapot and A. M. Lukatskii, “A Constructive algorithm for Foldind Large-Scale Systems of Linear Inequalities,” Computational Mathematics and Mathematical Physics, Vol. 48, No. 7, 2008, pp. 1100-1112. doi:10.1134/S0965542508070038
- T. S. Motzkin, H. Raiffa, G. L. Thompson and R. M. Trall, “The Double Description Method,” Contributions to the Theory of Games, Vol. 2, 1953, pp. 51-73.
- F. P. Preparata and M. I. Shamos, “Computational Geometry. An Introduction,” Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1985.
- V. N. Shevchenko and D. V. Gruzdev, “Modifications of Fou-rier-Motskin Algorithm for Triangulation Construction,” Discrete Analysis and Investigation of Operations, Series 2, Vol. 10, 2003, pp. 53-64.
- R. V. Efremov, G. K. Kamenev and A. V. Lotov, “Constructing an Economical Description of a Polytop Using the Duality Theory of Convex Sets,” Doklady Mathematics, Vol. 70, 2004, pp. 934-936.
- A. I. Golikov and Y. G. Evtushenko, “A New Method for Solving Systems of Linear Equalities and Inequalities,” Doklady Mathematics, Vol. 64, 2001, pp. 370-373.
- P. O. Gutman and I. Ioslovich, “On the Generalized Wolf Problem: Preliminary Analysis of Nonnegativity of Large Linear Programs Subject to Group Constrains,” Automation Telemech, No. 8, 2007, pp. 116-125.