有向网络的最小流问题及其分枝定界解法

在以人为运动主体的交通网络中，堵塞是经济发生的现象。本文研究的网络最小流是指网络中发生最严重堵塞状态时通过网络的最大流量，它是设计和运行效能网络，特别是紧急疏散网络的参数。     

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

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

在网络中寻找最小树形图的简易算法

研究网络中支撑树形图的的性质，提出了在网络图中寻找最小树形图的简易算法，并对算法的复杂性进行了讨论，还给出应用该算法进行计算的一个实际算例。     

基于网络流矩阵求解网络最大流

通过建立网络流矩阵及相关概念，研究其性质，从理论上提出了基于网络流矩阵的最大流求解方法，并且给出了严格的数学证明和具体步骤。主要采用了节点流量平衡、转化为矩阵、矩阵降阶的思想。这些思想的应用具有重要的理论意义，同时也为研究最小费用最大流问题开辟了新途径，和其它方法比较，本文的方法具有操作简单、易于实现等优点。     

网络最大流的割集矩阵算法

利用网络单位流量及网络可行流的流量平衡关系,得出流量关系矩阵,由流量关系矩阵,得出网络割矩阵,从而求出网络图的割集,最后根据网络最大流等于最小割容量,求得网络最大流,此方法使得计算网络最大流变得简便,且具有很强的实用性.     

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

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

最小费用流的灵敏度分析

最小费用流的灵敏度分析林景荣（广东民族学院，广州５１０６３３）ＳｅｎｓｉｔｉｖｉｔｙＡｎａｌｙｓｉｓｏｎＭｉｎｉｍｕｍＣｏｓｔＣｉｒｃｕｌａｔｉｏｎＬｉｎＪｉｎｇｒｏｎｇ（ＧｕａｎｇｄｏｎｇＩｎｓｔｉｔｕｔｅｆｏｒＮａｔｉｏｎａｌｉｔｉｅｓ）Ａｂｓｔ...     

基于最小生成树的LAPLACE谱图像匹配算法

提出了一种基于最小生成树的Laplace谱图像匹配算法.首先分别对两幅待匹配图像的特征点集构造完全图,其次寻找最小生成树,然后通过各自的最小生成树构造Laplace矩阵,接下来进行分解并利用分解结果构造匹配矩阵,最后通过匹配矩阵实现两幅图像匹配.实验验证了该算法能够降低匹配的时间复杂度和获得较高的匹配精度.     

基于偏最小二乘回归的基因网络数学建模

对基因表达数据进行数学建模是理论系统生物学的一个热点,其难点之一在于数据的小样本特性、多重相关性及粗糙性.针对基因表达数据的这些特点,偏最小二乘回归被首次引入基因网络的数学建模领域,通过轮换计算将变量投影重要性指标拓展为VIP矩阵,建立了基因网络模型:经验证所构建的网络具有生物学意义,运用图论分析可证实其符合无尺度网络的特性,从而证明了这种建模方法的可行性.     

求最小费用最大流的改进标号法

针对现有网络最小费用最大流算法存在的针对性差、步骤繁复、计算量大的问题,根据赋权有向图的最短路算法,提出并证明了一种寻找最小费用增广链的改进标号法.此方法可以直接在网络图上使用,避免了传统方法中需要反复将网络图转化为赋权有向图的操作.将此方法应用到求网络最小费用最大流的计算中,可以简化计算过程,提高运算效率.     

多车场满载货运车辆优化调度的网络流算法

探讨在一般条件下的多车场满载的VSP问题。建立了它的网络流模型，并给出了一个基于该网络流最优解的启发式算法。该算法的一个明显特征是，对每一条行车路线的确定总是基于一修改后的网络流模型的最优解，大大提高了算法结果的优化质量。同时，与其它同类算法相比，其算法设计也明显偏优。     

唯网络流论

本文建立了基于网络流的ＯＤ矩阵预测模型，主要内容是：１、建立由现状网络流生成的ＯＤ矩阵，否定现状ＯＤ调查的必要性。２、按经济为交通的“源需求”思路，建立由经济变量为主导的趋势型ＯＤ矩阵预测模型。３、为发挥“交通反馈效应”的思路，建立了诱增型ＯＤ矩阵预测模型。４、依配流理论，完成网络流的趋势预测和诱增预测。     

基于最少换乘的公交系统网络配流模型及算法

公交网络配流有平衡配流模型和非平衡配流模型,两者各有适用范围。根据乘客选择乘车路径的心理特征,分析了最少换乘下的路径选择和阻抗计算,然后根据Logit模型提出了公交网络配流的非平衡模型和算法。最后给出具体算例得到了每一路公交车的OD矩阵,计算速度较快,可适用于大型网络。     

求解度约束最小生成树的单亲遗传算法

提出了求解度约束最小生成树问题的单亲遗传算法.该算法首先利用Prufer数对生成树进行编码;然后精心地设计了一个随机地产生初始种群的方法,用这种方法产生的初始种群,不会含有任何不可行解;在遗传操作中只使用选择和变异操作,共设计了三种变异操作,其中两种变异操作均不会产生不可行解,只有一种变异操作可能会产生不可行解,需要作树的度的检查和修改;这样就大大的降低了不可行解产生的机会,从而提高了遗传算法的效率;而且只使用变异算子,有效的避免了早熟收敛现象的产生;通过大量的数值试验,表明该算法简单,高效,收敛率高;最后对此算法做了适当推广,并给出了它求解TSP问题的具体步骤和实例。     

基于d-最小割集的多状态网络可靠度矩阵分解算法

鉴于基于d-最小割集应用容斥原理计算多状态网络可靠度精确值的复杂性, 借鉴分解的思想, 基于事件并运算之间的吸收律, 通过定义d-最小割集矩阵及矩阵概率, 提出了一种矩阵分解算法. 算法的基础是在一定规则下反复对矩阵进行分解、简化, 并通过迭代计算矩阵概率得到可靠度精确值. 同时, 通过定义删除函数以及动态选择分解边加速分解过程. 相关分析表明算法的复杂度随网络中边的数目成指数增加. 算例分析表明算法计算结果正确, 且结构清晰、易于实现, 验证了其正确性和有效性.     

最小费用流在商品购运销中的应用

本文力图用网络技术中的最小费用流理论解决商品流通企业降低其商品购、运、销中的成本问题。     

无线感知网络最小二乘法定位算法的误差分析与优化

无线感知网络(WSN,wireless sensor networks)中位置信息及其位置可信度对于感知数据至关重要,目前针对WSN定位的可信度分析很少见.利用误差分析理论对最常用的最小二乘法定位算法进行理论分析,并提出一种简化误差分析算法,在给出节点预测位置同时给出定位误差范围;而且,利用误差分析对循环定位的锚点选择进行优化,能够显著提高定位精度;最后,采用模拟试验的方法对误差分析及其简化算法和优化算法的有效性进行验证.     

利用极小割计算随机流网络可靠度的一种算法

对随机流网络可靠度的计算问题进行了研究.提出了网络元件(边和结点)容量下确界的概念,在求基于每个极小割集的每个元件的容量向量时,对其满足的约束条件进行了改进,使其可行解集合大大减小.同时给出了两个引理,根据这两个引理,使得求基于极小割集的所有d-上界点变得非常简单,从而得到了一个计算随机流网络最大流量不少于给定需求流量d+1的可靠度的有效算法.最后,通过实例验证了该方法的有效性.