有序组合树法

本文针对线性零一规划模型提出了一种新的解法。它利用特殊结构的组合树及相应算法,能将组合方案按目标函数大小顺次挑出作可行性检查。为了加快收敛速度,还设计了《同构树算法》及《并行算法》,以适应大规模系统的需要。文中对线性零一规划模型的可行性问题,也作了适当的探讨,并给出了鉴别可行性的充要条件。     

Network Decomposition and Maximum Independent Set Part Ⅰ:Theoretic Basis

IntroductionItisofsignificanttheoreticalmeaningtofindthemaximumindependentsetwithinanetwork .Thisisnotonlyrelatedtoclique ,nodecovering ,coloringandmatchingissues ,butalsoassociatedwithmanycombinatorialoptimization problems .In practicalapplications ,find…     

优化编组计划的非线性0—1规划模型及模拟退火算法

技术站直达列车编组计划的优化问题可以用一个目标函数为线性而约束条件有二次的０－１规划模型来准确地描述，采用的模拟退火优化技术是基于多粒子物理系统和组合优化问题之间的类比，能避免陷入局部最优解，该方法可以使铁路网规模问题有效地获得接近全优的解，计算试验结果进一步确定了这种方法的有效性。     

铁路纽车流调度决策模型研究

在对枢纽车流进行分析的基础上，提出了枢纽车流调决策的基本原则和解决枢纽车流调度决策问题的基本思路，进而建立了枢纽车流调度决策模型，较好地解决了枢纽内车流调度决策问题。     

带有改编能力限制的编组计划优化模型及算法

本文用一个非线性０－１规模模型，来描述带有改编能力限制的技术直达列车编组计划问题。能力约束增加了该问题的计算难度。这是一个ＮＰＣ问题。因此，获得一个全局最优解是困难的。本文用模拟退火算法解该问题。该算法可以以很高的概率获得全局最优解。文末列出了两个数值例子，并分别同了考虑和不考虑改编能车约束两种情况下的计算结果。     

路网上车流径路与列车编组计划的整体优化

从组合优化的角度研究车流径路选择，装车地直达列车编组计划及技术站直达列车编组计划三者的统一优化问题，建立了ＴＲＭＰ的数学规划模型，并引进模拟退火算法作为寻优工具，使真实路网规模的ＴＲＭＰ优化决策成为可能。     

网络分解及最大独立集算法研究（Ⅰ）

本文首先分析了一般网络的结构特征，开发出对任意网络进行变换及分解、且不丢失可行解的新方法，继而发现了网络中具有优化迭代功能的特殊子网络；对其进行了较深入的研究，提出并论证了求最大独立集的充要条件：研制出在网络中系统搜索该特殊子网络的新算法。最后，对算法的有效性及可靠性，进行了较全面的分析论证，研究表明，该算法可在时间复杂性O(|V|^5)界内收敛。     

Network Decomposition and Maximum Independent Set Part Ⅱ：Application Research

According to the researches on theoretic basis in part I of the paper，the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part，part Ⅱ of the paper．The algorithms trans form first the general network into the pair sets network，and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network．As for the even network，the algorithm requires only one time of trans formation and decomposition，the maximum independent set can be gained without any iteration processes，and the time complexity of the algorithm is within the bound of O(｜V｜^3)．However，as for the odd network，the algorithm consists of two stages．In the first stage，the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first；then the algorithm turns to the second stage，searching for the negative envelope graphs within the pseudo-negative envelope graphs only．Each time as a negative envelope graphhas been found．renew the pair sets network by iteration at once．and then tum back to the first stage．So both stages form a circulation process up to the optimum．Two available methods，the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network．Both of them link up with each other harmoniously and are embedded together in the algorithm．Analysis and study indicate that the time complexity of this algorithm is within the bound of O(｜V｜^5)．     

整数规划的群论方法及其改进——嵌入有序组合树算法

本文对国外关于整数规划的群论方法作了扼要的述评后,提出了一种嵌入群论模型的整数有序组合树算法。为了进一步加速收敛,还提出非负性截断及整数性截断两种树技截断技术以及一种并行算法。最后,用本文算法对文献[1]的例题也作了计算,以便对照比较。