灾情巡视路线寻优模型

本文讨论了灾情巡视路线的优化问题。并总结出一些在这类图中求最优回路的有效法则。文中首先将乡村公路示意图转化为赋权连通图,并通过最小生成树分解法将原权图分为若干子图,分析并给出在这些子图中寻找最佳回路的若干原则:扩环策略、增环策略、换枝策略。依据这些原则,求得不同条件下的巡视路线。 当巡视人员分为组时,在要求总路程最短且尽可能均衡的条件下各组巡视路程分别为:2O6.8km,219.5km 159.3km。当要求在24小时完成巡视,至少需分4组,巡视完成时间为:22.3小时。当巡视人员足够多时,完成巡视的最短时间为6.43小时,巡视人员需分成22组     

灾情巡视路线的设计

本文建模的主要思想是将巡视路线的设计分为两个部分:首先生成一个可行的巡视路线,然后利用启发式算法对巡视路线进行调整优先,对可行路线的生成给出了三种方法,1.采用直观判断,较为简单,2.借鉴了求Hamilton圈的方法,3.基于最小生成树,求出的路线总路程较短,为553.6公理。本文采用方法3得出的路线作为启发式算法的初始路线。 本文提出了一系列启发式算法并采用一定的调整规则对初始路线进行了调整,较好地解决了所提出的问题。对于问题1,给出了均衡度的概念来衡量各组路线的均衡性,解为总路程587.2公理,均衡度0.16;对于问题2,采用点调整的规则求出用4组完成巡视所需的最短的时间22.62小时,对于问题3,采用一种最短路线调整法求出在最短的时间6.43小时内,用22组就可以完成巡视     

校园最佳游览路线问题的数学模型分析

将某高校的校园示意图转化为赋权连通图，求得该连通图的邻接矩阵，利用Floyd算法及图论软件包构造一个最短路径矩阵，得到一个赋权完全图，将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题，建立混合整数线性规划模型，并利用优化软件求得最优解．从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题．     

约束最优路线问题的模拟退火解法

本以１９９８年全国大学生数模竞赛中的Ｂ题（即“灾情巡视路线”）为例,介绍一种最优路线问题的方法－－模拟退火法＾「１」。该法对旅行推销员、中国邮递员等问题,即使有约束条件,也能求得较好的近似解,具有适用范围广和可拓展的优点。     

灾情巡视路线最优解的证明

本文对灾情巡视路线中的问题三,从理论上证明了完成巡视至少要分22组,并给出一个分22组总巡视时间为130.578小时的方案     

基于离散近似迭代法的多阶段M-V投资组合优化

提出了离散近似迭代方法,并用该方法求解具有交易成本和交易量限制的多阶段均值-方差(M-V)投资组合模型.离散近似迭代方法的基本思路为:首先,将连续型状态变量离散化,根据网络图的构造方法将上述模型转化多阶段赋权有向图;其次,运用嘉量原理求出起点至终点的最长路程,即获得模型的一个可行解;最后,以该可行解为基础,继续迭代直到前后两个可行解非常接近.还证明了该方法的收敛性和复杂性.     

路段容量约束弹性需求交通均衡分配近似算法

本文研究了带路段容量约束弹性需求用户均衡交通分配问题及其近似解法.采用超需求模型将弹性需求转化为固定需求,提出了一种带路段容量约束弹性需求用户均衡交通分配近似算法.该算法在迭代过程中,通过不断自适应调节排队延误因子、误差因子来近似真实路段行驶时间,使路段流量逐步满足约束条件,最终达到广义用户均衡.这种方法克服了容量约束弹性需求用户均衡分配计算量大及随机分配法要求枚举所有路径的困难.随后证明了算法的收敛性,并对一个小型路网进行了数值试验.     

N车探险问题的一种ε-近似度的近似算法

本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了-个收敛速度为二阶的迭代箅法,文章最后给出算法实例.     

灾情巡视问题的蚁群两目标优化算法研究

