完整动态规划答案.doc

2 队备件配置优化问题摘 要 本文讨论了在一定总费用下， 如何配置各部件的备件使系统的可靠性最大的问题对问题一，以部件配置备件的数量为决策， 根据状态变量和决策变量写出状态转移方程然后从后向前地计算系统可靠性最大的概率， 得到递推公式和终端条件对问题二，将数据代入问题一的模型 系统的可靠性最大问题转化为求部件间相通的最大概率问题， 从后向前分别求出系统联通的概率， 最后比较得出要使系统的可靠性最大，则需部件 1、 2、 3 的备件数分别为 3 个、 1 个、 2 个动态规划模型常用来求解经济管理中的货物存贮、 设备更新、资源分配、任务均衡、水库调度、系统可靠性等问题，在离散系统最优控制中也有广泛应用关键词 动态规划；备件配置；系统可靠性一、 问题提出系统由若干部件串联而成，只要一个部件出现故障，系统就不能正常工作为了提高系统可靠性每个部件都装有备件， 一旦原部件出线故障， 备件就自动进入系统显然，备件越多系统可靠性越大，但费用也越高在一定的总费用下，如何配置各部件的备件使系统的可靠性最大是一个实际问题通过建立相关数学模型，解决如下问题：问题一：由 n 个部件串联的系统，当部件 k 配置 j 个备件时，该部件正常工作的概率及费用均已知， 在总费用不超过给定值的条件下， 建立使系统的可靠性最大的模型。

问题二：设 n 3且每个部件至多配置 3 个备件，部件 k 配置 j 个备件时正常工作的概率 pkj 及费用 ckj 如表 1，总费用不超过 10 ，如何配置各部件的备件数使系统的可靠性最大表 1备件数量与费用关系图备件数量 j备件数量 j12312310.50.70.91245部件号20.70.80.9部件号235630.60.80.93123二、问题分析该问题属于离散动态优化问题动态规划模型是解决该问题的有效方法对问题一：将部件配置备件的次序划分阶段，部件配置备件的数量为决策，根据状态变量和决策变量写出状态转移方程 然后从后向前地计算系统可靠性最大的概率，得到递推公式对问题二：只需将问题二中的数据代入问题一所建的模型中即可 至于模型的求解，可将每个部件配置备件的费用看做各个部件的不同站点，画出示意图，从一个部件的每一个站点到达下一部件的哪个站点由总费用不超过 10 元及部件间相通的概率决定 系统的可靠性最大问题就可转化为求部件间相通的最大概率问题从后向前分别求出系统联通的概率，最后比较得出结果三、基本假设1、 假设系统的可靠性仅与配置备件的数量有关；2、 假设备件与原部件完全相同；四、符号表示符号表示含义部件数量部件号备件数量部件 k 配置 j 个备件时正常工作的概率部件 k 配置 j 个备件的费用部件 k 配置备件时所容许的费用状态状态 xk 下部件 k 到 n 组成的子系统的最大正常工作概率五、模型建立与求解5.1n 个系统串接的系统可靠性最大模型按照对 n 个部件配置备件的次序划分阶段 k, k1,2, ,n ，部件配置备件的数量 j, j 1,2,, m 为决策。

根据费用的限制，设部件k 配置备件时所容许的费用状态为 xk ，则状态转移方程为 xk 1xkckj .设状态 xk 下部件 k 到 n 组成的子系统的最大正常工作概率为f k( xk ) 则有递推公式：终端条件为 f n 1 ( xn1) 1.5.23 个部件串接系统的模型求解将（ 1）中的模型直观地化为下面的最大概率问题，如图1.2314525图 1 系统正常工作的最大概率问题36有 2,4,5 三个站每个部件配置备件的费用看做各个部件的不同站点， 部件 1点，部件 2 有 3,5,6三个站点，部件 3 有 1,2,3 三个站点， 图中这些站点用圆圈里的数字表示从一个部件的每一个站点到达下一部件的哪个站点由总费用不超过 10 元及部件间相通的概率决定这样系统的可靠性最大就转化为求部件间相通的最大概率问题最大概率问题从后向前求解 , 部件 2 的每个站点与部件 3 的每个站点相通的概率如下 :部件 1 的每个站点到部件 3 的各个站点的最大概率如下：比较部件 1 的每个站点到部件 3 的各个站点的最大概率可知， 部件 1 与部件3相通的最大概率为 0.504. 此时部件 1、 2、 3 的备件购买费用分别为 5、3、2，即部件 1、 2、3 的备件数分别为 3、1、2。

综上所述，要使系统的可靠性最大则需部件1、2、3 的备件数分别为 3 个、1个、2 个六、模型评价与推广该模型运用动态规划的数学思想， 将求系统可靠性最大问题转化为求部件间相通的最大概率问题， 便于模型的求解 而动态规划模型在数值求解时存在维数灾，由于状态个数随维数呈指数增长，对高维问题求解十分困难动态规划模型常用来求解经济管理中的货物存贮、 设备更新、资源分配、任务均衡、水库调度、系统可靠性等问题，在离散系统最优控制中也有广泛应用参考文献[1] 姜启源，谢金星，叶俊，数学模型 ( 第四版 )[M]. 北京 : 高等教育出版社。