多链马氏决策优化理论研究及在联合更换问题中的应用

论文摘要

为生产生活中提供服务和支持的环节,因其重要性,越来越吸引人们对其分析和优化的关注。本研究中昂贵设备的部件联合更换问题即是一例。在设备维修时,可利用机会同时更换一些将要到期的部件从而分摊维修固定费、拆装费等。好的更换策略,能在个别部件费用和整体的规模经济上进行恰当的折中,而取得可观的效益。然而,决策难以评价、问题规模巨大、最优策略不规则等造成策略的优化非常困难。本研究从问题的结构特征为切入点,基于马氏决策取得了一系列具有普适性和问题针对性的结果。主要的贡献和创新点如下所述。1.提出了可求解弱连通模型的时间集结马氏过程。现有的时间集结方法,处理的是具有单链性质的马氏决策问题。然而,实际问题可能很难判断或不具备该性质,如本文的维修问题。本文给出了弱连通模型下的时间集结马氏决策过程的描述,并得到了策略迭代求解算法。提出了渐近优化方法,并进而得到了更具意义的值迭代算法。该算法不但可求解弱连通模型,即使在单链问题中,和现有方法相比,也有求解规模更大、所需存储和计算资源更少的优点。2.在时间集结马氏决策过程的基础上,针对联合更换问题,设计了可有效求解实际大规模问题的“单阶段分析”启发式方法。相比于传统的阈值型方法,该方法具有较好的性能,尤其是设备故障率小及固定费用相对部件费用较高时。同时,证明了该方法所得策略具有我们所知的最优策略的两点性质。3.基于策略迭代,提出了处理大规模多链马氏决策问题的Rollout算法,对启发式算法进行改进。在极限情况下,该方法实际是一步策略改进。分析讨论了方法中参数选择对结果的影响。为克服大量仿真计算的问题,将“序优化”的思想和最优计算量分配的技术引入到Rollout方法中,提高了算法的效率。对于联合更换问题,当状态空间小或者比较大时,可使用时间集结策略迭代和值迭代来求解,以获取最优策略为目标。当状态空间很大时,单阶段分析法可快速得到近优策略;在计算时间允许的情况下,Rollout算法是更好的选择。以上方法的效果在数值算例和实际数据上都得到了很好的体现。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 理论背景
• 1.1.1 离散顺序决策问题
• 1.1.2 决策问题的优化方法
• 1.2 应用背景
• 1.2.1 引擎部件的联合更换问题
• 1.2.2 多部件联合更换问题国内外的研究现状
• 1.3 研究意义
• 1.4 研究思路与论文内容
• 第2章 马氏决策理论简介及联合更换问题的建模和分析
• 2.1 本章引言
• 2.2 马氏决策理论简介
• 2.2.1 马氏决策问题的定义及动态规划解法
• 2.2.2 平均费用模型及值迭代策略迭代解法
• 2.2.3 马氏决策过程的算法复杂性及大规模问题处理方法
• 2.3 联合更换问题的建模和分析
• 2.3.1 联合更换问题的马氏模型
• 2.3.2 模型的多链及连通性质
• 2.3.3 问题难点和结构带来的启示
• 2.4 本章小结
• 第3章 弱连通模型的时间集结理论
• 3.1 本章引言
• 3.2 弱连通模型的时间集结马氏决策问题
• 3.3 时间集结的马氏决策问题的求解
• 3.3.1 适于弱连通模型的渐近优化法
• 3.3.2 适用于弱连通模型的时间集结值迭代算法
• 3.4 算法应用
• 3.4.1 策略迭代求解一个连通的多链问题
• 3.4.2 与现有时间集结算法的比较
• 3.5 本章小结
• 第4章 联合更换问题最优求解及启发式算法
• 4.1 本章引言
• 4.2 时间集结法求解联合更换问题
• 4.3 单阶段分析法
• 4.4 单阶段分析法的性能与策略结构
• 4.5 单阶段分析法求解联合更换问题
• 4.5.1 与最优策略在性能上的比较
• 4.5.2 与最优策略在结构上的比较
• 4.6 本章小结
• 第5章 以Rollout方法改进启发式算法
• 5.1 本章引言
• 5.2 多链马氏决策过程的Rollout方法
• 5.3 对Rollout算法实现的分析
• 5.3.1 前瞻长度对算法的影响
• 5.3.2 以更有效的方式进行多次仿真
• 5.4 应用举例
• 5.4.1 较大规模问题测试算法的性能
• 5.4.2 求解工程实际中的大规模问题
• 5.5 本章小结
• 第6章 总结和展望
• 6.1 论文总结
• 6.2 研究展望
• 参考文献
• 致谢
• 附录A 论文数值算例的参数
• 个人简历、在学期间发表的学术论文与研究成果