线性规划的宽邻域预估校正算法

J4 ›› 2009, Vol. 44 ›› Issue (7): 66-70.

线性规划的宽邻域预估校正算法

张莉^1,2,张涛²

1. 四川省高等学校数值仿真重点实验室, 四川内江 641112;

2. 内江师范学院数学与信息科学学院, 四川内江 641112

收稿日期:2008-06-03 出版日期:2009-07-16 发布日期:2009-11-01
作者简介:张莉(1981-), 女, 讲师,硕士研究生,主要从事最优化理论及其算法研究.Email:zhangli520520520@tom.com
基金资助:
国家自然科学基金资助项目(10872085);四川省教育厅青年基金资助项目

(08zb046)

A wideneighborhood predictorcorrecting algorithm for
linear programming

ZHANG Li^1,2, ZHANG Tao²

1. Department of Key Laboratory of Numerical Simulation, Colleges and Universit ies of Sichuan, Neijiang 641112, Sichuan， China; 2. Department of Mathematics, Neijiang Teachers College, Neijiang 641112 , Sichuan， China

Received:2008-06-03 Online:2009-07-16 Published:2009-11-01

摘要/Abstract

摘要：

提出了一种新的内点算法——宽邻域预估校正算法。该算法基于经典预估校正算法思想,把窄邻域拓展到宽邻域里,使算法更快地迭代。给出了算法的具体步骤,讨论了其计算复杂性,分析结果表明,所给算法是一多项式时间算法。通过数值实验验证算法的有效性。

关键词: 线性规划;宽邻域;预估校正算法;复杂度

Abstract:

A new interior point wideneighborhood predictorcorrecting algorithm is presented for a linear programming problem. On the basis of the idea of a predictorcorrecting algorithm, the iteration of our algorithm is faster in a wideneighborhood than in a narrow one. The concrete steps of the algorithm are introduced, its computational complexity is discussed, and the results indicate that the algorithm is a polynomialtime one. The validity of the algorithm is confirmed though a numerical experiment.

Key words: linear programming; wideneighborhood; predictorco rrector algorithms; complexity

中图分类号:

O159

. 线性规划的宽邻域预估校正算法[J]. J4, 2009, 44(7): 66-70.

参考文献

相关文章 8

[1]	汤积华陈保会史开泉. P-集合与(,F)-数据生成-辨识[J]. J4, 2009, 44(11): 83-88.
[2]	于秀清. P-粗积分与函数双向S-粗集的粗糙度[J]. J4, 2009, 44(11): 89-92.
[3]	黄江燕于秀清方文青. 粗积分的动态特征[J]. J4, 2009, 44(11): 93-96.
[4]	高山林李健阮小葭. 基于理想点的模糊数排序方法[J]. J4, 2009, 44(8): 86-89.
[5]	方文青于秀清史开泉. F-粗积分与它的面积覆盖-边界厚度特征[J]. J4, 2008, 43(12): 88-92.
[6]	苏芬肖陈保会. β-粗积分[J]. J4, 2008, 43(12): 61-65.
[7]	苏芬肖张玲. 函数单向S_PF-粗集与它的概率特征[J]. J4, 2008, 43(12): 56-60.
[8]	孙守斌,孟广武 . LF拓扑空间的Dα-导集[J]. J4, 2008, 43(5): 63-65 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed