最钝角亏基松弛算法

• 作者: 孟祥瑞 潘平奇 邱新法 顾文亚
• 来源期刊: 高等学校计算数学学报
• 学科: 数学
• 年，卷（期）: 2018,（4）
• 页码范围: 289-296
• 页数: 8页
• 分类号: O227|F253.4
• 语种: 中文

摘要

1 引言 线性规划(LP)是产生最早,影响最深远的一个运筹学分支.历经70多年的发展,已广泛应用于经济,科技,管理和工程等诸多领域,产生了巨大的经济效益和社会效益. 1947年,美国数学家G.B.Dantzig提出了线性规划问题的一般数学模型和求解线性规划问题的经典算法——单纯形法[1],标志着这一学科的创立.1972年V.Klee and G.J.Minty[2]指出单纯形算法在计算复杂度上并不是多项式时间的算法,并通过实例说明在最坏的情形下单纯形算法是指数时间的.1979年,哈奇扬提出了椭球算法[3],证明了LP问题确实存在多项式时间算法,但实际效果不甚理想.1984年,Karmarkar提出了新的多项式时间算法-Karmarka内点算法[4],该算法不仅具有比椭球算法更低阶的多项式时间复杂性,且有令人鼓舞的实际表现.随后掀起了内点法热,产生一批很好的算法,许多学者认为求解大规模问题优于单纯形算法.然而由于不能热启动,不能用于整数LP问题的求解,内点算法还不能撼动单纯形算法在实际中的统治地位.