论文部分内容阅读
摘要:本文讨論在总费用一定的条件下,如何配置各部件的备件使系统可靠性最大的问题. 在对串接系统的各部件抽象简化分析的基础上,利用动态规划的方法,建立了合理的优化模型。(1)首先,引入串联系统等概念,利用多阶段决策动态规划法,将系统备件配置问题以部件号为准划分为多个阶段;其次,建立部件正常工作的概率与费用之间的指标函数;最后,结合最优化原理确立动态规划基本方程,即固定总费用下系统可靠性最大的模型。(2)在问题一的优化模型基础上,结合必要数据,用逆序解法对基本方程进行求解. 易得当总费用为10,部件1的备件数量为3,部件2的备件数量为1,部件3的备件数量为2时,系统的可靠性达最大,此时,系统正常工作的概率为0.504。最后,以问题二的求解结果为依据,采用遍历搜索的办法对模型的科学性和现实性进行了验证。
关键词:优化模型;多阶段决策;动态规划;遍历搜索法
中图分类号:O242.1 文献标识码:A 文章编号:1003-2177(2018)05-0065-03
1 问题重述
系统由若干部件组成,只要一个部件出现故障,系统就不能正常工作。为提高系统可靠性,每个部件都装有备件,一旦原部件出现故障,备件就自动进入系统。显然,备件越多系统可靠性越大,但费用也越高。问题是在一定的费用下,如何配置各部件的备件使系统的可靠性最大。
问题一:由N个部件串接的系统,当部件k配置j个备件时,该部件正常工作的概率及费用已知,在总费用不超过定值的条件下,建立使系统的可靠性最大的模型。
问题二:先设定总费用为10,若n=3且每个部件至多配置3个备件,部件k配置j个备件时正常工作的概率pkj及费用ckj如表1,求证如何配置各部件的备件系数使系统的可靠性最大。
2 问题分析
串联系统是所有部件均可使用时才运转正常的系统,它的可靠性为各部件可靠性的乘积。求系统的最大可靠性是一个典型的多阶段决策问题。动态规划是解决这样一类最优化问题的专门计算方法,这类问题允许把它的过程(求解)分解为一系列的单级过程(步骤)。
而适用动态规划的问题必须满足最优化原理和无后效性。于是,我们有必要考察一下所求问题是否具有这两点性质:
(1)最优化原理(最优子结构性质):不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。
这里,系统可靠性取决于各部件可靠性的乘积,可将系统配置的最优化问题转化为各部件配置的优化问题。
(2)无后效性:某给定的阶段状态,它之前各阶段的状态无法直接影响它未来的决策,而只能通过当前的状态。
该题表现为各部件的最优效率不影响下一部件的效率性能。
综上所述,该系统可靠性优化问题完全可以用动态规划的方法来解决。
2.1 问题一分析
经分析,该问题满足动态规划的诸要素,故可按以下步骤来建立动态规划模型:
(1)把问题的过程划分为恰当的若干个阶段,引入阶段变量;(2)正确选择状态变量,使它既能描述过程的演变,又能满足无后效性;(3)确定决策变量及每个阶段的允许决策集;(4)写出状态转移方程;(5)指出阶段指标及指标函数;(6)写出最优函数。
2.2 问题二分析
在问题一的模型基础上,结合必要数据,采用逆序解法进行求解即可。
3 模型假设
(1)系统的正常运作只取决于题给的部件;(2)备件配置后即发挥可靠性作用,不因意外因素停止运转;(3)题给数据精确可靠。
4 定义与符号说明
5 模型建立与求解
由问题分析可知,该问题可用动态规划的方法来求解。
5.1 模型建立
按部件划分阶段,将它看做一个n阶段决策问题。把系统第k个部件看作k个阶段,每个阶段初可用于支配的费用是前面阶段决策的结果,也是本阶段决策的依据(示意图如图1)。
按上面的顺序反推算,可以得到:
由以上求解可知,当总费用为10,部件1的备件数量为3,部件2的备件数量为1,部件3的备件数量为2时,系统的可靠性达最大,此时,系统正常工作的概率为0.504。
6 结果分析与检验
6.1 结果的程序验算
对于模型的准确性验证,可利用程序证明(见附录程序6—1)。将动态规划函数的程序录入并计算后发现结果与我们的逆序解法完全一致,充分证明了模型的准确性和科学性。
6.2 模型合理性验证
由于5.2所给数据较少,可采用遍历搜索法进行模型合理性的检验,通过对所有可行解进行分析,最优解为当部件1的备件数量为3,部件2的备件数量为1,部件3的备件数量为2,总费用为: 5 3 2=10,不超过10。系统的可靠性最大时的正常运行概率为:,与用动态规划求解的结果相同。可见,该模型是合理的。
7 模型评价与推广
本文运用动态规划的重要思想,建立了给定费用下,系统配置的最优化模型。
7.1 模型评价
优点:(1)原理简单,适用性广;(2)在模型检验方面,针对该题数据少的实际情况,引入了遍历搜索的办法,更加精准的验证了模型的科学性;(3)由于动态规划方法反映了过程逐段演变的前后联系和动态特征,在计算中可以利用实际知识和经验提高求解效率。
缺点:(1)用数值方法求解时存在维数灾;(2)对于较复杂的问题在选择状态、决策、确定状态转移规律等方面缺乏灵活性,这就带来了应用上的局限性。
7.2 模型改进
当系统部件数目较大时,可借助计算机求取最优解。
7.3 模型推广
本模型适用性较广,可用于解决实际生活中的问题,例如,人员分配问题,最大受益问题以及最短路径问题。
参考文献
[1](美) Frank R Giordano,等.数学建模[M].叶其孝,姜启源,等译.北京:机械工业出版社,2009.
[2]徐欲生,张海英.运筹学[M].北京:北京大学出版社,2005.
[3]王连堂.数学建模[M].西安:陕西师范大学出版社,2008.
[4]阳明盛.MATLAB基础及数学软件[M].大连:大连理工大学出版社,2003.
[5]于义良.数学建模[M].北京:中国人民大学出版社,2004.
关键词:优化模型;多阶段决策;动态规划;遍历搜索法
中图分类号:O242.1 文献标识码:A 文章编号:1003-2177(2018)05-0065-03
1 问题重述
系统由若干部件组成,只要一个部件出现故障,系统就不能正常工作。为提高系统可靠性,每个部件都装有备件,一旦原部件出现故障,备件就自动进入系统。显然,备件越多系统可靠性越大,但费用也越高。问题是在一定的费用下,如何配置各部件的备件使系统的可靠性最大。
问题一:由N个部件串接的系统,当部件k配置j个备件时,该部件正常工作的概率及费用已知,在总费用不超过定值的条件下,建立使系统的可靠性最大的模型。
问题二:先设定总费用为10,若n=3且每个部件至多配置3个备件,部件k配置j个备件时正常工作的概率pkj及费用ckj如表1,求证如何配置各部件的备件系数使系统的可靠性最大。
2 问题分析
串联系统是所有部件均可使用时才运转正常的系统,它的可靠性为各部件可靠性的乘积。求系统的最大可靠性是一个典型的多阶段决策问题。动态规划是解决这样一类最优化问题的专门计算方法,这类问题允许把它的过程(求解)分解为一系列的单级过程(步骤)。
而适用动态规划的问题必须满足最优化原理和无后效性。于是,我们有必要考察一下所求问题是否具有这两点性质:
(1)最优化原理(最优子结构性质):不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。
这里,系统可靠性取决于各部件可靠性的乘积,可将系统配置的最优化问题转化为各部件配置的优化问题。
(2)无后效性:某给定的阶段状态,它之前各阶段的状态无法直接影响它未来的决策,而只能通过当前的状态。
该题表现为各部件的最优效率不影响下一部件的效率性能。
综上所述,该系统可靠性优化问题完全可以用动态规划的方法来解决。
2.1 问题一分析
经分析,该问题满足动态规划的诸要素,故可按以下步骤来建立动态规划模型:
(1)把问题的过程划分为恰当的若干个阶段,引入阶段变量;(2)正确选择状态变量,使它既能描述过程的演变,又能满足无后效性;(3)确定决策变量及每个阶段的允许决策集;(4)写出状态转移方程;(5)指出阶段指标及指标函数;(6)写出最优函数。
2.2 问题二分析
在问题一的模型基础上,结合必要数据,采用逆序解法进行求解即可。
3 模型假设
(1)系统的正常运作只取决于题给的部件;(2)备件配置后即发挥可靠性作用,不因意外因素停止运转;(3)题给数据精确可靠。
4 定义与符号说明
5 模型建立与求解
由问题分析可知,该问题可用动态规划的方法来求解。
5.1 模型建立
按部件划分阶段,将它看做一个n阶段决策问题。把系统第k个部件看作k个阶段,每个阶段初可用于支配的费用是前面阶段决策的结果,也是本阶段决策的依据(示意图如图1)。
按上面的顺序反推算,可以得到:
由以上求解可知,当总费用为10,部件1的备件数量为3,部件2的备件数量为1,部件3的备件数量为2时,系统的可靠性达最大,此时,系统正常工作的概率为0.504。
6 结果分析与检验
6.1 结果的程序验算
对于模型的准确性验证,可利用程序证明(见附录程序6—1)。将动态规划函数的程序录入并计算后发现结果与我们的逆序解法完全一致,充分证明了模型的准确性和科学性。
6.2 模型合理性验证
由于5.2所给数据较少,可采用遍历搜索法进行模型合理性的检验,通过对所有可行解进行分析,最优解为当部件1的备件数量为3,部件2的备件数量为1,部件3的备件数量为2,总费用为: 5 3 2=10,不超过10。系统的可靠性最大时的正常运行概率为:,与用动态规划求解的结果相同。可见,该模型是合理的。
7 模型评价与推广
本文运用动态规划的重要思想,建立了给定费用下,系统配置的最优化模型。
7.1 模型评价
优点:(1)原理简单,适用性广;(2)在模型检验方面,针对该题数据少的实际情况,引入了遍历搜索的办法,更加精准的验证了模型的科学性;(3)由于动态规划方法反映了过程逐段演变的前后联系和动态特征,在计算中可以利用实际知识和经验提高求解效率。
缺点:(1)用数值方法求解时存在维数灾;(2)对于较复杂的问题在选择状态、决策、确定状态转移规律等方面缺乏灵活性,这就带来了应用上的局限性。
7.2 模型改进
当系统部件数目较大时,可借助计算机求取最优解。
7.3 模型推广
本模型适用性较广,可用于解决实际生活中的问题,例如,人员分配问题,最大受益问题以及最短路径问题。
参考文献
[1](美) Frank R Giordano,等.数学建模[M].叶其孝,姜启源,等译.北京:机械工业出版社,2009.
[2]徐欲生,张海英.运筹学[M].北京:北京大学出版社,2005.
[3]王连堂.数学建模[M].西安:陕西师范大学出版社,2008.
[4]阳明盛.MATLAB基础及数学软件[M].大连:大连理工大学出版社,2003.
[5]于义良.数学建模[M].北京:中国人民大学出版社,2004.