网络最大流的矩阵解法

网络最大流问题目前的解法是标号算法,现提出矩阵解法。此方法能求出N网络最大流,并打印出网络流量实际分配情况。 采用N·N方阵存放网络各边的额定容量,其对角线元素存放节点流量不平衡值。通过消负、转移、减流、消正四个步骤将节点流量调正到平衡状态,此时两端点为最大流,其余元素表示流量实际情况。 本文介绍了计算机语言程序及使用方法。     

网络系统异常处理的数学模型

物流以网络流方式运行,网络中顶点有中转容量,同时也有顶点环流容量,顶点环流使用顶点分开为入点和出点的方法来表示.当网络流发生异常变化时,可引起顶点环流增加或减少的变化;而顶点环流也可以起到对网络流异常的调节作用,使网络保持一个可行流.     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

无环网络最大流的一种新算法

网络最大流问题是运筹学和网络优化的重要问题之一.基于动态规划基本思想,提出了在无环网络中适用的一种网络最大流算法.该算法通过判断在各个动态阶段各节点允许通过的最大流量,最终得到终点的最大流量-网络最大流,从而大大提高了执行的效率.最后算法分析和算例表明了新算法的有效性.     

危险天气下的终端区动态容量评估

危险天气对终端区容量分布有着显著影响,常导致其值沿不同方向增减水平迥异。以终端区内的航路汇聚点、机场和实时识别的飞行受限区为节点,可飞路径为弧建立网络,通过几何算法求出弧容量,利用最大流最小割定理找到网络最大流,最后通过改变网络收发点放置方式得到终端区容量沿各方向的分布。算例表明,方法自危险天气生成至消散一直能够连续有效地对终端区进行容量评估。     

回转支承内、外圈装配中的选配模型

在对回转支承的内、外圈进行装配时 ,为了获得最优装配组合 ,运用网络流规划将该问题转化为网络最大流问题 ,并建立了一种选配模型。通过合理定义模型网络的中间点、弧的容量和方向以及模型的一般约束条件 ,应用有效算法求出了模型网络的最大流 ,最终获得了内、外圈的最优装配组合。同时 ,基于该模型开发了用于选配回转支承内、外圈的软件模块 ,并在实际生产中得到了应用     

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.     

一种改进的社区发现最大流算法

为合理设计最大流算法中边容量的分配策略,利用网页的入度和出度的概率分布以及Web页面间链接重要性差异,合理分配边容量,提出改进的最大流算法MBP.实验结果表明,改进的最大流算法MBP发现的社区质量多数情况下优于HITS算法和原始最大流算法.     

基于网络最大流的作者同名区分算法

为了降低不同学者实体之间的共享特征(如机构、发表会议等)给同名区分带来的影响,提出一种基于网络最大流的同名区分算法.该算法将论文实体及其特征融合成一张网络图,根据特征节点的被共享程度设定不同的容量,再计算论文节点间的最大流量,并基于最大流量进行层次聚类.实验结果表明:该算法在精准率和召回率上有较为均衡的表现,具有较好的综合性能.     

基于不确定图的最可靠最大流的改进算法

针对网络规模和稠密度的增大最可靠最大流SDBA算法性能下降较快的不足,提出了基于概率和割集双过滤的状态空间划分算法DF-SDBA.首先,在状态空间划分过程中使用概率约束,针对每一个待处理的区间,筛选掉下界分布概率值小于当前最可靠最大流分布的未处理区间,有效地减少了算法迭代的次数;然后,针对不确定的区间使用割集约束,即在区间上界对应的子图中求出最大流,同时求出最小割集,根据最小割集中的边必须都出现在合格子区间上界向量中这一规则,对待划分的子区间进行筛选,从而进一步减少了划分区间的数量.实验结果表明,相对于SDBA算法,DF-SDBA算法有效地减少了需要划分的区间,很大程度上克服了网络规模和稠密度对算法性能的影响,具有显著的性能优势,有效地提高了算法的适用性.     

一种面向HPC Cloud系统的在线作业调度算法

针对HPC Cloud中的作业之间对网络I/O资源的竞争问题,提出了一种基于动态规划算法、二分搜索算法和网络最大流算法的在线作业调度算法——DBMF算法.DBMF算法专注于物理节点上网络I/O的负载均衡,通过物理节点之间的网络I/O负载均衡来减少对网络I/O资源的竞争.通过与FCFS和RSF算法进行对比,DBMF调度算法有效提高了HPC Cloud的系统负载,减少了作业之间对网络I/O资源的竞争.     

城市复合交通系统容量超级网络评估方法

