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

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

The degeneration and contradiction of optimal basis in linear programming

Through the discussion of the relation between the basis and the basic relation, A conclu-sion can be made, that is, in hnear programming, the optimal basis becomes contradictory and degener-ate due to the irreversible relation between basis and basic relation:①When any of the two mutual dual linear programming problems has more than one optimal basis, any optimal basis may be degenerate ordual 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 ba-sis and basic relation, and it also deals with the functions of degenerate optimal basis and contradictory optimal basis in solving the problem.