[1] Pan Pingqi, Li Wei,. A non-monotone Phase-1 method in linear programming [J]. Journal of Southeast University (English Edition), 2003, 19 (3): 293-296. [doi:10.3969/j.issn.1003-7985.2003.03.018]
Copy
A non-monotone Phase-1 method in linear programming(
)
线性规划非单调一阶段算法
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 19
- Issue:
- 2003 3
- Page:
- 293-296
- Research Field:
- Mathematics, Physics, Mechanics
- Publishing date:
- 2003-09-30
Info
- Title:
- A non-monotone Phase-1 method in linear programming
- 线性规划非单调一阶段算法
- Author(s):
- Pan Pingqi; Li Wei
- Department of Mathematics, Southeast University, Nanjing 210096, China
- Keywords:
- linear programming; Phase-1; ratio-test-free; pivoting rule
- PACS:
- O221.1
- DOI:
- 10.3969/j.issn.1003-7985.2003.03.018
- Abstract:
- To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.
- 为了获取计算的高效率, 有必要修正单纯形算法的原则.本文提出了一个新的单纯形一阶段算法.与传统单纯形算法不同的是, 新算法不仅不要求目标函数值单调变化, 且在一阶段的迭代过程中也不必保持变量的可行性, 而是采用纯组合的方法去达到可行.这样摆脱了迭代时的比值检验, 减少了每次迭代的计算工组量.理论分析及数值计算结果表明新算法的前景令人鼓舞.
References:
[1] Wolfe P. The composite simplex algorithm [J]. SIAM Review, 1965, 7: 42-54.
[2] Maros Istvan. A general Phase-I method in linear programming [J]. European Journal of Operations Research, 1986, 34: 64-77.
[3] Belling-Seib K. An improved general Phase-I method in linear programming [J]. European Journal of Operations Research, 1988, 36: 101-106.
[4] Pan P Q. A projective simplex method for linear programming [J]. Linear Algebra and its Applications, 1999, 29(2):99-125.
[5] Pan P Q. A new perturbation simplex algorithm for linear programming [J]. Journal of Computational Mathematics, 1999, 17(3): 233-242.
[6] Pan P Q. A projective simplex algorithm using LU decomposition [J]. Computers and Mathematics with Applications, 2000, 39(1): 187-208.
[7] Pan P Q. Practical finite pivoting rules for the simplex method[J]. OR Spektrum, 1990, 12: 219-225.
Memo
- Memo:
- Biography: Pan Pingqi(1942—), male, professor; panpq@seu.edu.cn.