运用改进的线性规划算法求解分片线性方程组  

Finding all solutions of piecewise-linear equations using linear programming

作　　者：李颖[1] 黄晓霖[1] 王书宁[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《清华大学学报（自然科学版）》2009年第10期1593-1596,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60674025;60534060);国家"九七三"重点基础研究项目(2002CB312200)

摘　　要：为了提高求解分片线性方程组的线性规划算法的计算效率,提出基于线性规划算法的改进算法。首先找出若干线性区域组成的超立方体,使得方程组函数在此超立方体上表现为凸函数或凹函数,然后在超立方体上求解一次特定的线性规划问题并判断此超立方体是否含有方程组的解。在算例中该算法需要求解的线性规划问题数目仅为线性规划算法的1/4。该算法无需在全部线性区域上求解线性规划,因此相对线性规划算法提高了计算效率,提高程度取决于方程组函数的性质。A linear programming （LP） algorithm was developed to more efficiently find all solutions of piecewise-linear equations than the traditional LP algorithm. This algorithm first finds the hypercube consisting of the various linear regions with the equations being other convex or concave in this hypercube. Then, specific LP problems are solved in the hypercube to determine whether the solution exists. For the example given in this paper, the algorithm uses only 25~ as many linear programs as the conventional LP algorithm. Thus this algorithm is more efficient than the conventional LP algorithm since it reduces the number of linear programs that need to be solved. The improved performance compared to the conventional LP algorithm depends on the equation properties.

关 键 词：电路求解 分片线性方程组 线性规划 

分 类 号：TM133[电气工程—电工理论与新技术]