网络最大流问题典型组合算法研究

简述了网络最大流问题的现状,详细分析了几种具有广泛代表性的网络最大流问题组合算法,同时,阐述了几种在特殊网络结构上的网络最大流问题.对网络最大流问题的深入研究具有重要意义和实用价值.     

关于网络最大流问题的生长树求法

本文对网络中最大流问题的求法进行了探索，利用画树图，给出了网络最大流的生长树求法。     

广义最大流问题

将网络最大流问题作了推广，给出了推广后的网络最大流GMF的标号算法及初始可行流计算的办法，并用线性规划的对偶理论说明了有关的结论。     

最大一致流问题的一个逼近算法

通过建构辅助网络，以K0ne和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索，给出了一个新的求解最大一致流问题的逼近算法．然后，进行算法分析，说明了所建立的算法是拟多项式算法，并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系．该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的，并且为研究网络流问题提供了一种新的方法．     

基于标号法求解网络最大流算法的研究

近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展.本文简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法.此算法使得计算网络最大流变得简便,且具有很强的实用性.     

基于DFS的最大流多解问题研究

最大流问题一般是多解的，但传统的求解方法过于繁锁。提出了一种基于DFS的最大流多解算法，可以求得有向流网络的所有最大流解。该算法依据DFS策略，算法的执行效率较高。     

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

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

基于层次网络的最大流求解方法

针对最大流问题的研究现状,提出了分层求解最大流的简单方法,并给出了该方法可行的严格证明。该方法首先求得层次网络的阻塞流,进而最终求得一个最大流。另外,该方法还针对有向流网络的特点,将算法中涉及的流网络、剩余网络和层次网络共用一个网络结构,既有效地降低了算法的空间复杂度,还大大提高了算法的执行效率。     

基于双最短时间的运输分配研究

以运输分配为研究对象，提出了先遣需求完成最短时限和总运输时间最短问题，并给出了问题的网络模型。运用图论知识，构造了基于网络最大流算法和最短时间流算法的计算步骤，算例表明，本算法可有效地解决运输问题。     

使用MPLS解决网络最大流问题的方法

为解决大多数的流量工程问题和网络传输中的最大流问题，该文提出了基于多协议标签交换（MPLS）解决方案，阐述了解决最大流问题的数学方法，提出一种独特的将数据流划分成“微分支”的思想和方法，并介绍微分支的建立过程；给出仿真结果。     

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

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

服务承载网中基于最大流的服务器放置

针对在服务承载网中,传统的服务器放置方法会出现随着服务器个数的增加降低网络整体性能的问题,提出基于最大流效应的服务器放置算法。该算法不仅考虑到了流量因素,还将带宽、延迟、丢包率等网络节点性能因素简化为"距离因子"进行了考虑,解决了传统服务器放置引起的全局低效和网络拥堵问题,保证最大限度地满足用户的流量请求。经过实验验证,基于最大流效应的服务器放置算法相对于传统的服务器放置算法,在平均情况下,平均相应时间减低10%到25%,传输开销降低25%到50%,显著提高了网络性能。     

动态卫星网络性能评估

为评估动态卫星网络性能,对现有卫星星座系统的设计和评估方法进行了研究。提出了使用网络最大流问题对动态卫星网络流量进行评估的方法。利用STK进行仿真,求得动态卫星网络的系统覆盖率、卫星对地仰角特性、系统间各节点建链时刻表。使用分段函数将动态卫星网络转化为网络多个状态的组合以求解网络的最大流。结果表明:网络最大流问题可有效评估动态卫星网络传输性能,动态卫星网络传输性能比单层卫星网络的传输性能高30倍以上。     

多Agent系统中的任务可调度问题

为了将Agent方法应用于应急系统等新领域,在对该类系统研究的基础上提炼出它们的公共特征,根据这些特征设计出一种MAS系统模型,并在该模型的基础上定义了相应的任务可调度问题.利用网络流模型对可调度问题进行了建模,证明了最大流算法可以求解该可调度问题,由此说明该问题是可多项式时间求解的.并且对于给定该问题的一个可调度实例,利用最大流算法还可在系统中找到一组Agent完成所有任务.通过对该网络流模型的进一步分析,得出并且证明了任务可调度判定的充分必要条件,利用这个结论可以快速判断当前任务是否可调度.     

服务承载网中基于最大流的服务器放置

针对在服务承载网中,传统的服务器放置方法会出现随着服务器个数的增加降低网络整体性能的问题,提出基于最大流效应的服务器放置算法。该算法不仅考虑到了流量因素,还将带宽、延迟、丢包率等网络节点性能因素简化为"距离因子"进行了考虑,解决了传统服务器放置引起的全局低效和网络拥堵问题,保证最大限度地满足用户的流量请求。经过实验验证,基于最大流效应的服务器放置算法相对于传统的服务器放置算法,在平均情况下,平均相应时间减低10%到25%,传输开销降低25%到50%,显著提高了网络性能。     

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

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

制造网络的一个最小费用最大流算法

制造网络流广泛应用于解决水源的调度及工厂的产品运输、分配、合成等问题.该文提出一个制造网络流的最小费用最大流算法.     

路网交通流二层规划模型及其极大熵解

分析交通网络系统的特点,研究混合交通OD结构的关联性,在定量分析路网交通流受交通容量、交通安全及交通服务能力等条件限制的基础上,研究路网利用效益最大化及路网交通流量最大化问题,构建一种路网交通流的二层平衡规划模型。利用先验分布理论和极大熵原理,给出模型的极大熵函数解,进一步证明解的存在与唯一性。模型一方面描述了管理部门对路网交通的优化配置,一方面描述了出行者充分利用路网资源的最优选择。最后通过一个实例,分析模型计算的相关结论。     

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.