第一阶段单纯形法的一种分段定价策略

摘要：

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

关键词：线性规划、单纯形法、定价准则、分段定价、计算效率

所属期刊栏目：31

分类号：O221.1(运筹学)

资助基金：闽江学院人才引进基金资助课题MJU2012001;广西自然科学基金项目0728260;国家星火计划项目2013GA690426

在线出版日期：2017-01-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：21-26