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

A Variant of the New Algorithm for the Normalized Form of Linear Programming

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

A new algorithm for the normalized form of linear programming starts from an initial infeasible basis and then uses the primal simplex algorithm to achieve a feasible basis by an ingenious elementary transformation. How- ever, the new algorithm for the normalized form would increase the amount of computing the new coefficient matrix and right - hand side vector with the elementary transformation. For this reason, the paper presents a simplex vari- ant based on the artificial variable, in which each equality constraint added the same one artificial variable with the coefficients - 1 corresponding to the negative right - hand side, or the coefficients 0 else. Thus, the pivotal ex- change between the artificial variabld and basic variable associated with the most negative right -hand side would lead to the non- negative right -hand side, the same as the new algorithm for the normalized form. Noticeably, our simplex variant keeps the coefficient matrix unchanged. Finally, a comparison between our algorithm and the new algorithm for the normalized form is implemented on large - scale numerical examples. The computational re- suits show that our algorithm always uses fewer iterations in total, and spends less executive time for every problem than the new algorithm for the normalized norm.