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

第二十讲 动态规划（三）动态规划（三） 1 动态规划应用举例 2 不确定型问题的动态规划算法 3 总结动态规划的特点 1 1 动态规划应用举例动态规划应用举例 （1 1） ABC 动态规划是一种方法，而不是算法。即对复杂问题需加 以分析才能应用动态规划的迭代算法进行求解，而且其 中具有很大技巧性。动态规划目前已广泛用于旅行路径 问题、资源分配问题、生产计划问题、设备更新问题、 排序问题及复合系统可靠性问题等等。 一、复合系统可靠性问题 例3-10某复合系统由三个部分串联而成，其示意图见 图3-15。 已知： 图3-15 1 1 动态规划应用举例动态规划应用举例 （2 2） A、B、C相互独立 各部分的单件故障率分别为：P1=0.3，P2=0.2，P3=0.4 显然，若各部分只有一个部件时其总可靠率f为： f=(10.3)(10.2)(10.4)=0.336 每个部分的单件价格为：A部分单价c1=2万元； B部分单价c2=3万元；C部分单价c3=1万元 共投资购置部件额10万元 求A、B、C三部分各应购置多少部件才能使总可靠率最高？ 1 1 动态规划应用举例动态规划应用举例 （3 3） 解采用动态规划法，令A、B、C分别为阶段1、2、3。 并定义： sk第k阶段及以后可用来购买部件总额。 xk第k环节配备的件数 ck环节k部件单价 Pk环节k单件的故障率 显然，第k环节本身的可靠率为： dk(sk，xk)= 1 1 动态规划应用举例动态规划应用举例 （4 4） 状态转移方程：sk+1=skckxk 令：fk(sk，xk)表示第k阶段共有资金sk，且买k环节的部件数为 xk时的k段及以后各段组成的系统最高可靠率。 fk(sk)表示k阶段尚有资金sk时，可能获得k段及以后各段组成系 统的最高可靠率。 则递推方程为： fk(sk)= dk(sk，xk)fk+1(skckxk) fN+1(sNcNxN)=1 采用后向动态规划法，从第3阶段算起。 1 1 动态规划应用举例动态规划应用举例 （5 5） 第1步：考虑购置部件C的数量。 因为A、B至少各购一件（否则，整个可靠性为零）。则用于 购置C部件的最高金额为： s3=10c1c2=5(万元) 显然，由于C是最后阶段，故应把剩余金额全部购置C部件， 具体计算结果示如表3-11。 1 1 动态规划应用举例动态规划应用举例 （6 6） 表3-11 阶段3计算结果 s3x3 f3(s3)=d3(s3，x3) x*3 1 2 3 4 5 1 2 3 4 5 0.600 0.840 0.936 0.974 0.990 1 2 3 4 5 例如，当s3=3万元时，则： f3(3)=d(3，3)=10.43=0.936。 1 1 动态规划应用举例动态规划应用举例 （7 7） 第2步：退到阶段2，此时考虑当把钱用于购置B和C部件时， 各应购置多少个部件为最优。 显然，此时B、C应至少各配制1个部件，故 s2c2+c3=3+1=4； 同时，A部件亦至少配备1个部件，故s2102=8。 阶段2计算结果示如表3-12。 1 1 动态规划应用举例动态规划应用举例 （8 8） 表3-12 阶段2计算结果 s2 x2 d2(s2,x2) s3 f3(s3) f2(s2,x2) f2(s2) x*2 4 5 6 7 7 8 8 1 1 1 1 2 1 2 0.8 0.8 0.8 0.8 0.96 0.8 0.96 1 2 3 4 1 5 2 0.600 0.840 0.936 0.974 0.600 0.990 0.840 0.480 0.672 0.749 0.779 0.576 0.792 0.806 0.480 0.672 0.749 0.779 0.806 1 1 1 1 2 1 1 动态规划应用举例动态规划应用举例 （9 9） 例如，当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。 1 1 动态规划应用举例动态规划应用举例 （1010） 可见最优分配资金可获得最高可靠率为0.682，反向跟踪所 购置部件为：A、B、C、分别购置2、1和3件。 表3-13 阶段1的计算结果 s1 x1 d1(s1,x1) s2 f2(s2) f1(s1,x1) f1(s1) x*1 10 1 2 3 0.7 0.91 0.973 8 6 4 0.806 0.749 0.480 0.564 0.682 0.467 0.682 2 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （1 1） 当研究的对象的参量出现不确定状况和受到随机干扰时，这 样在根据某阶段的状态和决策就不能导出下阶段的状态确定 值，其阶段收益函数也不确定，即变为： f(x，u)f(x，u，e) e为随机变量，这时，只能求出阶段期望值来进行选择最优 决策。显然，前向动态规划无法解决，只能应用后向动态规 划算法。 不确定型问题的动态规划算法的一般公式可归纳如下。 设规划中，第末端为0级，始端为n级。这样后向递推从0级 开始进行。令： 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （2 2） V最优函数值 d决策变量 e随机变量 f阶段收益 s状态变量 E期望值 则知： Vn(sn)=max Efn(dn，sn，en)+Vn1(sn1) sn1=tn(dn，sn，en) 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （3 3） 起步 V0(s0)=max Ef0(d0，s0，e0) 下面举例说明。 例3-12生产计划问题。 厂长需决定当年开始两个月内的最优生产计划，已知： 产品生产费用1000元/件 产品销售价格2000元/件 产品储存费用100元/件月 两个月后，产品一次性处理，500元/件 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （4 4） 目前厂内无存货，且生产周期短，当月生产可满足当月订 货需求。 货物需求的概率分布见表3-15。 表3-15 工厂货物需求概率分布 需求概率 0 1 2 3 0.25 0.40 0.20 0.15 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （5 5） 求第1个月应生产多少件产品才能使收益期望值最大（或 损失最少）？ 当第1个月已度过，第2个月应生产多少件产品才能使余 下收益期望最大？ 解 仍需分三个阶段走，首先从二月末开始计算，然后倒退 到二月初和一月初。 1）设时间已到二月末，此时库存水平I0有4种可能性：0、1 、2、3（因需求最大为3）。则针对这几种可能性都必定一 次性处理，其处理价为500元/件，最后计算结果示于表3-16 。 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （6 6） 表3-16 阶段0计算结果 I0 V0 0 1 2 3 0 500 1000 1500 2）设已到二月初，此时，必已知一月末的库存I1，针对不同 的I1（状态），决定每一种可能的生产数量（决策），相应收 益以及售出水平等。对每一种库存水平选择使期望收益最大 的生产数量，其计算结果于表3-17。其中，*为最优决策值。 表3-17 阶段1计算结果 状态 I1 生产 d1 销售 s1 概率 新产生 状态I0 生产 费用 销售 收入 库存 费用 V0 （I0 ） 概 率 $ 期望 收益 0 001.000000000 1 0 1 0.25 0.75 1 0 -1000 -1000 0 2000 -100 0 500 0 -150 750 600* 2 0 1 2 0.25 0.40 0.35 2 1 0 -2000 -2000 -2000 0 2000 4000 -200 -100 0 1000 500 0 -300 160 700 560 3 0 1 2 3 0.25 0.40 0.20 0.15 3 2 1 0 -3000 -3000 -3000 -3000 0 2000 4000 6000 -300 -200 -100 0 1500 1000 500 0 -450 -80 280 450 200 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （7 7） 例如，当库存水平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元。 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （8 8） 库存费用为0。 转移到0阶段的收益V0（I0）为0。 概率收益值为（40002000）0.35=700元。 同时也可算出当s1=0和s1=1时的概率收益分别为300和160 ，其最后知I1=0，d1=2时的期望收益值为（700300+160） =560（元）。 同理知：d1=0 时，总期望收益为0。 d1=1时，总期望收益为600。 d1=3时，总期望收益为200。 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （9 9） 最后知，当状态I1=0时，最优决策d1*(0)=1，V1(0)=600，当I1 为其它值时，计算结果示于表3-18。 表3-18 I1 V1（I1） D1*(I1) 0 1 2 3 600 1600 2560 3200 1 0 0 0 3)退到一月初，此时初始存货为0，即I2=0，其计算方式同前 ，其结果示如表3-19。 表3-19 阶段2计算结果（I2=0） 状态 I2 生产 d2 销售 s2 概率 新产生 状态I1 生产 费用 销售 收入 库存 费用 V1 （I1 ） 概率 $ 期望 收益 0 001.000000600600600 1 0 1 0.25 0.75 1 0 -1000 -1000 0 2000 -100 0 1600 600 125 1200 1325 2 0 1 2 0.25 0.40 0.35 2 1 0 -2000 -2000 -2000 0 2000 4000 -200 -100 0 2560 1600 600 90 600 910 1600* 3 0 1 2 3 0.25 0.40 0.20 0.15 3 2 1 0 -3000 -3000 -3000 -3000 0 2000 4000 6000 -300 -200 -100 0 3200 2560 1600 600 -25 544 500 540 1559 2 2 不确定型问题的动态规划算不确定型问题的动态规划算 法法 （1010） 综合结果知，当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.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结果决策树 级数 1 0 2 1 0 0 1 0 0 0 1 0 0 0 1 状态 决策 事件 结果 状态 决策 事件 结果 状态 开始 存货 生产 概率 需求 需求 存货 生产 概率 需求 需求 存货 3 3 总结总结动态规划的特点动态规划的特点（1 1） 一、动态规划由于具有下述优点而得到广泛的应用 1对目标函数的形式不加限制。 2对于约束条件容易处理。 3所得结果，在理论上属绝对最优。（对概率型，属 概率意义上绝对最优） 4运算过程简单。 5计算结果为一个“解族”，即获得了整个决策树。这样 ，当由于干扰使运动过程离开了原最优轨迹，则可在新 状态下沿已计算好的另一条轨迹行进。 10 8 9 7 6 5 4 3 2 1 16 4 4 2 3 6 13 6 17 6 6 19 10 3 7 10 9 8 8,9 6 12 9 10 9 8 9 5 4 6 8 4 4 4 10