|
|||||
|
|
| 一种新的线性规划多项式时间算法 | |
| 引用本文： | 张青富 肖高奚. 一种新的线性规划多项式时间算法[J]. 应用数学学报, 1996, 19(1): 33-38 |
| 作者姓名： | 张青富 肖高奚 |
| 作者单位： | 西安电子科技大学数学系 |
| 摘 要： | 本文给出了一种新的线性规划多项式时间算法。在此算法中，每步可沿一族方向中的一个进行线性搜索，同时，还使用了开关策略，从而大大减少了求逆矩阵的次数，最后，证明了算法经Ｏ（ｎＬ）次迭代结束。 |
| 关 键 词： | 线性规划 Karmarkar算法 多项式时间算法 |
A NEW POLYNOMIAL-TIME ALGORITHM FOR LP |
|
| ZHANG QINGFU, XIAO GAOXI, CHEN KAIZHOU. A NEW POLYNOMIAL-TIME ALGORITHM FOR LP[J]. Acta Mathematicae Applicatae Sinica, 1996, 19(1): 33-38 | |
| Authors: | ZHANG QINGFU XIAO GAOXI CHEN KAIZHOU |
| Abstract: | in this paper, we present a new polynomial-time algorithm for linear programming, which has a family of feasible directions at each iteration step. Meanwhile, the switchstrategy is used. By all these means, it is possible to reduce the amount of inverse matrix calculations greatly. Finally, it is proved that the algorithm can be stopped in O(nL)iterations. |
| Keywords: | Linear programming Karmarkar's algorithm switch strategy |
| 本文献已被 CNKI 维普 等数据库收录！ | |