线性规划中大M法的参数M估值问题

The Evaluation of Parameter M in the Big M Method of Linear Programming

在线性规划的单纯形法中,为求初始的可行基有著名的大M法,即惩罚因子法.在通常的运筹学教材中,只说明当M充分大时,大M法是有效的,并没有给出参数M的确切估计值.现给出一个确定的常数M0,并证明当M>M0时,大M法收敛于原问题的最优解.

finding an initi efficient when Moand proves Key words In the simplex method of linear programming, there is a big M method （the penalty factor method） for al feasible basis. The current textbooks of operations research only explain that the big M method is M is large enough, and never give precise evaluation to the parameter M. This paper determines a constant that the big M method is convergent to an optimal solution of the primal problem when M〉M0.