论线性规划的原始—对偶单纯形算法

摘要：

从一个既不是原始可行也不是对偶可行的初始基出发,提出了求解线性规划问题的原始—对偶单纯形算法.首先,将等式约束右手边向量取负值的项置为零,用原始单纯形算法求解相应的线性规划问题,如果存在最优解,则是原问题的一个正则解.在原始单纯形迭代过程中,一旦原问题右手边向量取负值的项转化为非负项,则恢复其原来的约束条件参与迭代计算,可使获得的正则解距原问题的最优解(如果存在)更近.接着,从所获得的正则解出发,用对偶单纯形算法求解原问题,直到获得原问题的最优解或无可行解的结论.最后,为了验证该算法的计算性能,通过MATLAB编程在计算机上进行大规模数值试验,结果表明,与经典单纯形算法相比,该算法在大部分问题上使用更少的迭代次数和执行时间,具有更高的计算效率.

关键词：线性规划、初始基、单纯形算法、对偶单纯形算法、计算效率

所属期刊栏目：25

分类号：O224(运筹学)

资助基金：闽江学院人才引进基金资助课题MJU201201

在线出版日期：2013-07-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：24-28