科研之友
微信
新浪微博
Facebook
分享链接
摘要
提出第一阶段单纯形法的一种分段定价策略,而在此策略下可产生两种单纯形算法变式.根据Cheng的判断准则将所有非基变量分成四段,其中一段由最优基本解中的非基变量构成,在迭代过程中对另外三段非基变量依其保持非基的可能性程度先后交替定价.第一种算法从迭代开始就根据Cheng的两个判断准则对四段非基变量不断调整,这虽极大节省了定价计算的工作量,但两个判断准则的计算需要耗费大量时间,导致该算法计算效率很低.第二种算法对第一种算法作了改进,当目标当前值超过最优值的2/3时,开始对非基变量分段,然后只根据Cheng的一个较简单的判断准则对定价后的非基变量进行调整.对来自NETLIB和MIPLIB的27个典型算例的初步试验结果表明,改进的算法不仅比经典单纯形算法所用的总迭代次数要少,在所有算例上所搜寻的非基列数也少,所耗费的计算时间更少,其计算性能高效而稳定.
-
单位闽江学院
