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

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

最小费用流的直接优化

研究了广义最小费用流问题，给出并证明了最小费用流的直接优化原理，构造了直接优化算法．数据实例表明，直接优化算法不仅有效而且可以弥补ＯＫＡ（Ｏｕｔ－ｏｆ－ＫｉｌｔｅｒＡｌｇｏｒｉｔｈｍ）算法的缺陷，并能解决网络流规划的其他类型的问题．     

动态网络中最大流快速增量求解

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.     

位势法在交通优化问题中的应用

研究了单源多汇交通优化问题及其重要性质,提出了单源多汇交通优化问题的位势法,该算法以关于费用的最短路程为初始势,以非零流的最小费用流为初始流;用标号法找可行的增广链,在标号过程中若某点不满足平衡要求则由到达该点的可行的增广链增广最小费用流的流量;以弧割为工具,计算最小费用流的势的最大调整量,并修改最小费用流的势.算例证明了算法的正确性和复杂性及算法的有效性.     

网络图任意两点间最短路径问题的计算机实现

最短路径问题是网络分析中的一个最基本的问题,著名的旅行推销员问题,中国邮路问题,运输网络的最小费用最大流问题及最小根树问题等都建立在此问题的基础上。本文用集合并的思想解决了Floyd算法中路径寻求在计算机上实现的问题,并给出了负回路的判别方法,从而也解决了中国邮路、旅行推销员等相关问题的计算机实现问题。     

带循环时间窗口的独立路径配送问题

通过优化物流的配送运输网络,可以有效降低配送成本.带循环时间窗口的独立路径配送问题实际是车辆路径优化问题,属于NP-hard问题类.定义了循环时间窗口,并设计了图形预处理算法,通过建立有向赋权网络上带循环时间窗口的物流配送问题的数学模型,构造有向网络赋权辅助图,在辅助图上采用最大流的Ford-Fulkerson算法来解决弧独立路径问题,判断问题是否有解,之后用最小费用流的最小费用路算法来求权值和最小的R条弧独立路径,得到该问题的一个最优算法,为物流配送环节提供新思路.     

试论物流系统的网络模式

1 物流的网络概念 从系统论的整体观念来看,可以将物流系统看作网络结构来进行研究,用流和积累等流机理来进一步掌握和控制网络。这种网络结构一般至少有一个源(发点,如油井、油库、车站、港口和计算中心的处理机等)和一个汇(收点,如炼油厂、另一个输送站和计算机通道等),网络中有多条支路,各支路的交点称为网络节点(如输油线上的阀门,计算机系统中的门电路等),每一对收发点间都有许多带方向的动态连线,以表示两点间的运动路线。相对静止的节点和动态的连线,构成一个系统网络。     

最小费用流的直接优化

研究了广义最小费用流问题，给出并证明了最小费用流的直接优化算法。数据裕列表明，直接优化算法不仅有效而且可以弥补ＯＫＡ算法的缺陷，并能解决网络流规划的其他类型的问题。     

非线性最小费用网络流新算法及其应用

本文提出了新的非线性最小费用网络流的最优性定理和相应的算法，建立了适用于梯级水电站群短期经济调度的计算网络模型，给出了适于求解这个模型的最小费用增广路径和最大费用减广路径的算法。应用本文提出的理论和算法进行梯级水电站群短期经济调度计算，计算速度有明显提高，优化结果也更为精确。     

并行蒸发器两相冷却系统支路散热不平衡性的实验研究

 对并行蒸发器机械泵驱动两相流冷却系统各个支路散热量不平衡条件下散热特性进行实验研究,结果表明并行蒸发段各支路的流量分配同管路的阻力有关,当上下两侧蒸发器的热量不平衡时,质量流量的分配始终是一个动态的变化过程,其中,热负荷较大的一侧,阻力不断增加,流量逐渐减小,而热负荷较小的一侧流量在不断变大,并且热量差越大,流量差变化越快;当减小并行支路的热量差有利于蒸发段的散热平衡,热量差越小,系统散热稳定性越强。同毛细泵驱动的两相冷却系统相比,机械泵驱动的两相流冷却系统的散热性好,等温性高,热不平衡处理能力强,并行支路热负荷之差可以达到100多倍,并且能够保持较长的稳定运行。     

总流量可变的最小费用流问题及其求解

讨论在总流量可变动的情况下，网络最小费用流问题的解法。分别就单源单汇和多源多汇情况构造不同的辅助网络，将原网络中的最小费用流问题转化为辅助网络中的最小费用循环流问题，然后用瑕疵算法求最小费用循环流问题的最优解，这样在求出原网络中最小费用流的同时，也获得了总流量的最优取值。     

