SENSITIVITY ANALYSIS OF THE KNAPSACK PROBLEM： TIGHTER LOWER AND UPPER BOUND LIMITS

In this paper, we study the sensitivity of the optimum of the knapsack problem to the perturbation of the profit of a subset of items. We propose a polynomial heuristic in order to establish both lower and upper bound limits of the sensitivity interval. The aim is to stabilize any given optimal solution obtained by applying any exact algorithm. We then evaluate the effectiveness of the proposed solution procedure on an example and a set of randomly generated problem instances.     

基于分层马尔可夫决策过程的AUV全局路径规划研究

自主路径规划是自治式水下机器人(AUV)自主能力的重要体现,是保障AUV在大范围复杂海洋环境中自主完成使命作业的关键技术之一。提出了基于马尔可夫决策过程的路径规划方法;并建立了基本的马尔可夫决策模型和结合状态聚类的分层马尔可夫决策模型,同时给出了两种规划的仿真实验及结果分析。实验证明,此类方法能够很好地求解大范围复杂环境内AUV的二维路径规划问题。     

基于神经网络和PSO的机器人路径规划研究

提出一种神经网络和粒子群算法相结合的移动机器人路径规划方法。采用小波网络和RBF网络相结合的四层神经网络结构,克服了传统神经网络方法进行路径规划时对每个障碍均设计一些特定的隐节点,当障碍较多且环境动态时,网络结构庞大且神经元的阈值随时间的变化而需要不断改变的缺点。利用粒子群对神经网络的参数进行训练,在规定的代数内对网络参数优化,使得机器人在移动过程中能够快速响应环境的变化。通过对移动机器人在动、静态不同环境下的仿真实验,证明了方法的有效性。     

考虑BOM的FMS生产线能力规划问题

针对印刷装配板(Printed Wiring Board, PWB)的制造过程,建立了一个基于多种需求状态的多计划期多种产品类的能力规划模型.该模型考虑了机器的柔性、产品类的BOM(Bill of Materials)约束(物料需求约束)以及进行生产能力调整的风险.考虑该模型是一个大规模的混和整数规划问题,无法用一般的数学软件直接进行求解,提出了一种求解近似最优解的方法,首先应用启发式算法减少装配线能力调整决策变量的搜索空间,然后应用遗传算法进行搜索.最后通过实例分析验证了该方法的可行性及其在管理学上的意义.     

不同约束下多产品报童问题解的比较研究

不同约束形式代表决策者不同的决策过程。传统多产品报童问题只考虑预算和能力等线性约束,而不涉及损失约束,显然有违真实的决策过程。为说明损失约束模型不同于预算约束模型的决策特点,通过算例对两个模型的解进行了分析和比较,总结了各自的决策特点。预算约束模型参照基于预算边际效用删除法和一般迭代方法(GIM法)求解。损失约束模型应用基于损失边际效用排序的删除法与线性近似规划法求解。另外对GIM法中衡量误差的公式作了修正。     

基于神经网络的移动机器人路径规划方法

针对动态环境下移动机器人路径规划,提出了一种基于递归神经网络的实时路径规划方法。利用神经网络表示机器人的工作空间,每个神经元都只有局部侧连接。目标点位置神经元具有全局最大的正活性值,该活性值通过神经元之间的局部侧连接逐渐衰减地传播到整个状态空间,障碍物及其周围区域神经元活性值则被抑制为零。目标点全局地吸引机器人,障碍物局部地将机器人推开实现避障,从而能够在动态环境下产生最优规划路径。仿真结果表明该方法具有较好的环境适应性和实时性。     

北方农牧交错带土地利用结构的最优规划

运用线性规划、层次分析和模糊数学的隶属函数对北方农牧交错带土地利用结构的不同经济效益、投入水平和水土流失为目标的函数进行分权计算与综合评价,最后再运用模糊数学的隶属函数,得出几种评价中最可行的方案.优化方案为土地利用由2005年的农、林和草面积比例54:10:36调整为30:13:57.表8,参7.     

含退出期权的动态联盟控制路径规划

股权控制与关系管理是联盟控制的主要方式.围绕联盟效益和稳定的平衡,根据博弈理论从动态视角研究联盟的控制决策.研究结果表明,在动态博弈框架下,联盟的控制特性及稳定性与企业退出期权的持有能力有关.持有退出期权的企业将在联盟中处于优势地位并倾向于运用单一的控制机制--股权控制.没有退出期权的企业则更加依赖关系管理,联盟的股权控制与关系管理呈现互补特征.随着联盟中持有退出期权的企业数目的增加,联盟关系趋向于不稳定.与此同时,未来联盟收益越高,关系管理的作用就越大,两种控制机制的互补性就越强.     

基于动态RCS的无人机航迹实时规划方法研究

为了提高无人机的生存能力,针对不确定飞行环境的无人机航迹规划问题展开研究,提出了一种基于RCS的无人机航迹实时规划方法,建立了相关计算模型,提出合理的代价函数,并采用多阶段分析博弈评估算法对航迹进行优化。仿真结果表明,基于动态RCS的无人机航迹实时规划方法能够比较好的解决无人机的航迹规划问题。     

基于GIS的网上世博场馆导航系统

网上世博场馆导航系统能够引导游客流向,提高世博会的服务水平.将GIS和虚拟现实技术相结合实现了网上世博场馆虚拟导航系统,系统具备场馆漫游和查询、路线推荐和定制以及流量估计等功能.系统建立了ArcGIS数据库模型,实现了基于FNR树时空数据索引和智能导航组合算法,并利用经验导航路线设计符合用户期望的最佳导航路线.系统能够提供直观、可视、可交互的导航服务.