最小费用最大流模型在航班衔接问题中的应用

针对单枢纽航线网络的特点 ,以所需飞机数最少 ,航班在枢纽机场的过站衔接最紧凑为目标 ,提出了描述航班衔接问题的最小费用最大流网络模型 :首先将航班衔接问题转化为航班节的衔接问题并以各航班节在枢纽机场的到港、离港时刻为结点 ,建立了一个描述航班节衔接问题的单源汇网络 ,从而将航班衔接问题转化为该单源汇网络的最小费用最大流问题。利用 dijkstra算法求该网络的最小费用最大流进而得到了一个需用飞机数最少 ,且过站衔接最紧凑的航班节衔接方案 。

灾害事件下局域路网应急疏散交通分配模型

应急疏散的目的是要在灾害发生时将处于危险地带的人群尽快转移至安全地带。针对不同灾害事件类型而引发的单源单汇、单(多)源多汇网络状态的路网疏散问题分别进行了分析。在各路段通行能力的约束条件下,以疏散交通流量最大、总疏散时间最小为优化目标,运用最小费用最大流理论建立了局域路网疏散分配模型。通过实例对模型进行了求解,并在Matlab中得到了实现。通过查找最小截量组成弧的分布位置,并对路网中最小截量组成弧的路段扩容改造,进而有效提高局域路网的应急疏散能力。

DVD租赁问题的模型设计及求解

本文讨论了DVD在线租赁的服务供应商可能遇到的问题与其解决方案。模型Ⅱ解决了在已知订单与各种DVD数量的情况下,如何分配DVD使得满意的人数最多,且总的满意度最大。模型Ⅲ解决了在已知订单的情况下,在一定的满意率与总满意度最大的约束下,如何以最小的成本购买各种DVD,并确定分配方案。模型V对原问题作了更深入的推广,解决了在DVD数量有限且租赁费用与租赁时间成正比的条件下如何选择性地出租DVD以获得最大收入的问题。本文所讨论的问题均为最优化问题,但是各题的约束条件均不相同。本文对各个问题建立不同的网络模型,经过严密的理论论证,并用统一的费用流算法在微机上实现,充分利用了网络流模型适用面广,结果精确,计算简单的优点,对DVD租赁的现实问题提供了高效的解决方案。

低地球轨道卫星网络节能方法

通常卫星的唯一能源来源是太阳能,因此星上网络设备的能源供应问题比地面网络的更加严峻。通过修改和扩展链路容量受限的最小代价多商品流模型来适应卫星网络这一特殊的体系结构,并基于低轨道卫星网络的多重覆盖机制和流量分布模型,改进现有的启发式算法来关闭冗余的卫星节点、星地链路和星间链路。在满足链路利用率和路由跳数增加比例约束的条件下,仿真实验中关闭上述三种参数的比例分别可达59%、61%和72%,卫星网络的总体节能比例可达65%。

求解广义优先关系下的项目最小费用问题

在项目调度中,求解与费用相关的问题时,需要先求得项目的最小费用,然后以此为起点进行优化,例如时间―费用权衡问题.当工序之间只存在单一优先关系时,各工序只需选用费用最小的工期就能得到项目最小费用.但是当工序之间存在广义优先关系(GPRs)时,各工序若都选用费用最小的工期通常无法满足既定的优先关系,导致项目不可行.针对GPRs下的项目最小费用问题,首先,通过分析GPRs的特点,建立了其数学模型;其次,对该模型进行对偶变换,将其等效转化为特殊的最小费用最大流模型.该模型能够运用现有算法求解,并跟据初始―对偶关系求得GPRs下的项目最小费用.

应用最小费用流求解活动网络时间-费用模型

