基于最钝角主元标规则的亏基算法

The Deficient-Basis Algorithm Based on the Most-obtuse-angle Principle

在最钝角原理基础上建立了新的主元标规则,它按最钝角原理赋予一组非基本变量较高优先权,先在其中选择进基变量,直到其相应的检验数均满足符号条件;如果此时剩下的检验数均已满足条件,则已达到最优.在亏基架构中引入新的主元规则,能有效地减少每次迭代可选的非基变量的个数.数值试验表明,新算法的效率优于亏基原始单纯形算法,表明了最钝角原理的可行性和有效性.

This paper offers a new pivot rule.A set of non-basic variables is given priority under the most-obtuse-angle principle.Entering variables are select ed within this set,until all reduced costs associated with the set have correct signs. At this moment,reduced costs associated with the remaining non-basis variables are examined.If they all have correct signs,then optimality is achieved. The algorithm is promising in reduction of the number of iterations. New algorithms＇s efficiency is superior to the deficient-basis algorithm. So the most-obtuse-angle principle is a very attractive new approach.