单纯形法解决LP问题的研究

Reserch on Solving LP Problems by Simplex Method

借助线性代数知识中的线性方程、矩阵理论及矩阵初等变换等知识分析学习单纯形法时的几个过程和步骤。通过实例分析几个过程和步骤疑难所在,指出单纯形法在解决线性规划问题时一般形式、最简单单纯形表的结构、换基迭代过程中"进基"和"出基"的最大值规则和最小比值规则、判定有无最优解的3种情况和有最优解时求最优解的方法等。分析按最大值规则进行换基迭代时,检验行中决策变量对应的最大数有2个以上相同值时的解决方法,按最小比值来确定换出基变量时,当出现2个以上相同的最小比值会出现退化解,对退化解出现的原因为模型中存在多余的约束及出现退化解的解决方法进行了研究。

Application of simplex method was investigated with the knowledge of linear equation, matrix theory and matrix elementary transformation. By analyzing the examples, the general form, the structure of simplex model table, the maximum and minimum ratio roles of entering basis and leaving basis, the three kinds of conditions to determine whether the optimum solutions existed and the method to determine optimum solution in the application of simplex method were pointed. The solution was analyzed in basis iteration by maximum rule, when there were more than two same values of maximum numbers corresponding with decision variable in the check row; By minimum ratio rule, degenerate solution occured as there came more than two same minimum ratios, then it was also investigated for the extra restricts in the model built by the reasons of appeared degenerate solutions as model and the corresponding solutions.