不确定图最可靠最大流算法研究

文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型,这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义;然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA,通过简单路径流量的组合,在无需求得所有最大流分布的情况下获得最可靠最大流,并在组合过程中引入概率剪枝与约束剪枝策略,对无效组合进行过滤,从而显著地提高了算法效率;接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题,又提出一种基于状态空间划分的最可靠最大流算法SDBA,该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合,进而寻找所有闭合区间中概率最大的下界状态,经证明这个下界状态对应子图中的最大流分布为最可靠最大流;最后通过实验,比较了两种算法的性能.实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加,但时间复杂度方面具有较大的优势,能够很好地解决SPCA算法性能受制于容量的问题,具有更好的性能与适用性.     

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

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

流不平衡条件下飞机恢复的优化模型与算法研究

为更有效地解决航空公司飞机恢复问题,在经典的资源指派优化模型中放宽飞机流平衡约束,加入合并航班的恢复策略;在贪婪随机自适应算法(GRASP)和模拟退火算法的基础上,提出一种新的启发式算法贪婪随机模拟退火算法,降低了陷入局部最优解的概率,同时通过限定路径对的种类和候选解的数量,提高了算法的时间效率.实例计算结果表明,本文提出的模型和算法能有效处理流不平衡条件下大规模飞机恢复问题,在有效的时间内求得最优解或近似最优解.     

基于最小费用最大流的大规模资源调度方法

并行作业是大规模资源调度的研究热点.已有研究工作通常采用队列进行资源调度建模,仅能满足局部最优解,只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束三种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构使其具备适应性调整能力.其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法.最后,实验对比公平性、优先级和放置约束三种资源调度典型系统,验证了本方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真验证了万级规模下基于图的资源调度延迟,比基于未优化图算法的资源调度延迟最多降低10倍.     

一种改进蚁群算法的移动机器人快速路径规划算法研究

以Dijkstra算法求解移动机器人路径规划(mobile robot path planning,MRPP)问题已得到广泛的应用,但在复杂工况下无法保证求解的正确性和全局最优性.而基于蚁群算法的移动机器人路径规划模型,在一定条件下能可靠地获得全局最优解,但存在求解时间过长的问题.因此,提出一种结合Dijkstra算法和蚁群算法模型两者优势求解MRPP问题的融合优化方法,以实现在短时间内获得全局最优解的目标.首先,应用Dijkstra快速算法在机器人工作环境中粗略寻迹得到最短路径次优解,然后,在次优解路径附近进行工作环境的精确划分;最后,利用蚁群算法在次优解附近精确寻迹,使最终的寻迹结果无限逼近最短路径.仿真结果表明,该融合优化方法既克服了经典蚁群算法求解时间过长的缺点,又能无限逼近全局最优解,寻迹时间较蚁群算法可缩短90%以上.     

一种基于改进堆优化Dijkstra算法的最小费用最大流算法

通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式,而Dijkstra算法是最高效的最短路径算法之一。本文通过证明残存网络中不存在负循环,采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率。实验结果表明,与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比,本文提出的改进算法具有更高的时间效率。     

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

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

k最近邻流序列算法对异常流检测的优化研究

通过时空异常流检测技术可以发现城市交通数据中的异常交通特征。与时间序列中单个异常流检测采用的方法不同,提出了从流序列中检测异常流分布的k最近邻流序列算法（kNNFS）。算法首先为每个位置测定每个时间区间内的单个流观测值;随后计算单个流的观测频率来构建每个位置处每个时间区间的流分布概率库;最后由阈值判定使用KL散度计算的新的流分布概率与其k最近邻之间的距离是否为异常值,距离值小于阈值则更新入流分布概率库,否则为异常的流分布。仿真分析表明,对比DPMM算法和SETMADA算法,kNNFS算法在检测精度和算法运行时间方面均有优化提升。     

最短时限最少耗费指派问题的一种解法

对最短时限最少耗费指派问题分两步求解,第一步使用最大优先指派算法(MSFA)结合二分图匹配快速求解最短时限值;第二步在已求得的最短时限下,构造带权二分图,使用最小带权二分图指派算法求解,得到最短时限下的最少耗费指派解。所提出的求解方法思路简单清晰,便于计算机实现。     

基于并行图计算框架大规模图最大流加速算法

最大流是一个重要的图计算问题,很多实际场景中如城市车流量和排水管道的排水量等问题若转化为最大流问题可以得到有效的解决.已有工作从多个角度对最大流问题进行了探讨,但仍存在一些问题.针对一些分布式图计算系统进行图分割计算复杂度较高,多次计算存在大量冗余工作等问题,提出基于GraphChi框架的大规模图最大流加速算法.根据原图中的割点构建覆盖图,给定源点和汇点后确定覆盖图中唯一路径,在GraphChi框架上并行求解覆盖图路径上各子图的最大流,找到各子图最大流的最小值即为原图的最大流值.在美国路网数据集的测试结果表明,提出的算法可显著缩短大规模图的最大流计算时间并且空间复杂度较低,有很好的加速效果.     

微流控芯片中电渗流的数值模拟与仿真研究

从电渗流形成的基本理论入手,推导了电场和流场双物理场耦合的控制方程.运用多物理场数值计算分析软件建立了长为1000μm,宽为100μm的二维流道,在微流道中间250~750μm的区域施加了直流电压,并在数值模拟中还原了微流道内壁和微流体的物理属性,计算得出了各段流体的速度场,进而得出了各段流体的流型.通过二维流道压力分布分析了微流道中各段产生不同流型的原因.对微流控芯片中的电动流动的功能原理分析及优化设计具有借鉴意义.     

