树状网络中最短接通时间的快速算法

针对文件分配问题,提出了一种求解树状网络中最短接通时间的快速算法.基于边着色和标号的思想,结合网络拓扑,将原来的网络分解为一系列更小规模的子网络进行处理.子网络对应的最优解逼近原始网络的最优解.理论分析和实验结果表明,在最短接通时间的计算精度略微降低的情况下,本文算法的计算复杂度为O(n).     

用Frame-Stewart算法求解Reeve问题的几个结论

讨论了Reeve问题及其Frame-Stewart算法,对于在该算法框架下在求解Reeve问题所需要的最少步数R(n),利用递推关系得到了几个结论,并且估算了R(n)的计算量.     

一类改进的蚁群算法及其收敛性分析

在基本蚁群算法的基础上,提出了一类改进的蚂蚁算法,并证明了当算法迭代次数n充分大时,对于任意小ε>0,算法至少一次找到最优解的概率P*(n)≥1-ε,当n→∞时,P*(n)→1.数值实验表明,改进的算法在取得满意搜索结果的同时,能减少算法的计算量.     

差异演化算法求解二次分配问题

二次分配问题是典型的NP难题.建立了二次分配问题的数学模型.设计了基于差异演化算法的新方法对其进行求解.给出了差异演化算法求解该问题的具体方案.对不同的二次分配问题算例进行了仿真实验.结果表明,算法可以有效、快速地找到二次分配问题的最优解.     

求解子集和问题的快速算法

针对子集和问题,文中提出了一种快速算法。该算法设计运用了整数带余除法和生日问题的原理。理论分析表明该算法时间复杂度为O(n2),其正确率为1-(T-2/T-1)n2m。随机试验显示,该算法在时间效率上明显优于传统指数时间复杂度算法,且对大集合问题具有很高的正确率。     

一种基于伏格尔法的指派问题新算法

指派问题是一个应用广泛的运筹学问题.用伏格尔(Vogel)法以及闭合回路验优和调优的方法给出了指派问题的新算法,该算法避免了匈牙利法可能导致死循环的缺陷.并编制了通用高效的计算机程序,该程序能求解任意n人员n任务的指派问题.     

分配问题的启发式算法求解

禁忌搜索算法和蚁群算法是近几年优化领域中出现的两种启发式算法.简单介绍了这两种启发式算法的基本原理,给出了应用这两种算法以及其混合算法解决分配问题的求解过程.仿真结果表明混合算法取得的结果较好.     

广义分配问题的一种小生境遗传蚁群优化算法

提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚁群优化算法用于求解NP难的广义分配问题,以避免经典求解算法存在的易陷于局部最优的缺陷.以典型的广义分配问题——火力分配为例,对该算法进行实验,并将实验结果与其它算法进行分析比较.结果表明:新复合算法优化效率高,运行时间短,对其它的NP问题同样适用.     

最优指派问题的动态规划模型及算法

考虑了指派问题:有m项工作和n个人.若m与n是相同的,并且每一项工作只能由一个人来做;同时,每一个人只能做一项工作;符合这一条件的指派问题称为标准指派问题;若m与n不相同, 则称为非标准指派问题.本文在充分考虑了指派问题性质的基础上,建立了求解标准指派问题的动态规划模型,并给出了其求解算法;同时在标准指派问题的动态规划模型的基础上给出了求解非标准指派问题的动态规划模型.最后,通过实例说明了本文提出的方法的基本步骤和计算方法的可靠性.     

关于同余式2n≡4(mod n)

用模幂算法计算出同余式2n≡4(mod n)在3≤n≤1011范围内的所有奇数解.利用由二次剩余推出的一个结论,提高了算法效率,解决了[2]、[3]中提出的一个问题并提出了与此奇数解相关的新问题与猜想.     

匈牙利方法在资源分配问题中的应用

通过对一维资源平行分配问题的讨论,给出了将该问题分解成若干个指派问题的方法,通过用匈牙利方法求解应对的指派问题,得出该资源分配问题的最优解。     

指派问题的遗传算法研究与实现

提出了用遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ）进行运筹学中指派问题（ＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ）优化的新方法。根据优化问题的性质，设计了两种编码方案，以及适合此类问题的复制、交换、倒位、变异四种遗传操作符。在此基础上，完成了整个优化算法及程序框图，并用Ｃ语言实现。计算结果表明，算法设计正确，程序灵活可靠，是解决此类问题的一种行之有效的方法。     

具有学习效应且加工时间可控的单机排序问题

讨论一类加工时间可控的单机排序问题.在这一问题的模型中,机器具有学习效应,工件的实际加工时间为同时依赖于所排位置和所分配的资源量的资源消耗函数,其中资源消耗函数又分为线性资源消耗函数和凸资源消耗函数这两种函数.考虑共同工期分派方法和松弛工期分派方法这两种工期分派方法.极小化一个包含加权总误工数的费用、工期分派的费用、最大完工时间的费用和总资源消耗的费用的目标函数.对于工件加工时间的两种资源消耗函数与工期分派方法的不同组合,算法复杂性为O（n4）的多项式时间算法相应地被给出.创新之处是：在Shabtay研究的基础上增加考虑了学习效应后,计算相关问题的算法复杂性仍保持不变.     

动态自适应蚁群算法在二次分配问题中的应用

采用一种新算法--动态自适应蚁群算法解决二次 分配问题, 并引入3-opt方法对问题求解进行局部优化, 通过对二次分配问题的不同实例进 行实验, 结果表明, 该算法在求解二次分配问题上具有较好的能力, 可以很好地解决较大规 模的二次分配问题, 而以往的算法只适合于处理较小规模的二次分配问题.     

量子遗传算法在目标分配上的应用

量子遗传算法是量子计算和遗传算法相结合的产物,量子遗传算法将量子比特和量子门表示引入到遗传算法中,具有比遗传算法更好的搜索效率和收敛性.目标分配问题是一种典型的NP难问题,传统的方法在求解此问题时很容易陷入局部最优.本文利用量子遗传算有效地解决了目标分配最优化的问题,数值模拟表明量子遗传算法在该类问题中具有效性和可行性.     

分派问题的一种实用算法——对角线法

分派问题是运筹学中一类具有实用价值的问题。本文在分析“匈牙利算法”的基础上,提出了解决这类问题的一种实用算法——对角线法。这种算法思路清晰,过程简单,占用内存空间少,便于计算机求解。     

2种限制性指派问题

提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.     

利用拉格朗日松弛算法求解三维分配问题

将拉格朗日松弛算法与最优求解算法的复杂性进行了分析比较，并将该算法应用于求解3-D分配问题,分析与算例结果表明，该算法可大幅度降低3-D分配问题的求解计算量，是求解3-D分配问题的一种有效算法．     

改进的蚂蚁算法求解任务分配问题

将蚂蚁算法用于求解任务分配问题，并提出一种改进算法来提高其全局搜索能力。文中介绍了任务分配问题和蚂蚁算法，给出了求解任务分配问题的蚂蚁算法的数学描述及求解的算法步骤，在此基础上提出求解任务分配问题的改进蚂蚁算法。两个实例验证了改进蚂蚁算法的优越性。