| 运用改进的线性规划算法求解分片线性方程组 |
| |
| 引用本文： | 李颖,黄晓霖,王书宁.运用改进的线性规划算法求解分片线性方程组[J].清华大学学报(自然科学版),2009(10). |
| |
| 作者姓名： | 李颖 黄晓霖 王书宁 |
| |
| 作者单位： | 清华大学自动化系; |
| |
| 基金项目： | 国家自然科学基金资助项目(60674025,60534060);;国家“九七三”重点基础研究项目(2002CB312200) |
| |
| 摘 要： | 为了提高求解分片线性方程组的线性规划算法的计算效率,提出基于线性规划算法的改进算法。首先找出若干线性区域组成的超立方体,使得方程组函数在此超立方体上表现为凸函数或凹函数,然后在超立方体上求解一次特定的线性规划问题并判断此超立方体是否含有方程组的解。在算例中该算法需要求解的线性规划问题数目仅为线性规划算法的1/4。该算法无需在全部线性区域上求解线性规划,因此相对线性规划算法提高了计算效率,提高程度取决于方程组函数的性质。
|
| 关 键 词： | 电路求解 分片线性方程组 线性规划 |
Finding all solutions of piecewise-linear equations using linear programming |
| |
| LI Ying,HUANG Xiaolin,WANG Shuning.Finding all solutions of piecewise-linear equations using linear programming[J].Journal of Tsinghua University(Science and Technology),2009(10). |
| |
| Authors: | LI Ying HUANG Xiaolin WANG Shuning |
| |
| Institution: | Department of Automation;Tsinghua University;Beijing 100084;China |
| |
| Abstract: | 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 algor... |
| |
| Keywords: | circuit solving piecewise-linear equations linear programming |
| 本文献已被 CNKI 等数据库收录！ |
