求解线性规划问题最优解时常遇到的几种特殊情况

Several Kinds of Special Cases of Finding Optimal Solution for Linear Programming(LP) problem by the Simplex Algorithm

重点介绍了单纯形法在求解过程中常遇到的几种特殊情况.首先,在一个线性规划问题的最优解对应的单纯形表中,如果至少有一个非基变量的检验数为零,那么该线性规划问题的最优解可能不只一个,当求到另一个最优解时,则原问题必有多重最优解;其次,在单纯形表中,如果某一负检验数所对应的列向量的分量全部非正,则原问题无最优解;再次,在求解过程中,若原问题不可行,而对偶问题可行时,我们可以应用对偶单纯形法进行求解.

This paper introduce the basic idea of the simplex algorithm for the standard form of LP,we begin with a basic feasible solution.We always meet the following several cases.Case 1：If there are at least one nonbasis variables;whose relative costs are equal to zero,then the optimal solution of the LP may not be only one while finding another one,the LP maybe have infinite optimal solution.Case 2：If one of the negative relative costs corresponding to components of the column vectors are all nonpositive,then the LP dose not exist optimal solution.Case 3：If the primal LP is not feasible,while its dual is feasible,then we can use the Dual Simplex Algorithm to resolve them.