对线性规划单纯形法的注记

为了更有效地应用单纯形算法求解线性规划问题,本文提出了以下几点注记。(1)人工变量列不必参与数值计算,也不占存储空间,从而可大量节省计算量和存储量;(2)使用基变量指标集来判断人工变量是否离基,可避免舍人误差的影响;(3)虚设人工变量的最终非零值对于修改存在矛盾的数学模型将起着关键性作用;(4)可将大M法与两阶段法统一处理,且M可不取具体的数值,也不参与数值计算;(5)实际计算中宜将Dantzig算法与Bland算法结合起来使用,既可对一般问题达到快速收敛的目的,又可避免退化问题可能产生的循环现象,而且在软件设计与实现上要比字典序方法等简单容易;(6)对于大型稀疏矩阵的计算机数据录入,建议采用二元数组的数据结构逐行录入,则可节省三分之一的录入工作量。

Notes on the Simplex Algorithm for LP

Several useful notes are presented in this paper to solve the LP proble.ms by simpled algorithm more efficiently, (l) Artificial variable columns do not take part in the numerical compution. (2) Judging if the artificial variables are pivoted out or not from basis with index set of basic varables can aviod the effect of rounding error. (3) The non-zero value of the solution of artificial variable possesses an impotant function in the modification of mathematical model.(4) The Big-M method and Two-phass method can be used simultaneously in a unified way.(5) Results will be better if Dantzig algorithm is combined with Bland algorithm in practical computing. It will accelerate convergence and avoid cycling of degenerate problem. (6) The adoption of binary array in conveying the large sparse matrix data to computer can reduce one third of typing.