一类有损耗网络最大流问题的模型与算法

由于阻力及其它因素的存在,网络流在实际中往往是有损耗的.建立了有损耗网络最大流的模型,并依据其流递远递减的特性设计了算法.以各弧还需要的流的消耗量为权值构造一赋权图,找出一条增流链,分配发点以合适的流量,并调整增流链上各弧的流量和赋权有向图上各弧的权值.反复迭代,直到各边流量都饱和或初始量被分配完毕,此时,收点的输入量达到最大值.最后通过实例验证了其正确性.     

交通运输网络中两个结点间有流量约束的最小费用最大流算法

对交通运输网络最小费用最大流的分配是在满足容量限制条件和流量守恒条件下,基于总费用最低的原则进行的,但在实际应用中,通常对交通运输网络中两个结点之间的流量有具体的要求和约束限制条件.针对交通运输网络中两个结点之间有流量约束的最小费用最大流问题进行了分析,总结了两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围内的3种约束条件.基于连续最短路算法中构造伴随增流网络的思路,设计了这3种约束限制条件下的最小费用最大流分配算法.利用这个算法,可以解决交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题.在交通运输领域,两个结点之间有流量约束的最小费用最大流问题普遍存在,这些算法也为解决实际的运输问题提供了应用基础.     

基于信号强度和功率损耗的分层网络切换算法

为解决毫微微小区基站布置在宏蜂窝小区中引起的切换问题,提出了一种新的分层网络切换算法.该算法主要基于用户接收的信号强度和信号在传播过程中的功率损耗2个参数进行切换判决.当依据接收的信号强度进行切换判决,且其不能有效工作时,将功率损耗作为辅助判决条件,可提高毫微微小区的利用率和降低算法复杂度.仿真分析结果表明,与传统的切换算法相比,该算法的切换次数增加了1倍;与基于宏基站和毫微微小区基站联合信号强度的切换算法相比,减少了1/2不必要的切换次数.     

最大独立集算法

本文提出了网络中的一种特殊结构－负包络图。原来是它包含了网络的最小截，因而制约了网络的最小流量。研究表明，负包络图也是关于网络最大独立集的充要条件。本文以既有的最大流算法为手段，利用这个充要条件，给出了偶网络上求最大独立集的有效算法，而且也给出了在奇网络上求最大独立集的递归算法。     

一类点权网络中的全局最大动态流问题

全局最大动态流问题在交通运输等领域有着广泛的应用,以往关于该类问题的研究,基本上是针对只含弧权的普通网络或节点有一个停留时间和停留量限制的点权网络．但应用于某些实际问题时,网络中节点的权重具有方向性,一定数量的流通过节点时所耗费的时间和容量限制与其走行方向有关．本文针对这类点权网络,研究其全局最大动态流问题,建立了数学模型,提出了一种改进算法,并给出了数值算例．     

基于Petri网的网络最小费用最大流算法

将Petri网方法应用于求解网络的最小费用最大流问题,提出费用Petri网的定义,设计费用Petri网的变迁使能规则并提出求解最小费用最大流问题的Petri网算法.与以往的算法不同,该算法通过对库所进行标号寻找变迁的触发序列,并在该序列上增流.最后举例说明算法的应用.     

编组站静态配流网络模型

配流是编组站阶段计划不可缺少的内容，本文为此建立了网络模型，将静态配流问题转化为最大流问题，并通过分析和证明，使模型进一步得到简化，从而缩小了问题的规模，可用最大流算法方便地求解。     

带有区间数弧容量上限的网络优化

提出了弧容量上限为区间数的网络优化问题;给出了保守最大流、乐观最大流、最小风险代价乐观最大流和最小风险代价流的定义和数学模型;针对目标函数的非线性特性,设计了特殊的算法步骤;引入可调圈概念,通过求最大流和给定流配流问题的多重解以获得最小风险代价最优解;最后,本文还给出了算例,验证了算法的有效性．     

基于实用的技术站直通列车接续方案计算方法研究

编制网络列车运行图的很重要的一环就是处理直通列车在技术站的接续与始发列车的合理协调问题,通过分析技术站直通列车接续与始发列车的相互关系,建立优化该问题的数学模型,并将其与转化为网络流模型,用最小费用最大流方法求解,实际应用表现,该算法能够有效地解决技术站直通列车接续问题。     

求解最小费用最大流问题的分枝界定法

