利用“准最优基”简化单纯形法求解过程

Using "quasi-optimal basis" to reduce seeking solution progress of simplex method

深入剖析线性规划的优化机理,在线性规划单纯形表解法的基础上,利用单位资源所获得的价值由大到小规定了进基顺序,依据基的概念确定了"准最优基",将相应于"准最优基"的系数矩阵化为单位阵,然后依照单纯形法的判定标准,判定"准最优基"是否为最优基,若不是,再利用原单纯形表解法进行基的转换,直至找到最优基."准最优基"方法有效地化简了求解过程,使计算缩减了60%以上,同时,不再引入人工变量,求解过程改两阶段为一阶段,为解决大规模线性规划问题提供了一个有效的方法.

Based on linear programming simplex tabuleau method, and from a thorough anatomy of optimizing mechanism of linear programming, the'quasi-optimal basis' is discussed. The basis is composed of those variables, which has provided more value than others. Then the basis can be judged, whether it is the optimum basis by using simplex method; if not, simplex tabuleau method is used to find out optimum basis. 'Quasi-optimal basis' method has predigested the progress of seeking solution; and there have no need of man-variable. It has provided an efficient method to solute large-scale linear programming.