无回路网络中的最小费用流算法

针对无回路网络的特殊性,利用广探法的思想,提出了无回路网络最短路的有效算法,并在此基础之上提出了最小费用流的有效算法.其算法的复杂性分别为o(m)和o(mvo),相比拓扑排序法和最小费用路算法,本文提出的算法更为简练、易懂且复杂性低.     

点和边有容量约束的网络最小费用最大流算法*

分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明：点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。     

最小费用最大流

针对当前很多最小费用最大流算法存在的问题和缺陷,用实例做出修正和完善.     

最小费用流算法的图象重建

本文提中一种最小费用流算法,实现从两个正交的一维投影重建图象。该方法在寻找增值链的过程中,为网络各节点设置状态变量,用以记录当前增值链通过该节点允许的最大费用值,使算法只搜索可能增流的节点,从而提高了图象重建效率.该方法已成功地应用于医学同位素扫描图象的重建.     

基于最小费用最大流问题的“排序”算法

由于现有的求解最小费用最大流问题的方法都存在其局限性,为了更好地解决实际问题,在已有最短路算法以及最小费用算法的基础上作了改进,给出了一种求解基于最大流的最小费用问题的算法.文中针对小规模网络给出求两点之间最小费用的一种简单易行的方法,此外该算法可以在一个图上完成,这样可以节省许多画图时间,增强了算法的直观性和可控性.并且构建石油运输的网络模型,结合最小费用最大流算法,给出该模型从产地到销地的最优运输方案,最后通过具体的模型实例验证了该方法的效率和实用性.     

支持快速扩散制造的制造资源配置平台研究*

在分析国内外网络化制造研究成果的基础上,结合武器装备快速变批量生产的需求,对武器装备快速扩散制造的概念和特征进行了介绍,并给出满足快速扩散制造要求的制造资源内涵及其概念模型。为了达到短时间内快速组织制造资源进行生产的目标,本着利用外部资源、使用内部技术的原则,提出了面向快速扩散制造的制造资源配置平台解决思路,并提炼出制造资源配置平台的体系结构和若干关键技术,从而实现问题研究范围的界定。     

求解最小费用最大流的新方法

文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性     

基于最小费用最大流的MANET网络路由能量控制模型

MANET是当前无线网络研究的热点领域,作为网络层核心技术的路由协议显得尤为重要。控制节点能量、提高网络生存时间是实现在MANET中传输高效业务的关键。本文借鉴网络最小费用最大流思想,建立网络最大剩余能量最短路数学模型,提出了基于能量控制的网络路由优化模型。并且定义了网络生存时间作为评价指标,进行网络仿真。仿真结果表明,该模型可以有效地延长网络生存时间。     

最小费用最大流算法(C++)实现

最小费用最大流是一类网络优化问题,它与最大流的区别在于,它不仅要考虑流量问题,还要考虑费用因素,其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算,提高工作效率,因而它在信息学竞赛,国际信息学竞赛,大学生数学建模比赛等方面都能得到应用。     

最小费用最大流问题的一种新算法

现有的最小费用最大流算法都有自身的缺陷,增广链的选取不当会给计算带来不便,同时费用也达不到理想的效果。鉴于对最小费用最大流算法的增广链选取和最小费用的探索,文章通过对费用差的定义给出了一种求最小费用最大流的新算法。新算法的原则是优先选择费用差最小的有向路径进行增广,当费用差相同时就选择修正后的路径。通过对最小费用最大流算法的改进,新算法易理解且便于计算。通过实例说明了新算法的有效性和执行效率。     

基于边缘节点的深度神经网络任务分配方法

随着边缘计算的发展,边缘节点的计算规模不断增加,现有的边缘设备难以搭载深度神经网络模型,网络通信与云端服务器承受着巨大压力。为解决上述问题,通过对Roofline模型进行改进,借助新模型对边缘设备的性能与网络环境进行动态评估。根据评估指标,对神经网络模型进行分离式拆分,部分计算任务分配给边缘节点完成,云端服务器结合节点返回数据完成其它任务。该方法基于节点自身性能与网络环境,进行动态任务分配,具有一定兼容性与鲁棒性。实验结果表明,基于边缘节点的深度神经网络任务分配方法可在不同环境中利用设备的闲置性能,大幅度降低中心服务器的计算负载。     

求解最小费用最大流问题的信念传播算法

最小费用最大流问题是一种组合优化问题,在经济、工业等领域具有重要研究意义和应用价值.针对部分最小费用最大流问题求解算法效率较低的情况,依据最小费用最大流问题的线性规划方程,将问题模型映射为对应因子图模型,改进描述函数,给出迭代方程,设计了求解最小费用最大流问题的信念传播算法.利用迭代方程优先对最大可行流特征值进行收敛计算,得到最大流,设置最大流阈值,在此基础上进行最小费用计算,从而求得问题最优解.最后选取若干带权有向图模型进行数值实验,验证了算法的可行性及有效性,且算法在求解效率上优于部分算法.     