分析目前灾情巡视问题求解方法存在的缺陷,归纳出灾情巡视问题两目标优化模型.针对灾情巡视问题模型特点,引入蚁群算法和多目标优化理论,提出两个灾情巡视问题的蚁群两目标优化算法:算法1将灾情巡视问题的道路网络转化为完全图,增加m-1个(m为巡视组数)虚拟巡视起点,将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,然后使用蚁群算法和多目标优化理论进行迭代求解.算法2使用一只蚂蚁寻找一个子回路,m个子回路构成一个灾情巡视可行方案,采用罚函数法和多目标优化理论构建增广两目标优化评价函数,使用g组,共g×m只蚂蚁共同协作来发现灾情巡视问题的最优解.算法特点:①算法1将灾情巡视两目标优化问题转化为单旅行商两目标优化问题,可以充分利用已有蚁群算法求解单旅行商问题的研究成果;②两个算法引入蚁群算法,提高了算法效率;③两个算法克服目前灾情巡视问题的求解方法不严密性缺陷;④两目标优化算法可以为用户提供多个满足约束条件的Pareto组合解,扩大了用户选择范围,增强了算法的适用性.算法测试表明:灾情巡视问题的蚁群两目标优化算法是完全可行和有效的.     

几种特殊结构全光网中多播路由的波长分配算法

研究全光WDM网络中多播请求的路由与波长分配问题.给定网络拓扑和一组多播通信请求,要求对其进行路由和波长分配,满足波长连续性和波长无冲突约束,使得所用的波长总数最少.就几类特殊网络进行了研究.首先对二分树网络进行了研究,此时问题是多项式时间可求解的.其次对树网络进行了讨论,证明了即使是星网络,问题也不存在近似比小于m1/2-ρ(0＜ρ＜1))的近似算法,除非NP=ZPP,这里m是星图的边数.随后给出了近似比为(√m 1)(log r/√m 1 1)的近似算法,此结果对一般图也成立.最后考虑了环网和树环网,给出了近似比为3.6和2△的近似算法,这里△是图的最大度.     

一种求解救灾物资运输问题的改进解法

本文通过对B运输问题建立数学模型,提出了一种求解B运输问题的改进解法。改进解法首先通过最小元素法求出初始解,然后进行变量闭回路法调整,直到求出最优解,并给出了一个计算实例证明了解法的有效性。文章还对改进解法和另外两种现有的算法进行了综合的分析,由于改进解法计算过程中采用的变量闭回路法省略了求检验数的环节,使得新算法比两种现有的算法更简便。     

分块分层优化的旅游路线规划问题研究

针对旅游路线规划决定着自驾旅游者的旅游成败问题,利用分块分层优化的思想解决了旅游路线规划这一网络优化问题。用赋权图和近邻聚类的思想构建分块网络加权图,建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型,规划区块内景点的自驾旅游路线;然后将各区块视为节点、区块间旅游时间作为时间权值之一,建立改进的多旅行商优化模型,并用模拟退火算法规划出区块间的自驾旅游路线;其次,用类比一维装箱问题的思想,建立了求最少旅游年数的一维装箱模型,并用交叉装填算法求得其最小值;最后,应用提出的方法为西安市的自驾旅游爱好者规划出了满足多种约束的游遍全国201个5A级景区的最佳旅游路线。     

一类速度不同的具有m台通用机的n组工件的排序问题

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全问题,人们通常寻求其近似算法．文中提出了一种改进的LPT算法,利用。首先空闲”准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的C‰。。问题,得到了利用该近似算法所得的解T与最优解T＊的—个估计：T/T＊≤2＋（n-2）/（m＋1）     

含回路网络的中心选址 Ⅰ.单回路情形

