采用大M单纯形法时M值上下界的确定

Determination of Upper and Lower Boundaries of M in Big-M-Simplex-Method for Solving Linear Programming Problems

采用大M单纯形法求解线性规划(或线性目标规划)模型时,过去文献仅指出M应为'足够大的正数'。笔者通过理论分析,认为M值不仅与模型中的系数c_j,a_i,和b_i等有关,而且还与所用程序语言变量的有效位数长度L有关。为了保证模型运行中能正确选择所需的枢列和减小计算误差,本文中从理论上提出M值的上下界的确定方法和简便的定值方法。

The value of M should be a relatively large positive value in big-M-simplex- method for solving linear programming problems in past articles.The arthor indicates that the value of M is related not only to coefficents c_j,a_(ij)and b_i,but also to the length of significant digits of variable(L)in used program.To correctly choose the pivot column and reduce the computation error,M should be restricted between its upper and lower boundaries.Besides,a simple rule to determine it is presented.