海流环境下多AUV多目标生物启发任务分配与路径规划算法

针对多障碍物海流环境下多自治水下机器人(AUV)目标任务分配与路径规划问题, 本文在栅格地图构建的 基础上给出了一种基于生物启发神经网络(BINN)模型的新型自主任务分配与路径规划算法, 并考虑海流对路径规 划的影响. 首先建立BINN模型, 利用此模型表示AUV的工作环境, 神经网络中的每一个神经元与栅格地图中的位 置单元一一对应; 接着, 比较每个目标物在BINN地图中所有AUV的活性值, 并选取活性值最大的AUV作为它的获 胜AUV, 实现多AUV任务分配; 最后, 考虑常值海流影响, 根据矢量合成算法确定AUV实际的航行方向, 实现AUV路 径规划与安全避障. 海流环境下仿真实验结果表明了生物启发模型在多AUV水下任务分配与路径规划中的有效性.     

改进粒子群优化算法求解任务指派问题

任务指派问题是典型NP难题,引入粒子群优化算法对其进行求解。建立了任务指派问题的数学模型,给出了粒子群优化算法求解任务指派问题的具体方案。为提高其优化求解效果,引入变异机制及局部更新机制对粒子群优化算法进行改进。实例及数字仿真验证了改进粒子群优化算法的有效性。     

基于网络演算的智能交通流量分配研究

精确的交通流量分配计算模型,能为实际的交通工程应用提供具体的流量出入速率或者信号灯控制时间方案,具有重大价值。首次将动态交通流量分配拟化为网络负载均衡问题,使用漏桶理论和网络演算方法,将交通的流量分配与路径时延转换为一系列极值运算,结合贪婪算法,以均衡网络延时为优化目标,得到交通配流。仿真结果表明,本模型在化解拥堵的同时,使分流后的道路平均延时普遍降低,能提升整体路网的通行能力。     

基于流网络的流式计算动态任务调度策略

针对大数据流式计算平台中输入数据流速急剧上升所导致的计算延迟升高问题,提出了基于流网络模型的动态调度策略,并将其应用于Flink数据流计算平台。首先,通过定义有向无环图（DAG）中每条边的容量和流量将其转化为流网络模型,并通过容量检测算法确定每条边的容量值;然后,通过最大流算法计算对应的增进网络和优化路径,从而在输入速率上升阶段提升集群的吞吐量,并通过评估时空代价论证了算法的可行性;最后,讨论了重要参数对算法执行效果的影响,并通过实验得出了在不同类型的作业中推荐的参数取值。经实验验证得出：所提算法与Flink平台现有的任务调度策略相比,在输入速率上升阶段对不同作业类型中集群吞吐量的优化比均高于16.12%。实验结果表明动态调度策略在满足任务延迟约束的前提下有效提高了集群的吞吐量。     

最小总风险准则的贝叶斯网络个人信用评估模型*

将最小总风险准则MOR与贝叶斯网络分类器相结合,提出了一种新型信用评估模型。在两个真实数据集上以MOR用10层交叉验证对贝叶斯网络信用评估模型进行了测试,并与最小错误概率准则MPE的贝叶斯网络分类器的结果进行了对比。结果表明,基于MOR的贝叶斯网络分类模型可以有效地减小信用评估风险。     

Polynomial-time primal simplex algorithms for the minimum cost network flow problem

We present two variants of the primal network simplex algorithm which solve the minimum cost network flow problem in at mostO(n ² logn) pivots. Here we define the network simplex method as a method which proceeds from basis tree to adjacent basis tree regardless of the change in objective function value; i.e., the objective function is allowed to increase on some iterations. The first method is an extension of theminimum mean augmenting cycle-canceling method of Goldberg and Tarjan. The second method is a combination of a cost-scaling technique and a primal network simplex method for the maximum flow problem. We also show that the diameter of the primal network flow polytope is at mostn ² m.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402 and ONR Contract N00014-87-K0214.     

基于客流分配的高铁票价调整策略

针对目前高铁票价单一、客运收益率低、区段客流不均衡等问题,提出基于客流分配的高铁票价调整策略。首先,分析影响旅客出行选择行为的相关因素,构建包含经济性、快速性、便捷性和舒适性四项指标的广义出行费用函数;然后,建立兼顾高铁客运管理部门收益最大化和旅客出行费用最小化的双层规划模型,其中上层规划通过制定票价调整策略实现高铁客运收益最大化,下层规划以旅客广义出行费用最小为目标,利用区段不同车次间的竞合关系构建随机用户均衡（SUE）分配模型,同时采用基于改进Logit分配模型的相继平均法（MSA）进行求解;最后,结合案例验证了所提票价调整策略能够有效地平衡区段客流,降低旅客出行成本并在一定程度上提高客运收益。结果分析表明该票价调整策略能够为铁路客运管理部门优化票价体系、制定票价调整方案提供决策支持与方法指导。     

Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.