紧急网络中的最小饱和流问题(英文)

网络Ｎ中的一个流，如果沿前向已无法再增流，则称为饱和流．在交通拥挤或紧急疏散时，网络往往被一饱和流所堵塞．显然，这饱和流的值越小，网络的性能就越差．于是从网络分析的观点就提出最小饱和流问题．本文首先证明此问题是ＮＰ-困难的，然后给出关于最小饱和流与最大流的关系及算法方面的结果．

堵塞网络中最小饱和流的灵敏度分析

由于流动单元的随机流动,在网络结构堵塞点处经常会发生堵塞,网络堵塞最严重时的饱和流是最小饱和流,它小于最大流值。网络当前的饱和流反映了网络的实际流通能力,以网络最大流为设计流通能力的网络中,发生堵塞时实际流通能力经常达不到设计流通能力。为缓解网络的堵塞,可以通过扩充某些弧容量的方法。由于网络中存在一类弧,增加这类弧容量不仅不能改善网络的堵塞程度,有时反而会更加恶化网络的流通性能。本文利用网络最大堵塞截面的性质,分析了改变截面中的弧容量时对最小饱和流的影响,结果表明最大堵塞截面中增加正向弧的容量可以改善网络的堵塞程度,而增加反向弧的容量不仅不能改善网络的堵塞,有时甚至会使最小饱和流减少。

有向网络中无环最小饱和流问题及其算法

假设网络的初始流为零流,以最大堵塞截面为准堵塞截面,找出从源点到汇点的包含准堵塞截面弧最多的有条件最长增广路对网络进行增流,直至网络达到饱和,并对该算法进行了复杂性分析。利用该算法对多个网络进行论证,结果表明利用有条件最长增广路算法计算出的最小饱和流值与仿真计算以及与双向增流算法计算得到的结果基本相同,增流次数大大减少,且求解的结果避免了在封闭环路中的流量流动,进一步优化了最小饱和流值。

最小饱和流问题的多项式时间可解变形(英文)

最小饱和流问题就是求具有最小值的饱和流.此问题起源于紧急疏散和交通阻塞的研究,并且已知是一个NP-困难问题.本文探讨两个特殊情形:一个限定问题是寻求给定截集的最小饱和流,一个松弛问题是寻求最小双向容量截集.对于前者,通过构造一个辅助网络AN(S)及运用最大流算法,建立一个多项式时间算法,并证明其复杂性是O(n3).对于后者,通过构造一个单向网络N′,将问题转化为一个最小容量截问题.但是这个新网络N′可能包含负容量的弧,一般不易求解.当单向网络N′是平面网络时,我们建立了多项式时间算法.

运输网络中最小饱和流的求解

运输网络中常常由于流量的不可控易发生堵塞现象.网络发生堵塞时的饱和流值达不到最大流值.最小饱和流是运输网络,尤其是紧急疏散网络设计中很重要的一个参数.通过建立网络的割集矩阵来确定网络的堵塞截面,基于此提出了求解最小饱和流的线性规划模型及算法.举例分析表明,利用该算法计算网络最小饱和流更加简便、更加实用.

求解最小费用饱和流问题的一种全局优化算法

将费用权值引入饱和流问题中,提出带费用权值的饱和流概念.通过建立相应的数学模型,将其转化为有效集上的优化问题,并借助一种改进的全局优化算法来求解.

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

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

紧急疏散网络防堵塞改造研究

紧急疏散网络中由于流动单元流动方向的不受控制,网络易发生堵塞,此时的饱和流值达不到理论最大流值.如何改善紧急疏散网络中的堵塞现象,以尽可能少的费用来改造流通网络,关键是尽可能地使网络中的各点容差不小于零,以消除或减少网络的结构堵塞点.基于此提出了网络中边容量有上限的防堵塞的最小费用改造模型;并在此模型基础上讨论了改造费用取值不同时的应用.举例分析表明,该模型可有效地解决紧急疏散网络中的堵塞现象.

银河杜仲沼液种植3层目标轮换6级储存网络系统设计

由农村沼气工程引起的规模养殖沼液二次污染问题是当前农村环境污染治理的重点问题,也是牵制农业产业化发展,影响中国特色农业现代化道路的关键矛盾。运用最大流和最小饱和流理论,以消除江西银河杜仲绿色规模养殖基地的二次污染为研究对象,对沼液输送浇灌净化工艺流程进行了3层6级储存网络设计分析,给出了解决规模养殖沼液二次污染矛盾,实现沼液零污染最小排量问题的有效方法。

城市街道网单行道改造方案的评估

城市里随着汽车保有量的高速增长,交通日益拥挤,街道网的改造已势在必行,目前单行道改造是国内外常采用的方法。着重研究对n_1,n_2小的呈网格状的有n_1+1条东西向街道和n_2+1条南北向街道的城市道路网的单行道改造。由于网络中流动单元的随机流动,各端点之间的饱和流呈多值分布,最小饱和流发生在堵塞最严重的情况,改善网络的最小饱和流可以提高网络在堵塞最严重时的通行能力。基于网络中两端点之间的期望流通值和随机饱和流的偏方差值两个指标函数,建立了基于多重目标的评估模型以找出最佳改造方案。通过对实例的仿真研究证明了这种评估方法的有效性。