本文对单回路网络引入了一种新的双标号准则,借此给出了求其1-中心的O(n)阶算法。对边不交的多回路网络,在Ⅱ中将给出一个有效的去边准则。设网络G=(V,E)是一个无向连通图,V(G)和E(E)分别表示其顶点集和边集。在此,我们考虑如下的网络选址问题其中p∈G表示p也可取在边上。关于树网络的中心选址,有关文献[3]、[4]、[5]已做了深入的研究。本文对单回路网络引进了双标号准则,从而给出此类网络1-中心选址的O(n)阶算法。     

多阶段均值-半绝对偏差模糊投资组合优化研究

考虑交易成本和交易量限制,提出投资组合的收益率的隶属函数为梯形的多阶段均值-半绝对偏差可能性投资组合模型,并用自创算法——离散近似迭代法求解.其基本思路为:将连续型状态变量离散化,根据网络图的构造方法将上述模型转化多阶段赋权有向图;运用极大代数求出起点至终点的最长路程,即获得模型的一个可行解;以该可行解为基础,继续迭代直到前后两个可行解非常接近.文章还证明了该方法的线性收敛.最后,文章以一个具体的算例验证了该算法的有效性.     

统计总复习小学数学毕业复习指导系列之六

一、求平均数 [知识综述] 求平均数,其实质是在总量不变的情况下把几个不相等的数量移多补少,使各个数量相等.解题的关键是在求一组数据的平均数时,必须知道总数和总份数这两个数量,然后根据数量关系"总数÷总份数=平均数"求出平均数.在解答求平均数问题的应用题时,有三点要提醒同学们注意:1.许多情况下,总数或总份数这两个数量并不是直接告诉我们,需要我们根据题目中的条件求出;2.根据"总数÷总份数=平均数"数量之间的关系,用"平均数×总份数=总数"可以求出总数;3.求平均数时如果除不尽,一般保留两位小数.     

关于单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q的一个注记

研究了单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q,证明了该问题与问题1|MAi|∑wjcj及问题1|hi,pmtn|∑wjcj之间是相互等价的.对wj=pj时的特殊情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对wj任意的一般情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1||∑wAjcAj:fBmax≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1||∑wAjcAj:∑wBjcBj ≤ Q具有多项式时间近似方案(PTAS).     

求复数根的路斯法

<正> 我们要研究的问题是求实系数代数方程的根.为了解决这个问题,首先应当求出根的近似值.求出充分好的近似根后,刚已有多种有效的方法使近似根逐步地精确化.设该代数方程仅有实根,则求近似根的问题并不困难.设该代数方程有虚根(非实数的复根),用路斯法可以逐步地定出该虚根的实部的近似值.如何求出与该实部近似值对应的虚根的虛部近似值,至今还没有很简单的方法.在本文内作者将证明在用路期法定出虚根的实部的近似值后,就可以从路斯列表计算法的表格上的已算出的数字毫不费力地算出该虚根的虚部的近似值.即使同一实部对应着两对或更多对虚根吋,定出这些虚根的各部也没虚有困难.当虚根的虚部很小时及     

负载均衡问题

自Ron Graham20世纪60年代发表第一篇负载均衡算法的论文以来,平行机排序作为组合优化近似算法理论的首个问题引起了学界的广泛兴趣,其本身研究的不断深化也一路见证了该领域的发展历程.介绍负载均衡问题的来龙去脉,特别是作者所在团队在相关问题的研究进展,从算法和复杂性不同的视角分析经典问题的计算本质,并对未来的研究提出一些建议.     

钢管的订购和运输

本文先利用问题一中铺设线路无分岔的特点 ,建立了基于图解法的最小面积模型 ,将规划问题转化为使若干折线段下方面积和最小的问题 ,通过简单的判别准则 ,手工求得最小总费用为 1 2 78631 .6万元 ,并对该结果最优性进行了说明 .对问题三参考网络流思想建立了适用于一般铺设路线的非线性规划模型 ,用SAS得到一个最优方案和最小费用 1 4 0 6631 .4万元 ,并用此模型对问题一的灵敏度进行了准确的定量分析 .