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

• 作者: 高培旺
• 来源期刊: 徐州工程学院学报（自然科学版）
• 学科: 数学
• 关键词: 线性规划 单纯形法 定价准则 分段定价 计算效率
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 【专家特稿】
• 页码范围: 21-26
• 页数: 6页
• 分类号: O221.1
• 字数: 5598字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高培旺		17	19	2.0	3.0