本文纠正文中的一个当之处，对于在保证最大流的前提下，求解最小费用最大流问题，给出一种便于在计算机上操作的分枝界定算法。     

多品种流中特定品种在结点上的流量有要求的最大流算法设计

本文首先分析多品种流交通网络的特性,在借鉴Ford-Fulkerson算法的基础上构造了求多品种问题最大流的基于多品种流的Ford-Fulkerson算法。然后分析了多品种流交通网络对特定品种在结点上的流量有要求的几种情况,并设计了这几种情况下交通网络求最大流的算法。在实际交通网络中多品种流问题普遍存在,对特定结点的品种的流量有要求的多品种问题更是不胜枚举,本文的算法为解决实际问题提供了应用基础。     

A Note on k-Limited Maximum Base

Introduction Findingaspecialmaximumbaseofamatroidis aninterestingproblem.Theproblemhasmanyappli cationsinnetworks,graphtheory,andcombinatorial optimization.InRef.[1],Edmondsgavearelation betweenamatroidandgreedyalgorithm,which answeredhowtofindthemaximumb…     

���ڸ���ͼ���۵�·��������Ľ��㷨

在路网规划中,路网关键断面的确定对于解决路网中的交通瓶颈问题有很大的帮助。路网关键断面问题可以转变为寻找路网最大流最小割的问题。本文首先对现有求解网络最大流的各种算法进行了分析和比较。然后,基于图论中的辅助图理论和求解最大流中的Dijkstra算法,得到了一种求解无向路网中最小割集较为简便的算法,即通过构造辅助路网,利用求辅助路网最短路的方法得到最小割集,即原始路网的最大流。在此基础之上,利用VC++计算机语言程序实现了该算法。最后通过对天津市公路网的分析,进一步对本算法进行了说明。通过比较可知,这种方法是一种确定网络关键断面较为简便的算法,并且会对交通规划与管理提供重要的理论依据和数据支持。     

多品种流交通网络的最大流算法研究

基于Ford-Fulkerson算法在单一品种网络中最大流量分配的思路,通过对多品种交通网络的网络特性进行分析,作者将多源多汇的交通网络构建成单源单汇的形式。在保证符合流量约束的条件下,设计了适用于多品种交通网络的最大流分配算法。在交通网络的实际应用领域里,多品种交通网络的问题普遍存在,因此该算法为解决实际交通网络的相关问题提供了基础。     

Improved Algorithm about the Maximum Flow in Road Network Using Auxiliary Graph Theory

In road network planning, locating the key sections will be very useful to solve the traffic bottleneck. Locating the key sections is equal to finding the maximum flow. To begin with, this paper analyzed and compared kinds of methods solving the network maximum flow problem. Second, this paper pointed out a convenient method based on the auxiliary graph theory and Dijkstra method. That is to say, the method could be used to get the minimum cutset and the maximum flow using the shortest path algorithm, and the VC++ program was also used. Finally, based on the road network of Tianjin, an example was given for further explanation. Through comparison, we know that it is a convenient method to locate the key sections and can support the transportation planning and management with theoretical basis and data.     

系统最优的动态交通网络流

智能交通系统是一个复杂的综合系统,动态交通流分配是它的一个关键问题,是运输科学的一个前沿和热点.对于已经建立的系统最优的动态交通流分配模型,根据非线性规划问题的Kuhn-Tucker条件求解出问题的解.由于交通网络是一个大系统,结合分批调度理论将交通网络进行分批处理后简化了配流过程中的寻径,最后设计出分批并行调度算法.     

双环网络DL（N,h）（h｜N）的最短路径算法

对双环网络DL（N,h)（满足最大公因数g(N,h)=h)进行了分析,证明了这类双环网络中最短路径形式唯一且可用简单的数学表达来描述,给出了最短路径的公式,在此基础上,给出了一个求最短路径的简便算法,讨论了该类网络的直径等有关问题,证明了两点间的平均距离等于直径的一半。     

基于进化规划的BP神经网络学习

通过对将传统的BP算法和遗传算法应用到BP神经网络的学习的研究和分析,指出它们存在的缺陷。提出一个改进的进化规划算法,并将其应用于BP神经网络的权值优化。取XOR问题和4奇偶性问题的实验对传统的进化规划算法和改进的进化规划算法进行实验对比。实验结果表明,本文中提出的改进的进化规划算法优于前2个算法。