单纯形法的一种新的入基准则

A NEW PIVOTING RULE FOR THE SIMPLEX METHOD

单纯形法是求解线性规划问题的一种实用方法 ,入基准则对单纯形法的有效性起着决定性作用 .该文提出一种新的入基准则 (称其为最大加权检验数准则 )并利用随机模拟方法将该入基准则与其它入基准则的进行比较 .随机模拟的结果表明该准则优于最大检验数准则和最大上升准则 .还求出平均转轴次数与问题规模的近似函数关系 ,并由此得到 :当线性规划问题的规模很大时 ,最大加权检验数准则的预期转轴次数小于最大上升准则的 1/ 3,小于最大检验数准则的 1/ 10 .

The simplex method is a practical method for solving linear programming problems. Pivoting rule is crucial for the number of steps in the method. In this paper, a new pivoting rule (called lagest weighted_coefficient pivoting rule) is introduced. Then the random simulation method to compare the number of steps of the simplex method with other pivoting rules is applied. The simulation results show that the pivoting rule is better than the largest_increase rule and the largest_coeffient rule.Finally, the approximate relation between the expect number of steps and the size of a linear programming problem are got. It follows that the expect number of steps for largest weighted_coefficient rule is less than 1/3 of that for largest_increase rule, and less than 1/10 of that for largest_coefficient rule.