网络流与最大流问题

本文主要讨论了网络流及其应用 ,其中最大流问题是当今网络流理论中最重要的问题之一 ,它在我们现实生活、科技及生产领域中都有广泛的应用     

网络最大流算法的改进

将已有的网络最大流的算法－标号法改进为断路法，从而加快了求网络最大流的速度并减少作标号图的麻烦。     

改进的Ford-Fulkerson算法

在网络的管理与控制中,需要考虑成本和流量问题,即网络的最小费用和最大流量问题.利用改进Ford-Fulkerson标号法求得单端和多端的网络最大流,使得通过一次标号得到全部增广链,并同时增流即得最大流.从而在考虑费用最小,最终求得网络最小费用.transportation最后用实例展现了此过程.     

求解最大流问题的"构造式"算法

在前向推进最大流算法的基础上作了改进，提出一种求解最大流问题的“构造式”算法。该算法应用图的深度优先搜索原理，摒弃前向推进最大流算法的并行控制而着眼于每一支流的依次增广，逐步构造中间过程“构造图”的结构并最终得到网络最大流。该方法增强了算法的直观性和可控性，易于实现。     

网络最大流算法在房产推销策划中的应用

在房产营销过程中，利用图论中的匹配思想，把追求销量最大的目的转化为求偶图的最大匹配问题，然后用网络最大流算法给出解。     

特殊网络结构上的最大流问题研究

简述了网络最大流问题的现状,给出网络最大流问题的数学模型并对Goldberg推进-重标号算法及它所使用的关键技术进行分析,同时阐述了几种在特殊网络结构上的网络最大流问题     

求解最小费用流问题的蚁群算法

为了运用蚁群算法解决最小费用流问题,首先结合有向网络描述了最小费用流数学模型,运用从终点向始点反向计算的思想求解在最大可行流约束下的最小费用,然后给出了其具体过程.最后通过仿真实验,调整圈法和标号算法验证表明：该算法是有效可行的.     

曲线网最大流问题初探

本文简介什么是曲线网最大流？曲线网最大流的性质；曲线网最大流性质的应用．     

求解多设施韦伯问题的半光滑牛顿增广拉格朗日法

重点研究了解决多设施韦伯问题(MFWP)的有效算法。首先,将MFWP重新表述为它的等价形式,然后提出一种半光滑牛顿增广拉格朗日(Ssnal)算法来求解MFWP,并且刻画了Ssnal算法的全局收敛性和局部渐近超线性收敛性。最后,在数据集上进行数值实验,结果表明,Ssnal算法在鲁棒性和计算效率方面都优于双曲近似过程(HAP)算法和交替方向乘子法(ADMM)。     

基于Petri网的最大流-最小割问题建模与求解

给出了任意流网络及其残留网络Petri网模型的构造流程;通过对模型中各元素的实际意义进行分析,指出如何得到最大流的各个分布;从理论上证明达到最大流的条件并给出通过活性分析可以得到一个最小割的结论;将残留网络和流网络Petri网模型结合起来给出最大流-最小割问题完整的解决方案。Petri网图形化的仿真过程为研究网络流从局部到整体的变化提供了直观的描述。仿真结果证实该方法准确、有效。     

模糊网络最小流问题的求解

网络最小流是网络发生最严重堵塞时通过网络的最大流量,它是设计交通网络,特别是紧急疏散网络的重要参数。本文将传统的网络最小流问题推广到模糊环境,探讨了弧的容量为模糊数时的情况,建立了相应的数学模型并给出了相关解法。最后,给出了一个具体实例。     

网络最大流的最大容量有向路算法

针对单源、单汇网络给出最大流问题的一个新算法--最大容量有向路算法,算法的核心思想是利用分层原理在增量网络中反复寻找从源点到汇点的在一定规则下的容量最大的有向路,直至找不到有向路为止.给出算法的复杂度为O(mn)与最大流问题的两个具有代表性的算法--Ford-Fulkerson算法和Dinic算法,作了复杂性和实例比较,结论是最大容量有向路算法的效果好于Ford-Fulkerson,算法不低于Dinic算法.该算法完全能够编程实现,仿真试验结果表明,算法效果良好.     

基于分治、剪枝和蚁群算法求解最大团问题

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上,实践上都具有一定的意义。蚁群算法已成功地求解许多组合优化难题。本文使用分治法,将图分解成子图,对各子图应用蚁群算法求解,并根据目前求得的最优解的值对各个子图进行剪枝,去除对求解没有意义的点,提出基于分治、剪枝和蚁群算法求解最大团问题的算法。它减小了问题的求解规模,使求解容易。实验取得了较好的结果。     

浅析求解最大子段和问题的算法

用计算机解决复杂的问题,往往把一个大的、复杂的问题根据其功能划分为不同的模块,每一个模块完成一独立的功能.如果每一个模块用计算机语言来实现,那么当所有模块都实现时,即为对复杂问题的解决.最大子段和问题就是一具有独立功能的小模块,在很多大的问题中都涉及到此问题,用不同的算法解决此问题,并分析其优劣.     

最短路问题的简便算法（二）

本文分别给出了一种比E．W．Dijkstra最短路算法更为方便的求最短路的算法和一种求最大流－最小费用的简便计算方法。     

一般约束非线性优化的增广Lagrangian算法

构造了一个求解一般约束非线性优化问题的增广Lagrangian算法 ,通过引进函数 φ(x) =max{g(x) ,- λr}可直接处理不等式的约束情形 .并且每次只需近似地求出对应增广Lagrangian罚函数的局部最小点 .在一般假设下 ,算法产生的点列的任意聚点都是问题的K -T点     

修正的增广拉格朗日算法的收敛性

考虑了四种不同的算法策略来修正增广拉格朗日算法,表明不要求乘子有界就能收敛到原问题的全局最优解.     

最大匹配问题的闭环DNA算法

给出了一个解决最大匹配问题的闭环DNA算法模型,并对相应的生化实验做出了说明,实现了仅用删除实验直接构造最大匹配的构想。由于算法仅用到基本删除操作,使得算法的实现简捷、可靠。     

求解多项式最大公因式的一个算法

研究了用辗转相除法求解多项式最大公因式的一个迭代算法。算法将两个多项式相乘,相除等过程用矩阵方法来处理,从而获得了用Matlab软件求解多项式最大公因式的迭代算法。     

基于丢包概率的网络最大流研究

针对网络最大流问题,基于丢包概率提出了一种新的计算方法（Network Maximum Flow based on Dropping rate,NMFD）.该方法首先利用实际队列长度和到达速率定义了丢包策略,并在以前的研究基础上对最大流的计算方法进行了改进.同时,通过仿真实验对比分析了该算法与DINIC算法、FORD算法的性能,结果表明NMFD具有较好的适应性.