Improvement to the Sequential Combination Tree Algorithm
-
摘要: 为了提高有序组合树法的运算效率,必须充分利用约束条件中的有关信息.通过深入分析,提出了极差、必选变量、不可选变量等概念,将多个约束条件联系成为一个整体.提出了用检验约束条件的相容性,并以相容性为判据进行截枝的新办法.证明了如果必选变量全部取值为1是可行解,则必是最优解。给出了改进后的有序组合树法的计算步骤流程.Abstract: To increase the efficiency of sequential combination tree method,it is necessary to make full use of information in the constraint conditions.Based on a thorough analysis of the method,the concepts such as ultimate difference,necessary variables,and ineligible variables were proposed to combine constraints as a whole.A new algorithm was presented,in which the compatibility of constraints are determined and taken as a criterion to cut branches.It was proved that if all the necessary variables taking 1 is a feasible solution,it is the optimum solution.The flow chart of the new algorithm was presented.
-
Key words:
- 0-1 programming /
- constraint /
- searching algorithm /
- sequential combination tree
-
江南,史峰,任少卿.铁路承认车最优分配模型及算法[J].铁道学报,2005,27(5):19-23.JIANG Nan,SHI Feng,REN Shaoqing.The optimum model and algorithm for approved rail car allocation[J].Journal of the China Railway Society,2005,27(5):19-23.[2] 朱喜伟.货物配车调运问题初探[J].铁道运输与经济,2002,24(12):39-40.ZHU Xiwei.A tentative study on wagon-fitting and displacing of goods[J].Railway Transport and Economy,2002,24(12):39-40.[3] 尹传忠,卜雷,蒲云,等.行包运输行李车三维装载优化问题研究[J].铁道学报,2005,27(2):15-20.YIN Chuanzhong,BU Lei,PU Yun,et al.Research on three-dimensional load optimization of luggage vehicles in luggage and package transportation[J].Journal of the China Railway Society,2005,27 (2):15-20.[4] 郭耀煌.运筹学原理与方法[M].成都:西南交通大学出版社,1994:112-115.[5] 藤传琳.管理运筹学[M].北京:中国铁道出版社,1986:159-162.[6] 马振华.现代应用数学手册运筹学与最优化理论卷[M].北京:清华大学出版社,1998:210-214,1-2.[7] 朱松年.有序组合树法[J].西南交通大学学报,1985,(2):15-25.ZHU Songnian.The sequential combination tree method[J].Journal Southwest Jiaotong University,1985,(2):15-25. -
点击查看大图
计量
- 文章访问数: 1366
- HTML全文浏览量: 64
- PDF下载量: 398
- 被引次数: 0
下载: