求解网络最大流问题的一个算法

为了便于建立与网络最大流问题有关的决策支持系统，本给出一个求解网络最大流问题的数值算法。证明了算法的理论依据，并举例说明了算法的应用。该算法能求出网络最大流和最小截，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

带分解功能的网络最大流问题

本文在[1]和[5]的基础上,研究最大网络流问题.与已有的研究不同的是,本文对最大流问题进行了分解,即把最大流网络分解成几个相互独立的子网络.     

最大流问题的逆问题

讨论了最大流问题的逆问题,提出了ｆ＾０截的概念,给出并证明了逆问题有解的充要条件;当逆问题有解时,把逆问题转化为找一个容量网络的最小截的问题;最后,给出了一个复杂度为Ｏ（│Ｖ│＾３）的多项式算法。     

一类两种商品的网络流问题

本文考虑在有两个发点x1和x2，两个收点y1和y2的网络中，求把商品1从x1运送到y1，把商品2从x2运送到y2的最大流问题，给出一个充分必要条件，指出在一般情况下无最大流，但可以得到满意流，最后给出一个算例。     

一类两种商品的网络流问题

本文考虑在有两个发点ｘ１和ｘ２，两个收点ｙ１和ｙ２的网络中，求把商品１从ｘ１运送到ｙ１，把商品２从ｘ２运送到ｙ２的最大流问题．给出一个充分必要条件，指出在一般情况下无最大流，但可以得到满意流．最后给出一个算例．     

模糊网络最大流算法研究

将模糊数差值B~-A~视为模糊方程X~+A~=B~的解,进而探讨了模糊方程的求解问题,并基于目的规划理论,给出了模糊方程的广义解定义.运用目的规划的单纯型方法,得到了模糊方程广义解的计算公式及模糊方程广义解的若干性质.由模糊方程的广义解引申出了模糊数差值的定义.运用该定义将传统的网络最大流算法推广到模糊环境.结果表明,模糊数差值定义,克服了基于扩展原理意义下的模糊运算所产生的各种问题,解决了这些传统理论方法的拓展问题.     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统，本文给出一个求有上下界网络最大流与最小截的数值算法，证明了算法的理论依据，并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解，在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率，可用于求解最小饱和流问题。     

网络最大流算法的性能分析

对网络最大流问题的求解算法进行性能分析和比较.结果表明,与经典的增载轨算法相比,基于动态规划思想的算法将最大流的求解过程看作一个动态调整过程,通过判断在各个动态阶段各节点允许通过的最大流量,从而能更快的得到网络的最大流值.同时文中的算法分析进一步为这一算法建立了严格的理论基础.     

一个局部带优先权的最大多物资网络流问题

给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.     

具有全局性公平满意度的最大多物资网络流问题

我们研究-个具有全局性公平满意度的最大多物资网络流问题(MMFP-GFMR).该项工作不仅丰富了最大多物资网络流问题的内容,而且可用于研究某些实际优化决策问题,例如运输过程中的一些资源分配问题.文中主要内容如下:(A)定义问题MMFP-GFMR并证明其解的存在性.(B)设计-个求解MMFP-GFMR的拟多项式逼近算法.(C)研究算法的复杂性与逼近程度.(D)最后通过模拟计算验证了我们的工作.     

最大特征根的极值六角链

定义了六角链的一种翻转-粘贴运算, 利用这一运算, 证明了Gutman 猜想.这一证明思想也可用于证明关于Hosoya指标和Merrifield-Simmons 指标的极值六角链的结果.     

最大利润流问题及算法

最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .     

带模糊约束的最大流问题

首次提出带模糊约束的最大流问题,并根据网络中的弧容量限制是否带有模糊性,分别建立数学模型,给出求解这两个模型的相应算法和有关实例。     

求解最大利润流问题的一个算法

为了便于建立与最大利润流问题有关的决策支持系统，本给出了一个交易网络中求最大利润流的数值算法，证明了算法的理论依据，并举例了说明算法的应用。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

网络最大流的"冲塞式"求法

网络最大流的理论与方法在运输与网络管理中有着重要的应用。受在管道中冲塞物体的原理的启发，本提出了一种新的求解网络最大流的方法，该方法较以往的解法有一些特别的优点。     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

网络流问题的病态网络分析

对供需运输系统中的网络流问题,由于供需约束或容量配置不合理,有时会出现一种反常现象:对一个最优运输方案来说,即使供需量或容量限制增加,多运了货物,运费反而下降.这种违背常理的现象反映出网络结构的失衡或畸形,迫使最优方案产生扭曲逆转,这种现象可称之为"病态".在运输问题的特殊情形(无容量约束的最小费用流问题),文献中已有过讨论,称为"运输问题悖论",对一般的网络流问题,研究三种类型的病态:供需约束、容量配置及结构上的病态,并给出判定条件和判别算法,最终引导到网络改造问题.     

考虑路损的最大流问题及其基本特征

本给出了考虑流量损耗的最大流问题的数学模型,并阐明了该问题的几个基本特征。     

考虑路损的最大流问题及其基本特征

本文给出了考虑流量损耗的最大流问题的数学模型,并阐明了该问题的几个基本特征.     

网络流和棒球赛淘汰问题

正1996年9月10日,《旧金山纪事报》的体育版上登载了《巨人队正式告别NL西区比赛》一文,宣布了旧金山巨人队输掉比赛的消息。当时,圣地亚哥教士队凭借80场胜利暂列西区比赛第一,旧金山巨人队只赢得了59场比赛,要想追上圣地亚哥教士队,至少还得再赢21场比赛才行。然而,根据赛程安排,巨人队只剩下20场比赛没打了,因而彻底与冠军无缘。有趣的是,报社可能没有发现,其实在两天以前,也就是1996年9月8日,巨人队就已经没有夺冠