Electroosmotic flow at a liquid–air interface

This paper presents the first experimental evidence on electroosmotic flow at a liquid–air interface. A PDMS microchannel with an opening to air was created to allow for the formation of a liquid–air interface. Polystyrene particles were used to visualize the liquid motion and the experiments found that the particle velocity at the liquid–air interface was significantly slower than the particle velocity in the bulk. This result agrees with a mathematical model that considers the effects of electrical surface charges at the liquid–air interface in electroosmotic flow.     

高精度超声流量传感器建模

介绍基于Prandtl的流速分布经验公式、光滑管的Prandtl方程和粗糙管的Colebrook方程的超声流量传感器建模,以及超声流量计高精度测量的实现方法。通过M atlab仿真分析流速分布指数和流速分布系数的计算方法及其对流速测量的影响。最后,通过实验数据的误差分析,验证模型的正确性,其测量精度可达1%。     

On Boundary Condition Capturing for Multiphase Interfaces

This review paper begins with an overview of the boundary condition capturing approach to solving problems with interfaces. Although the authors’ original motivation was to extend the ghost fluid method from compressible to incompressible flow, the elliptic nature of incompressible flow quickly quenched the idea that ghost cells could be defined and used in the usual manner. Instead the boundary conditions had to be implicitly captured by the matrix formulation itself, leading to the novel approach. We first review the work on the variable coefficient Poisson equation, noting that the simplicity of the method allowed for an elegant convergence proof. Simplicity and robustness also allowed for a quick extension to three-dimensional two-phase incompressible flows including the effects of viscosity and surface tension, which is discussed subsequently. The method has enjoyed popularity in both computational physics and computer graphics, and we show some comparisons with the traditional delta function approach for the visual simulation of bubbles. Finally, we discuss extensions to problems where the velocity is discontinuous as well, as is the case for premixed flames, and show an example of multiple interacting liquids that includes all of the aforementioned phenomena.     

S中国销售公司投诉流程优化仿真

业务流程决定了企业运营的效率,其涵盖了采购、制造、销售等一系列的生产环节,因此对流程的分析和优化对于企业管理来说有着十分重要的作用。投诉,在日常生活中是商家和客户关系中最常见却又最敏感的问题,投诉问题处理好坏直接关系到商家的信誉和品质,应该引起足够的重视。本文分析了现有的S中国销售公司的投诉流程,发现其流程在时间成本和费用成本的消耗上都存在问题,需改进。利用Witness仿真软件对投诉流程系统进行建模和仿真,提出了投诉流程的优化方案,仿真结果证明了改进后方案的可行性和有效性,为流程的优化提供了一种有效的定量分析技术。     

MEMS-based gas flow sensors

Micro-electro-mechanical system (MEMS) devices integrate various mechanical elements, sensors, actuators, and electronics on a single silicon substrate in order to accomplish a multitude of different tasks in a diverse range of fields. The potential for device miniaturization made possible by MEMS micro-fabrication techniques has facilitated the development of many new applications, such as highly compact, non-invasive pressure sensors, accelerometers, gas sensors, etc. Besides their small physical footprint, such devices possess many other advantages compared to their macro-scale counterparts, including greater precision, lower power consumption, more rapid response, and the potential for low-cost batch production. One area in which MEMS technology has attracted particular attention is that of flow measurement. Broadly speaking, existing micro-flow sensors can be categorized as either thermal or non-thermal, depending upon their mode of operation. This paper commences by providing a high level overview of the MEMS field and then describes some of the fundamental thermal and non-thermal micro-flow sensors presented in the literature over the past 30 years or so.     

硅流量传感器的发展

概述了近年发展起来的、利用热传导原理的固态硅流星传感器。这类传感器具有灵敏度高、响应快、易于智能化、批量化和造价低等特点。适用于小流量测量。图4幅参18     

影响流量管流量系数的因素分析

对某航空发动机整机试验装置的流量管三维流场进行数值模拟,通过布置虚拟测点,建立流量管虚拟试验校准和测量的仿真方法,研究流量管流量系数获取方法、校准试验测试布局,分析来流雷诺数、壁面粗糙度、流量管圆度对流量系数的影响。结果表明,附面层位移厚度法和校准试验法获取的流量系数接近。在同一流向布置测量截面,流量系数随流量管内雷诺数的减小而减小,随流量管壁面粗糙度的增大而减小;低雷诺数工况下,流量系数对粗糙度变化不敏感。对于低雷诺数工况或者在流量管壁面粗糙度较大时,应采用附面层位移厚度法或校准试验法获取流量系数。流量系数对流量管圆度的变化不敏感,建议采用校准试验方法获得有变形的流量管的流量系数。尽量采用校准试验法获取流量管宽雷诺数范围的流量系数,采用实际测量工况下的雷诺数对应的流量系数,修正流量管测量数据,才可保证流量管测量精度。     

一种基于流图变换的代码迷惑算法

为了提高软件的安全性,常使攻击者难以理解专利软件系统内部的工作机制,代码迷惑技术因其代价低廉而越来越受到人们的重视。代码迷惑技术的提出对于软件保护具有非常重要的意义,代码迷惑技术的使用可以对程序代码及核心算法进行保护。简要概述了代码迷惑技术基本内容,阐述了基本块和流图的相关知识,给出了可归约流图变换为不可归约流图的迷惑变换具体的算法及实验结果,并对算法的有效性进行了分析。