卷烟机风力送丝系统管网结构的稳定性分析

针对卷烟厂中“集束式”、“鱼刺状”两种不同管网结构形式的风力送丝系统,根据卷烟机工艺特性,采用关闭某个或某些支路来模拟系统送丝状态和改变某支路阻抗大小来模拟系统送丝过程.运用MATLAB网络解算工具,计算出所有工况下送丝支路的流量偏离系数,分析比较两种管网系统的稳定性.结果表明:集束式系统的稳定性优于鱼刺状系统.变工况运行条件下,集束式系统中阻抗越小的支路对系统稳定性的影响越大.而鱼刺状系统中距离安装有风机的主管段越近的支路稳定性越好.     

关于节点分析法的新思考

针对“节点分析法”分析电路时，由于有些特殊情况要作特殊处理，往往给分析电路带来极大的不便。在此提出，先把各支路划分为含源支路和无源支路，再分别处理的新思路，使规律更明显，尤其有利于编制程序用计算机解题     

活动网络时间费用优化的截集算法

从活动网络中建立了流量网络，通过找出流量网络的最小载集及反截集。给出了活动网络时间费用优化算法，本文的算法比例举法更有效，比线性规划法更方便。     

关于网孔方程的独立性

一个具有n个节点、b条支路的复杂网络,用基尔霍夫定律求解时,可以列出n-1个独立节点方程和m=b-n+1个独立口路方程。关于独立回路的选取,一个最普遍的方法是“新选定的回路中,至少有一段电路是在已选过的回路中未曾出现过的”;再就是“在所给网络任选一个树后,所有的单连支回路就是一组恰当的独立回路。”但“对于平面网络,则全部网孔就构成一组独立回路。”用前两种方法选取回路的独     

一种基于最小费用最大流理论的Ad hoc路由协议

针对Ad hoc网络QoS路由问题,提出了一种基于最小费用最大流理论的Ad hoc路由协议(MCMFP)。将Ad hoc的移动终端作为网络节点,通信链路作为相邻节点之间的边,建立了Ad hoc网络的网络流模型,使Ad hoc网络的路由计算问题转化为图论中的最小费用最大流问题,从而计算出满足多QoS约束的路由路径,优化了网络带宽的使用,提高了通信信道的利用率,实现了网络流量的负载均衡。仿真结果表明,MCMFP协议具有更高的包转发率和更小的平均时延,有效提高了Adhoc网络的QoS性能。     

具有线性路阻函数的路径流量分配效率

用户均衡和系统最优是两种最基本的流量分配方式,前者是用户出行时追求费用最小,而不考虑其他用户如何选择路径;后者是对所有用户进行管制,追求网络上总费用最小。针对系统最优时部分路径上费用过大的问题,讨论了路阻函数为线性时,同一路径上两种不同分配方式费用的大小关系;同时,定义了重载路径和轻载路径,并给出两种路径的判别方法。     

最小费用最大流理论在传输电压中的应用

用电力电缆来传输电压,而电力电缆线自身需要费用,同时电力电缆有一定的载流量.电压传输可以刻画为网络模型,它的最小费用问题相当于电力电缆长度最短同时电力电缆的载流量最大的问题;运用图论中的Dijkstra算法和Ford-Fulkerson算法来解决电压传输的最小费用问题.     

S-粗集和它的一般结构

给出论域U上元素迁移F，F，单向奇异集合，双向奇异集合的概念；利用这些概念，提出奇异粗集，简称S－粗集，给出S－粗集的数学结构，S－粗集的存在背景和意义解释。S－粗集包含两种结构：单向S－粗集，双向S－粗集；S－粗集是研究系统动态近似特性，知识挖掘，知识发现的一个新的理论工具。     

复杂路网下多客户间最短路径的扇面Dijkstra算法

复杂路网模型下多客户之间最短路径的计算,直接影响市区集送货问题的求解效率。该文提出多客户间最短路径扇面Dijkstra算法。该算法首先由客户在路网的分布确定出最小扇形区域及扇面搜索区域,并将路网节点分为拓展点集、邻节点集。然后在搜索过程中通过优化到达邻节点的通行代价来确定新的拓展点集、邻节点集。算法通过限制搜索区域、减少遍历节点的数量来缩短搜索时间。100个分布于北京市的客户间最短路径的计算表明,相对于Dijkstra算法,扇面Dijkstra算法能够在保证精度的前提下,降低15%的最短路径求解时间。