通过构建虚拟节点和换乘线段,将复合交通系统转化为由小汽车网络、公交网络和轨道交通网络有机组合而成的超级网络,建立复合交通系统容量的超级网络分析评估模型.该模型上层为最大化流量问题,反映复合交通系统服务流量最大化,下层为出行分布和均衡配流的组合模型,反映出行者利用出行路径的选择,同时进行出行方式、换乘节点的选择.以芜湖市城市交通网络系统容量计算为例,结果显示网络容量与城市向东向南发展策略一致,反应了该模型和算法的正确性和有效性.     

外部多水源给水管网水力计算程序的应用

基于求解管网恒定流方程组的Hardr-Cross法(哈代-克罗斯法)及其算法原理,研究管网图形网络结构与水力计算中数据结构的特征．引入虚节点和虚环,将外部多水源管网问题转化为单水源问题．结合某管罔规划设计,以环为主线的编程思路,用C语言编制相应的计算程序并通过调试．     

Algorithm of capacity expansion on networks optimization

The paper points out the relationship between the bottleneck and the minimum cutset of the network, and presents a capacity expansion algorithm of network optimization to solve the network bottleneck problem. The complexity of the algorithm is also analyzed. As required by the algorithm, some virtual sources are imported through the whole positive direction subsection in the network, in which a certain capacity value is given. Simultaneously, a corresponding capacity-expanded network is constructed to search all minimum cutsets. For a given maximum flow value of the network, the authors found an adjustment value of each minimum cutset are‘s group with gradually reverse calculation and marked out the feasible flow on the capacity-extended networks again with the adjustment value increasing. All this has been done repeatedly until the original topology structure is resumed. So the algorithm can increase the capacity of networks effectively and solve the bottleneck problem of networks.     

时变网络最大流问题的过剩流量收缩算法

时变最大流问题是最大流问题的一个推广．设图G=（y,A）是一个有向图且有唯一的发点s和收点P．图G中的每条弧（i,j）∈A都带有两个参数：弧上流的传送时间b（i,j,u）和弧的容量f（i.j.u）,它们都是时间u的函数．时变最大流问题就是找出从s到P满足容量约束的最大流,并要求此最大流的传送时间不能超过一个预先给定的时间限制T.假设：除发点外,流在其他任何顶点都不能等待;b（i.j.u）是正整数;l（i.j.u）是任意的非负整数．提出了该问题的一个过剩流量收缩算法,并讨论了这个算法的复杂度．最后,给出了一个数值算例。     

Multiproduct and multistage integrated production planning model and algorithm based on an available production capacity network

This research attempts to devise a multistage and multiproduct short-term integrative production plan that can dynamically change based on the order priority and virtual occupancy for application in steel plants. Considering factors such as the delivery time, varietal compatibility between different products, production capacity of variety per hour, minimum or maximum batch size, and transfer time, we propose an available production capacity network with varietal compatibility and virtual occupancy for enhancing production plan implementation and quick adjustment in the case of dynamic production changes. Here available means the remaining production capacity after virtual occupancy.To quickly build an available production capacity network and increase the speed of algorithm solving, constraint selection and cutting methods with order priority were used for model solving. Finally, the genetic algorithm improved with local search was used to optimize the proposed production plan and significantly reduce the order delay rate. The validity of the proposed model and algorithm was numerically verified by simulating actual production practices. The simulation results demonstrate that the model and improved algorithm result in an effective production plan.     

一种新的处理能力优先的权值分配调度算法

针对加权最小连接数算法中服务节点权值不准确而直接影响负载均衡效率和整个集群系统性能的问题, 提出一种新的改进算法--处理能力优先的权值分配调度算法. 给出了改进算法的工作流程和要点, 分析并设计了算法的主要技术、 主要模块及原理. 实验结果表明: 该算法解决了LVS(Linux virtual server)负载调度的负载不平衡问题, 提高了LVS集群的性能和稳定性; 改进算法比加权最小连接数算法具有更优化的动态平衡性.     

满足链路约束的拓扑聚集度虚拟网络映射算法

高效的虚拟网络映射算法能提高网络收益,降低物理资源的消耗。假如一个虚拟网络能够被满足映射,那么它对物理节点资源的消耗是固定的,对资源消耗的总大小取决于链路映射。为减少链路资源消耗,相邻的虚拟节点在被映射后应该是接近的。本文提出基于满足链路约束的拓扑聚集度映射算法。该算法在计算汇聚度时考虑节点间的链路请求,是一阶段映射算法。此外,本文根据图的广度优先搜索对虚拟节点排名,使连续映射的虚拟节点有较高的关联性。仿真实验表明,所提出的算法提高了长期网络收益和收益花费比。     

一种新的配电网络重构最优流模式算法

提出了一种改进的最优流模式算法,用于解决以功率损耗为函数的网络重构问题。先从理论上推导出了在最优流模式下打开环网中的一个开关后系统功率损耗率变化的计算公式,然后以打开开关所引起的网络损增量小为启发式规则来打开关以形新的辐射网。