运筹学-动态规划ppt课件

1、1 动态规划应用举例 2 不确定型问题的动态规划算法 3 总结动态规划的特点 ABC动态规划是一种方法，而不是算法。即对复杂问题需加以分析才能应用动态规划的迭代算法进行求解，而且其中具有很大技巧性。动态规划目前已广泛用于旅行路径问题、资源分配问题、生产计划问题、设备更新问题、排序问题及复合系统可靠性问题等等。一、复合系统可靠性问题例3-10某复合系统由三个部分串联而成，其示意图见图3-15。知： 图3-15 A、B、C相互独立各部分的单件故障率分别为：P1=0.3，P2=0.2，P3=0.4显然，若各部分只有一个部件时其总可靠率f为：f=(10.3)(10.2)(10.4)=0.336每个部分

2、的单件价格为：A部分单价c1=2万元； B部分单价c2=3万元；C部分单价c3=1万元共投资购置部件额10万元求A、B、C三部分各应购置多少部件才能使总可靠率最高？ 解采用动态规划法，令A、B、C分别为阶段1、2、3。并定义：sk第k阶段及以后可用来购买部件总额。xk第k环节配备的件数ck环节k部件单价Pk环节k单件的故障率显然，第k环节本身的可靠率为：dk(sk，xk)=)(1 kxkP 状态转移方程：sk+1=skckxk令：fk(sk，xk)表示第k阶段共有资金sk，且买k环节的部件数为xk时的k段及以后各段组成的系统最高可靠率。fk(sk)表示k阶段尚有资金sk时，可能获得k段及以后各

3、段组成系统的最高可靠率。则递推方程为：fk(sk)= dk(sk，xk)fk+1(skckxk)fN+1(sNcNxN)=1采用后向动态规划法，从第3阶段算起。kxmax 第1步：考虑购置部件C的数量。因为A、B至少各购一件否则，整个可靠性为零）。则用于购置C部件的最高金额为：s3=10c1c2=5(万元)显然，由于C是最后阶段，故应把剩余金额全部购置C部件，具体计算结果示如表3-11。 表3-11 阶段3计算结果 s3x3 f3(s3)=d3(s3，x3) x*3 12345123450.6000.8400.9360.9740.99012345例如，当s3=3万元时，那么： f3(3)=d(

4、3，3)=10.43=0.936。 第2步：退到阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部件为最优。显然，此时B、C应至少各配制1个部件，故s2c2+c3=3+1=4；同时，A部件亦至少配备1个部件，故s2102=8。阶段2计算结果示如表3-12。 表3-12 阶段2计算结果s2 x2 d2(s2,x2) s3 f3(s3) f2(s2,x2) f2(s2) x*2 456778811112120.80.80.80.80.960.80.9612341520.6000.8400.9360.9740.6000.9900.8400.4800.6720.7490.7790.5760.

5、7920.8060.4800.6720.7490.779 0.8061111 2例如，当s2=8时，可有2个选择方案：令x2=1，得f2(8，1)=d2(8，1)f3(831)=(1P2)f3(5)=(10.2)0.990=0.80.990=0.792令x2=2，得f2(8，2)=d2(8，2)f3(832)=(1P22)f3(2)=(10.22)0.840=0.960.84=0.80640.806故应选x2*=2。第3步：退回到A部件处，s1=10万元。计算结果示于表3-13。可见最优分配资金可获得最高可靠率为0.682，反向跟踪所购置部件为：A、B、C、分别购置2、1和3件。表3-13 阶

6、段1的计算结果 s1 x1 d1(s1,x1) s2 f2(s2) f1(s1,x1) f1(s1) x*1 10 1230.70.910.9738640.8060.7490.4800.5640.6820.467 0.682 2 当研究的对象的参量出现不确定状况和受到随机干扰时，这样在根据某阶段的状态和决策就不能导出下阶段的状态确定值，其阶段收益函数也不确定，即变为：f(x，u)f(x，u，e)e为随机变量，这时，只能求出阶段期望值来进行选择最优决策。显然，前向动态规划无法解决，只能应用后向动态规划算法。不确定型问题的动态规划算法的一般公式可归纳如下。设规划中，第末端为0级，始端为n级。这样后

7、向递推从0级开始进行。令： V最优函数值d决策变量e随机变量f阶段收益s状态变量E期望值则知： Vn(sn)=max Efn(dn，sn，en)+Vn1(sn1) sn1=tn(dn，sn，en) 起步 V0(s0)=max Ef0(d0，s0，e0)下面举例说明。例3-12生产计划问题。厂长需决定当年开始两个月内的最优生产计划，知：产品生产费用1000元/件产品销售价格2000元/件产品储存费用100元/件月两个月后，产品一次性处理，500元/件 目前厂内无存货，且生产周期短，当月生产可满足当月订货需求。货物需求的概率分布见表3-15。表3-15 工厂货物需求概率分布需求概率0123 0.2

8、50.400.200.15 求第1个月应生产多少件产品才能使收益期望值最大或损失最少）？ 当第1个月已度过，第2个月应生产多少件产品才能使余下收益期望最大？解 仍需分三个阶段走，首先从二月末开始计算，然后倒退到二月初和一月初。1设时间已到二月末，此时库存水平I0有4种可能性：0、1、2、3因需求最大为3）。则针对这几种可能性都必定一次性处理，其处理价为500元/件，最后计算结果示于表3-16。 表3-16 阶段0计算结果 I0 V0 0123 050010001500 2设已到二月初，此时，必已知一月末的库存I1，针对不同的I1状态），决定每一种可能的生产数量决策），相应收益以及售出水平等。对

9、每一种库存水平选择使期望收益最大的生产数量，其计算结果于表3-17。其中，*为最优决策值。 表3-17 阶段1计算结果 状态 I1 生产d1 销售s1 概率 新产生状态I0 生产费用 销售收入 库存费用 V0（I0） 概率$ 期望收益 0 001.0000000001010.250.7510-1000-100002000-10005000-150750600* 20120.250.400.35 210 -2000-2000-2000 020004000 -200-1000 10005000 -300160700 560 30123 0.250.400.200.15 3210 -3000-300

10、0-3000-3000 0200040006000 -300-200-1000 150010005000 -450-80280450 200 例如，当库存水平I1=0时，有4种可能决策d1=（0，1，2，3）。当选择d1=2时，其销售量则仅有0，1，2三种可能性，其概率为：P(0)=0.25；P(1)=0.40；P(2)=P(2)+P(3)=0.35现就分析当I1=0，d1=2，s1=2情况：销售概率s1(2)=0.35新产生二月末存货状态I0=0生产费用为2000元，即收益为2000元。销售收入为4000元。 库存费用为0。转移到0阶段的收益V0I0为0。概率收益值为40002000）0.3

11、5=700元。同时也可算出当s1=0和s1=1时的概率收益分别为300和160，其最后知I1=0，d1=2时的期望收益值为700300+160）=560元）。同理知：d1=0 时，总期望收益为0。 d1=1时，总期望收益为600。 d1=3时，总期望收益为200。 最后知，当状态I1=0时，最优决策d1*(0)=1，V1(0)=600，当I1为其它值时，计算结果示于表3-18。 表3-18 I1 V1（I1） D1*(I1) 0123 600160025603200 1000 3)退到一月初，此时初始存货为0，即I2=0，其计算方式同前，其结果示如表3-19。 表3-19 阶段2计算结果I2=

