线性规划最优基的退化性和矛盾性

The degeneration and contradiction of optimal basis in linear programming

通过讨论基与基解的关系得出,当线性规划问题基与基解非一一对应时,最优基会出现如下矛盾和退化:①在互为对偶的两个线性规划问题中若有一个问题的最优基不唯一,则这两个问题的任何一个最优基都或者是退化基,或者是对偶退化基;②有最优基B产生矛盾:一方面,B可行,使目标函数达到最优,另一方面,B又不满足最优基的判定条件,不是对偶可行基.文中还分析了基与基解非一一对应的原因、最优基退化性及矛盾性在求解中的作用.

Through the discussion of the relation between the basis and the basic relation, A conclusion can be made, that is ate due to the irreversible linear programming proble , in linear programming, the optimal basis becomes contradictory and degenerrelation between basis and basic relation： ①When any of the two mutual dual ms has more than one optimal basis, any optimal basis may be degenerate or dual degenerate.②There will be contradictory optimal basis B： on one hand, B is feasible basis which makes the objective function optimum; on the other hand, B, which is not dual feasible basis, doesn＇t satisfy the optimal basis condition. This paper discusses the causes of the irreversible relation between basis and basic relation, and it also deals with the functions of degenerate optimal basis and contradictory optimal basis in solving the problem.