提出了利用最小费用流原理求解时间-费用优化模型的方法.应用对偶理论将费用-优化模型转换为适用于状态算法求解的最小费用流问题,采用互补松弛定理和状态算法推出了由对偶问题最优解求出原问题最优解的等式,以一个实例说明了利用上述方法求解时间-费用优化模型最优解的步骤.所提出的求解时间-费用优化模型的算法,提高了求解问题的效率,可用于大型工程网络的费用优化.

电子易货资源匹配模型研究

针对电子易货市场资源匹配问题,通过系统分析易货市场中资源分类情况以及匹配的目标要求,得到资源匹配的数学模型;运用网络流理论对问题模型进行转化,把资源匹配数量最大的目标转换成有流量限制的网络最小费用流问题,依此建立网络模型;最后,以制造业和服务业之间的易货进行案例分析建模,用winQSB软件求解验证。结果表明,该模型的应用提高了易货资源匹配的运算效率和准确性。

具有运输次序的运输问题研究

研究了一类新的运输问题———具有运输次序的运输问题,建立了这类运输问题的网络流模型,证明了该模型的有效性,根据解最小费用流问题的思路设计出求解该模型的实用算法,同时通过定义修正权将负权转化为非负权,从而可以用Dijkstra算法找最短路,使算法得到改进。

海底油气集输系统网络流规划模型设计

利用图论和网络流规划的有关理论对海底油气集输管网系统进行了分析,建立了海底管道网络的非线性规划模型,并利用非线性费用函数线性化的处理方法,将网络中每段凹费用弧分段线性近似地表示,通过求网络最小费用流问题的方法,对海底管道网络进行了分析和研究。

电商企业应急物流中的商品运输规划模型

借鉴应急物流研究中运输优化的思路,采用最小费用最大流理论,建立了企业应急物流中商品运输模型,得出了在满足企业各配送点最小商品需求的前提下,以最低的运输费用将商品运送到各配送中心的运输方案,并给出了相应的求解方法。

基于网络流的含分布式电源配电网两阶段规划

针对含分布式电源(DG)的配电网规划问题,利用图论的思想,建立以规划年费用最小为目标的含分布式电源配电网规划图模型,提出两阶段的启发式算法,实现优化分布式电源的接入位置、接入容量、实际接入量及变电站和配电线路的新建或者升级改造等综合优化。第一阶段,对所建的图模型应用多重局部搜索算法确定分布式电源的接入位置、接入容量及变电站和配电线路的新建或者升级改造决策;第二阶段,利用第一阶段优化得到的线路、电源参数,建立精确的数学模型,并运用遗传算法确定分布式电源的实际接入量。33节点典型系统算例证明了该算法在含分布式电源配电网规划中应用的可行性和有效性。

关于多收点容量网络最小费用流的一个问题

对多收点容量网络最小费用流问题，证明了当收点处的净流入量增加时。

危险天气下航路网络流可靠性的动态管理

为缓解危险天气对繁忙机场造成的空域压力,对空中交通可靠性管理的预分流问题展开研究。针对危险天气随机性变化的问题,提出了航路可靠性的度量方法,并通过数学变换将航空危险天气的随机性转化为航路网络的阻抗;根据管制实际运行条件改进了最小费用最大流模型,提出了一种考虑航路阻抗随天气动态变化、航路容量约束和管制员负荷约束的可靠性数学模型。以华北管制区的部分空域为例进行仿真分析,结果表明:该方法对流量大的机场优化效果明显,北京首都国际机场的飞机离场延误降低12.44%,天津滨海机场的离场延误降低11.98%。

考虑交叉口冲突点延误的交通紧急疏散

提出了一个考虑交叉口冲突点延误的疏散路径模型,用"当量费用"来表述交叉口冲突点延误;寻求使冲突点延误与疏散车辆行驶费用二者总费用最小的最优疏散路线;通过改进的最小费用流算法求解此模型,并以一个算例给出了算法的具体应用.

杂波信息未知下的多群目标跟踪算法

