| 线性规划问题的规范型算法的一种变式 |
| |
| 引用本文： | 高培旺.线性规划问题的规范型算法的一种变式[J].嘉应学院学报,2013(8):5-9. |
| |
| 作者姓名： | 高培旺 |
| |
| 作者单位： | 闽江学院数学系,福州350108 |
| |
| 基金项目： | 基金项目：闽江学院人才引进基金资助课题（MJU2012001） |
| |
| 摘 要： | 线性规划的规范性算法是从一个不可行初始基出发,通过一种简单而巧妙的初等变换,用原始单纯形算法求得可行基的方法.然而,规范型算法在初等变换过程中,需要更换系数矩阵和右手边向量,增加了计算工作量.在此提出了一种基于人工变量的单纯形变式,当确定不可行初始基之后,在每个约束方程中添加一个相同的人工变量,若右手边项为负值,其系数设置为-1,否则设置为0.这样,以人工变量作为入基变量,以最负右手边项所在行为枢轴行,进行旋转变换,就可将右手边全部化成非负项,而且与规范性算法产生的结果完全相同,但避免了初等变换产生新的系数矩阵的计算.最后,通过大规模数值试验对提出的变式与规范型算法进行了比较.结果表明,所提出的变式所用的总迭代次数要少,且在每个问题上都耗费更少的计算时间.
|
| 关 键 词： | 线性规划 可行基 单纯形算法 规范型 人工变量 |
A Variant of the New Algorithm for the Normalized Form of Linear Programming |
| |
| GAO Pei-wang.A Variant of the New Algorithm for the Normalized Form of Linear Programming[J].Journal of Jiaying University,2013(8):5-9. |
| |
| Authors: | GAO Pei-wang |
| |
| Institution: | GAO Pei - wang (Department of Mathematics, Minjiang University, Fuzhou 350108, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | linear programming feasible basis simplex algorithm normalized form artificial variable |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
