运筹学-动态规划(三)(名校讲义

《运筹学-动态规划(三)(名校讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十讲动态规划（三）§1动态规划应用举例§2不确定型问题的动态规划算法§3总结—动态规划的特点§1动态规划应用举例（1）ABC动态规划是一种方法，而不是算法。即对复杂问题需加以分析才能应用动态规划的迭代算法进行求解，而且其中具有很大技巧性。动态规划目前已广泛用于旅行路径问题、资源分配问题、生产计划问题、设备更新问题、排序问题及复合系统可靠性问题等等。一、复合系统可靠性问题[例3-10]某复合系统由三个部分串联而成，其示意图见图3-15。已知：图3-15§1动态规划应用举例（2）①A、B、C相互独立②各

2、部分的单件故障率分别为：P1=0.3，P2=0.2，P3=0.4③显然，若各部分只有一个部件时其总可靠率f为：f=(1－0.3)(1－0.2)(1－0.4)=0.336④每个部分的单件价格为：A部分单价c1=2万元；B部分单价c2=3万元；C部分单价c3=1万元⑤共投资购置部件额10万元求A、B、C三部分各应购置多少部件才能使总可靠率最高？§1动态规划应用举例（3）[解]采用动态规划法，令A、B、C分别为阶段1、2、3。并定义：sk——第k阶段及以后可用来购买部件总额。xk——第k环节配备的件数ck——

3、环节k部件单价Pk——环节k单件的故障率显然，第k环节本身的可靠率为：dk(sk，xk)=§1动态规划应用举例（4）状态转移方程：sk+1=sk－ckxk令：fk(sk，xk)表示第k阶段共有资金sk，且买k环节的部件数为xk时的k段及以后各段组成的系统最高可靠率。fk(sk)表示k阶段尚有资金sk时，可能获得k段及以后各段组成系统的最高可靠率。则递推方程为：fk(sk)=[dk(sk，xk)×fk+1(sk－ckxk)]fN+1(sN－cNxN)=1采用后向动态规划法，从第3阶段算起。§1动态规划应用

4、举例（5）第1步：考虑购置部件C的数量。因为A、B至少各购一件（否则，整个可靠性为零）。则用于购置C部件的最高金额为：s3=10－c1－c2=5(万元)显然，由于C是最后阶段，故应把剩余金额全部购置C部件，具体计算结果示如表3-11。§1动态规划应用举例（6）表3-11阶段3计算结果s3x3f3(s3)=d3(s3，x3)x*312345123450.6000.8400.9360.9740.99012345例如，当s3=3万元时，则：f3(3)=d(3，3)=1－0.43=0.936。§1动态规划应用举

5、例（7）第2步：退到阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部件为最优。显然，此时B、C应至少各配制1个部件，故s2≥c2+c3=3+1=4；同时，A部件亦至少配备1个部件，故s2≤10－2=8。阶段2计算结果示如表3-12。§1动态规划应用举例（8）表3-12阶段2计算结果s2x2d2(s2,x2)s3f3(s3)f2(s2,x2)f2(s2)x*2456778811112120.80.80.80.80.960.80.9612341520.6000.8400.9360.9740.60

6、00.9900.8400.4800.6720.7490.7790.5760.7920.8060.4800.6720.7490.7790.80611112§1动态规划应用举例（9）例如，当s2=8时，可有2个选择方案：①令x2=1，得f2(8，1)=[d2(8，1)][f3(8－3×1)]=(1－P2)f3(5)=(1－0.2)×0.990=0.8×0.990=0.792②令x2=2，得f2(8，2)=[d2(8，2)][f3(8－3×2)]=(1－P22)·f3(2)=(1－0.22)×0.840=0.

7、96×0.84=0.8064≈0.806故应选x2*=2。第3步：退回到A部件处，s1=10万元。计算结果示于表3-13。§1动态规划应用举例（10）可见最优分配资金可获得最高可靠率为0.682，反向跟踪所购置部件为：A、B、C、分别购置2、1和3件。表3-13阶段1的计算结果s1x1d1(s1,x1)s2f2(s2)f1(s1,x1)f1(s1)x*1101230.70.910.9738640.8060.7490.4800.5640.6820.4670.6822§2不确定型问题的动态规划算法（1）当研

8、究的对象的参量出现不确定状况和受到随机干扰时，这样在根据某阶段的状态和决策就不能导出下阶段的状态确定值，其阶段收益函数也不确定，即变为：f(x，u)→f(x，u，e)e为随机变量，这时，只能求出阶段期望值来进行选择最优决策。显然，前向动态规划无法解决，只能应用后向动态规划算法。不确定型问题的动态规划算法的一般公式可归纳如下。设规划中，第末端为0级，始端为n级。这样后向递推从0级开始进行。令：§2不确定型问题的动态规划算法（2）V——最优函数