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

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

作　　者：马艳琴[1] 张利利[1] 王爱苹[1] 卜春霞[2] 

机构地区：[1]黄河科技学院电子系,河南郑州450063 [2]郑州大学数学系,河南郑州450001

出　　处：《数学的实践与认识》2015年第7期255-260,共6页Mathematics in Practice and Theory

基　　金：河南省科技厅基础与前沿技术研究资助项目(132300410217)

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

关 键 词：单纯形法 亏基 退化 最钝角 主元标 

分 类 号：O221.1[理学—运筹学与控制论]