线性规划问题的规范型算法的一种变式

摘要

线性规划的规范性算法是从一个不可行初始基出发,通过一种简单而巧妙的初等变换,用原始单纯形算法求得可行基的方法.然而,规范型算法在初等变换过程中,需要更换系数矩阵和右手边向量,增加了计算工作量.在此提出了一种基于人工变量的单纯形变式,当确定不可行初始基之后,在每个约束方程中添加一个相同的人工变量,若右手边项为负值,其系数设置为-1,否则设置为0.这样,以人工变量作为入基变量,以最负右手边项所在行为枢轴行,进行旋转变换,就可将右手边全部化成非负项,而且与规范性算法产生的结果完全相同,但避免了初等变换产生新的系数矩阵的计算.最后,通过大规模数值试验对提出的变式与规范型算法进行了比较.结果表明,所提出的变式所用的总迭代次数要少,且在每个问题上都耗费更少的计算时间.