目标超平面上的一种原始-对偶单纯形算法  

A Primal-dual Simplex Algorithm on the Target Hyperplane

作　　者：高培旺[1] 

机构地区：[1]闽江学院数学系,福建福州350121

出　　处：《徐州工程学院学报（自然科学版）》2017年第4期30-34,45,共6页Journal of Xuzhou Institute of Technology(Natural Sciences Edition)

基　　金：国家自然科学基金项目(11471239);闽江学院人才引进基金资助课题(MJU2012001);广西自然科学基金项目(0728260)

摘　　要：对于目标最优值已知的情形,提出一次迭代到目标超平面上获得相应的对偶可行基,然后应用Samaras等的原始-对偶算法在目标超平面上进行对偶迭代.在确定枢轴列时,采用无比值检验方法,节省了计算工作量.为防止Samaras等的原始-对偶算法在原始可行点退化情形下可能发生的循环现象,加快迭代进程,引入MBU对偶单纯形算法进行迭代,直到对偶间隙严格缩少.中大规模数值试验结果表明,与经典单纯形算法相比,该算法在大部分算例上使用更少的迭代次数和执行时间,具有更高的计算效率.In the case that the optimal target value is known,the paper presents to obtain the corresponding dual feasible basis from one iteration to the target hyperplane,and then perform the dual iteration on the target hyperplane by using the primal-dual algorithm of Samaras et al.In determining the pivot column,the non-ratio test method is used to save the computational workload.In order to prevent the circling phenomenon that for Samaras et al＇s primal-dual algorithm may occur in the case of original feasible point degeneration,and accelerate the iterative process,the MBU dual simplex algorithm is introduced to iterate until the dual gap is strictly narrowed.The results of large-scale numerical experiments show that compared with the classical simplex algorithm,the proposed algorithm uses less iterations and execution time on most of the examples and has higher computational efficiency.

关 键 词：线性规划 可行域 单纯形算法 原始-对偶外点算法 计算效率 

分 类 号：O221.1[理学—运筹学与控制论]