针对杂波先验信息未知且群结构可能发生分裂和合并条件下的基于随机矩阵的多群目标跟踪问题,提出基于网络流理论的多群目标跟踪算法。首先建立椭圆轮廓且群结构发生分裂和合并的多群目标运动模型,再根据Pauta准则对包含目标点与杂波的量测集进行处理,消除异常值,利用自适应谱聚类算法对处理后的量测集进行分割,获得单位时间内多个群目标的数目。结合量测分割结果,构建基于随机矩阵的多群目标网络流模型,设计多约束条件下的最小费用优化函数,运用A*搜索算法求得目标函数的全局最优解。最后根据指向⁃隐含速度约束条件得到最优关联航迹。仿真结果表明,与GM⁃GPHD滤波器相比,所提算法可准确地提取多条航迹并具有较低的计算复杂度以及更好的跟踪性能。

楼宇用户基于移动人流量的需求响应管理模型

通过考虑建筑热储存的特性,可根据不同的价格对中央空调系统和新风系统进行需求响应调节,模拟考虑移动人流量的不确定性对楼宇需求响应的影响具有重要意义。对楼宇内所有系统以及移动人流量进行数学建模,该文对考虑移动人流量和不考虑移动人流量两种情况分别分析,采用YALMIP调用CPLEX进行优化求解。以某机场候车厅为例对所提的方法进行分析说明,通过对比两种结果得出移动人流量对楼宇内用电影响较大。得出在人流量较大的商业楼宇等公共场所内,因为人流量对空调制冷有一定的影响,所以考虑人流量并对负荷做出预测具有实际意义。

融合目标相似性和作用力的多目标跟踪

目的多目标跟踪是计算机视觉一个重要的研究方向,为了解决多目标跟踪中错跟和漏跟导致跟踪精度低的问题,提出一种融合目标相似性和作用力的多目标跟踪算法。方法首先将多目标跟踪问题转化为一个最大后验概率问题,其次将最大后验概率问题映射到网络流中,利用最小代价流寻找最优路径,这样获得的最优路径就是目标轨迹。为了计算网络流中目标节点之间的代价,从以下两方面考虑:1)将目标的外观、运动和位置信息三者结合,计算目标间的相似度;2)考虑目标与目标的相互影响,参考社会力模型中个体之间的吸引力来计算目标节点之间的作用力。结果在MOT15、MOT16和MOT17共3个公开数据集进行实验评估并与12种方法进行比较,实验结果表明,本文算法在MOTA (multiple object tracking accuracy)、MT (mostly tracked tracklets)、ML (mostly lost tracklets)、FP (false positives)、FN (false negatives)等指标上明显优于OACDASM (online association by continuous-discrete appearance similarity measurement)、STURE (spatial-temporal mutual representation learning)、IQHMOT (identityquantity harmonic multi-object tracking)和GCNNMatch (graph convolutional neural network match)等典型算法。在MOT15数据集中选取ETH-Bahnhof、TUD-Stadtmitte与PETS09-S2L1 3个视频序列进行消融实验,验证增加目标作用力之后的数据关联结果,消融实验结果表明,增加目标作用力之后可以改善目标跟踪的精度和其他指标,尤其在遮挡不明显的视频序列中。结论本文在目标多特征的基础之上增加目标节点间作用力,加强了目标间的数据关联,减少错跟的目标数量,有效地提高了目标跟踪的精度。

一种基于图模型的可信云资源调度算法

根据并行任务及胖树形云系统的结构特点,综合考虑了云计算环境下资源节点与通信链路的可靠性问题,构建了基于任务执行行为的云系统可靠性度量模型。提出了一种基于图的可信云资源调度模型,将云任务可信资源需求与云资源动态供给的最优匹配问题转换成最小费用最大流图的构造和求解问题。针对图的求解计算复杂度较高的问题,结合商空间理论将初始网络转化为规模较小的商网络进行求解。仿真实验结果表明,该算法能够有效提高云任务执行的成功率,降低基于图模型的资源调度算法延迟。