共查询到20条相似文献,搜索用时 31 毫秒
1.
本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n32n-2),其中n为随机排列中相异数字的个数。算法在给定n的条件下, 相似文献
2.
讨论单机随机排序问题,目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小.设工件间的优先约束为有根森林,机器发生随机故障.对此情况,给出了多项式时间的最优算法. 相似文献
3.
本文运用合作博弈的观点分析和解决在动态决策进程中出现的合作方式发生变化的问题.针对于在博弈树给定的有限个节点上随机改变联盟剖分的动态博弈,通过引入新的特征函数和最优准则,建立了动态最优解PGN向量,同时给出了求最优路径和最优解的算法. 相似文献
4.
带组约束可靠性网络最优化问题的精确算法 总被引:1,自引:0,他引:1
本文提出了一种求解带组约束串-并网络系统最优冗余问题的精确算法.该算法利用拉格朗日松驰和Dantzig-Wolfe分解法得到问题的上界,并结合动态规划求解子问题.算法采用一种有效的切割和剖分方法,以逐步缩小对偶间隙和保证收敛性.数值结果表明该算法对于求解带组约束可靠性最优化问题是很有效的. 相似文献
5.
我们构造了关于 R~n 的一种新的三角剖分——D_1三角剖分,且证明了它比熟知的三角剖分的单纯形个数都少.基于 D_1三角剖分,我们建立了一种新的变维数单纯算法.几个数值例子表明新的 D_1三角剖分及算法的确是更有效的. 相似文献
6.
7.
基于改进混合遗传算法安排生产调度 总被引:1,自引:0,他引:1
研究了某工厂生产调度问题,建立了数学模型.针对这一实际问题,通过引入小生境技术、最优保存策略、近优淘汰策略、自适应调整交叉概率和变异概率,设计了用于求解多个最优顺序的混合遗传算法,用所设计的混合遗传算法对该模型进行了计算,获得了许多最优顺序,这就使得生产调度安排灵活机动,便于智能调度,同时生产量比原来大幅度提高.这表明使用混合遗传算法安排生产调度是非常有效的. 相似文献
8.
9.
10.
罗成新 《数学的实践与认识》2022,(2):82-89
研究松弛工期窗口指派资源约束单机排序问题,决策者需要在一台处理机上连续处理n个独立的任务.每个任务有一个待定的松弛工期窗口,任务的处理时间通过分配资源可控,且是所在位置的递减函数,当函数递减到一定程度时,需要用一个控制参数替换.目的是在可用资源量有限条件下求出任务的处理顺序和工期窗口以及资源分配方案,使得任务中最大费用取最小值.分两步处理:首先将问题转化为非线性凸规划问题,利用凸规划理论求出任务的资源数量;其次通过解指派问题得到任务最优处理顺序,进而求得任务的工期窗口.给出了多项式时间的最优算法,提供一个算例说明算法的有效性和运算过程. 相似文献
11.
12.
为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的. 相似文献
13.
在求解非凸规划的分枝定界法中,剖分区间的选取直接影响到整个算法的收敛速度.本文对现有的LDB区间剖分法进行了改进,给出了一种剖分区间的选取原则,理论分析和数值算例表明采用新的ILDB算法会具有更快的收敛速度. 相似文献
14.
15.
16.
本文讨论内网点连通剖分下网线的编号方法,以使协调方程的带宽尽量的小.这样对解协调方程,进而确定给定剖分下的作条函数空间是有意义的.文中给出一个随机选取的剖分的网线的一个具体编号.对矩形剖分、I型与Ⅱ型三角剖分,给出了它们的带宽分析. 相似文献
17.
关于汽轮机叶片动平衡的一个最优排序问题 总被引:1,自引:0,他引:1
本文讨论在汽轮机转子设计中提出的叶片最优排序问题.它可以转化为特殊的二次分配问题,但由于规模较大,一般的二次分配问题算法(如分枝定界法)难以应用.本文的主要结果是导出最优排列的一个必要条件,由此建立两种实用的启发式算法.一、问题的力学提法 相似文献
18.
针对模型未知且带有时滞的随机线性二次型(SLQ)最优跟踪控制问题,提出了一种自适应动态规划(ADP)算法.首先,利用双因果坐标变换导出原时滞系统的等效系统,构造一个新的由等效系统和命令生成器组成的增广系统,并给出该增广系统的随机代数方程.其次,为了解决随机线性二次最优跟踪控制问题,将随机问题转化为确定性问题.然后提出ADP算法,并给出该算法的收敛性分析.为了实现ADP算法,设计了三种神经网络,分别近似最优性能指标函数,最优控制增益矩阵和系统模型.最后,通过一个数值算例验证算法的有效性. 相似文献
19.
20.
现代金融经济中的很多问题可以构建成随机控制模型,而随机控制的求解却存在一定的困难.马氏链算法应该是一种有效的求解随机控制问题的数值方法.本文以Claus Munk的工作为基础,针对一类最优投资模型,具体确定了马氏链的转移矩阵并证明其满足算法收敛条件,并用MATLAB语言编成一个程序实现. 相似文献