解线性规划问题的内生典式单纯形法

An Endogenous Typical form Simplex Method for Solving Linear Programming Problems

摘要: 对于线性规划问题的约束方程组对应的系数矩阵中没有子矩阵为单位矩阵，如大M法、两阶段法、对偶单纯形法等，都是采取“凑一个单位矩阵”出来，然后进行求解，过程繁琐、迭代次数较多。针对这一问题，采用实验法、分析法和比较法，对线性规划问题的求解过程进行研究，根据约束方程组的内在联系，利用消元法，从系数矩阵中推导出一个单位矩阵，从而使问题得以解决，因此提出了求解线性规划问题的内生典式单纯形法。实验结果显示，内生典式单纯形法适用题型多，求解快捷，迭代次数平均为0.75次。

Abstract: There is no sub matrix in the coefficient matrix corresponding to the constraint equations of the linear programming problem as the unit matrix, such as the large M method, the two-stage method, the dual simplex method, etc., which are all “gathered together a unit matrix” and then solved. The process is cumbersome and the number of iterations is large. In order to solve this problem, ex-perimental method, analytical method and comparative method are used to study the solution process of the linear programming problem. According to the internal relationship of the constraint equations, a unit matrix is derived from the coefficient matrix by elimination method, so that the problem can be solved. Therefore, an endogenous typical form simplex method for solving the line-ar programming problem is proposed. The experimental results show that the endogenous typical form simplex method is applicable to many types of questions, fast in solving, and the average number of iterations is 0.75.