Solution Building for Arbitrary System of Linear Inequalities in an Explicit Form

• 作者: Alexander M. Lukatskii Demetrius V. Shapot
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: Linear INEQUALITIES CONVOLUTION Variable Elimination Orthogonal Projection Method Fourier Algorithm Chernikov Rules DEPENDENT INEQUALITIES REDUNDANT INEQUALITIES Almost DEPENDENT INEQUALITIES Matrix CLEANUP COARSENING
• 年，卷（期）: 2012,（1）
• 页码范围: 1-11
• 页数: 11页
• 分类号: O1

摘要

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.