12、0） 状态 I2 生产d2 销售s2 概率 新产生状态I1 生产费用 销售收入 库存费用 V1（I1） 概率$ 期望收益 0 001.0000006006006001010.250.7510-1000-100002000-10001600600 1251200 1325 20120.250.400.35 210 -2000-2000-2000 020004000 -200-1000 25601600600 90600910 1600* 30123 0.250.400.200.15 3210 -3000-3000-3000-3000 0200040006000 -300-200-1000 320

13、025601600600 -25544500540 1559 综合结果知，当I2=0时，d2*(I2)=2，V2(I2)=1600。最后结果可归纳为决策树，具体示如图3-17。从图3-17看出，从期望收益可找出一月初的最优决策，然而找不出向后走的确切轨迹，而需根据以后发生的事件从决策树中找出相应决策。根据决策树，便可回答前面提的2个问题： 一月初最优期望值收益决策为： 决策d2=2，期望收益为1600元。 当时间指向一月末或二月初），此时决策取决于一月份销售量，即一月末存货量I1。 当I1=0，取决策d1=1。 当I1=1，2时，决策d1全为0。 0 -（0.25）1 -（0.40）2 -（0

14、.20）3 -（0.15）0 -（0.25）1 -（0.40）2 -（0.20）3 -（0.15）0 -（0.25）1 -（0.40）2 -（0.20）3 -（0.15）2 1 0 0 0（概率=0.25）（概率=0.40）（概率=0.35） 2 0 1 2或3 2 0图3-17 例3-12结果决策树级数10 2 1 0 0 1 0 0 0 1 0 0 0 1状态 决策 事件 结果 状态 决策 事件 结果 状态 开始存货 生产 概率需求 需求 存货 生产 概率需求 需求 存货 一、动态规划由于具有下述优点而得到广泛的应用1对目标函数的形式不加限制。2对于约束条件容易处理。3所得结果，在理论上属绝对最优。（对概率型，属概率意义上绝对最优）4运算过程简单。5计算结果为一个“解族”，即获得了整个决策树。这样，当由于干扰使运动过程离开了原最优轨迹，则可在新状态下沿已计算好的另一条轨迹行进。 108976543211644236136176619103710988,96129109895468444108108图3-1最优旅行路线问题 例 如 ， 在 图 3 - 1 中