《运筹学-动态规划（三）（名校讲义》由会员分享，可在线阅读，更多相关《运筹学-动态规划（三）（名校讲义（27页珍藏版）》请在金锄头文库上搜索。
1、第二十讲 动态规划（三）,1 动态规划应用举例 2 不确定型问题的动态规划算法 3 总结动态规划的特点,1 动态规划应用举例 （1）,动态规划是一种方法，而不是算法。即对复杂问题需加以分析才能应用动态规划的迭代算法进行求解，而且其中具有很大技巧性。动态规划目前已广泛用于旅行路径问题、资源分配问题、生产计划问题、设备更新问题、排序问题及复合系统可靠性问题等等。 一、复合系统可靠性问题 例3-10某复合系统由三个部分串联而成，其示意图见图3-15。 已知：,图3-15,1 动态规划应用举例 （2）,A、B、C相互独立 各部分的单件故障率分别为：P1=0.3，P2=0.2，P3=0.4 显然，若各部
2、分只有一个部件时其总可靠率f为： f=(10.3)(10.2)(10.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环节k部件单价 Pk环节k单件的故障率 显然，第k环节本身的可靠率为： dk(sk，xk)=,1 动态规划应用举例 （4）,状态转移方程：sk+1=skckxk 令：fk(
3、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 动态规划应用举例 （5）,第1步：考虑购置部件C的数量。 因为A、B至少各购一件（否则，整个可靠性为零）。则用于购置C部件的最高金额为： s3=10c1c2=5(万元) 显然，由于C是最后阶段，故应把剩余金额全部购置C部件，具体计算结果示如表3-11。,1 动态规
4、划应用举例 （6）,表3-11 阶段3计算结果,例如，当s3=3万元时，则： f3(3)=d(3，3)=10.43=0.936。,1 动态规划应用举例 （7）,第2步：退到阶段2，此时考虑当把钱用于购置B和C部件时， 各应购置多少个部件为最优。 显然，此时B、C应至少各配制1个部件，故 s2c2+c3=3+1=4； 同时，A部件亦至少配备1个部件，故s2102=8。 阶段2计算结果示如表3-12。,1 动态规划应用举例 （8）,表3-12 阶段2计算结果,1 动态规划应用举例 （9）,例如，当s2=8时，可有2个选择方案： 令x2=1，得f2(8，1)=d2(8，1)f3(831)=(1P2)
5、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 动态规划应用举例 （10）,可见最优分配资金可获得最高可靠率为0.682，反向跟踪所 购置部件为：A、B、C、分别购置2、1和3件。,表3-13 阶段1的计算结果,2 不确定型问题的动态规划算法 （1）,当研究的对象的参量出现不确定状况和受到随机干扰时，这样在根据某阶段的状态和决策就不
6、能导出下阶段的状态确定值，其阶段收益函数也不确定，即变为： f(x，u)f(x，u，e) e为随机变量，这时，只能求出阶段期望值来进行选择最优决策。显然，前向动态规划无法解决，只能应用后向动态规划算法。 不确定型问题的动态规划算法的一般公式可归纳如下。 设规划中，第末端为0级，始端为n级。这样后向递推从0级开始进行。令：,2 不确定型问题的动态规划算法 （2）,V最优函数值 d决策变量 e随机变量 f阶段收益 s状态变量 E期望值 则知： Vn(sn)=max Efn(dn，sn，en)+Vn1(sn1) sn1=tn(dn，sn，en),2 不确定型问题的动态规划算法 （3）,起步 V0(s
7、0)=max Ef0(d0，s0，e0) 下面举例说明。 例3-12生产计划问题。 厂长需决定当年开始两个月内的最优生产计划，已知： 产品生产费用1000元/件 产品销售价格2000元/件 产品储存费用100元/件月 两个月后，产品一次性处理，500元/件,2 不确定型问题的动态规划算法 （4）,目前厂内无存货，且生产周期短，当月生产可满足当月订货需求。 货物需求的概率分布见表3-15。,表3-15 工厂货物需求概率分布,2 不确定型问题的动态规划算法 （5）,求第1个月应生产多少件产品才能使收益期望值最大（或损失最少）？ 当第1个月已度过，第2个月应生产多少件产品才能使余下收益期望最大？ 解
8、 仍需分三个阶段走，首先从二月末开始计算，然后倒退到二月初和一月初。 1）设时间已到二月末，此时库存水平I0有4种可能性：0、1、2、3（因需求最大为3）。则针对这几种可能性都必定一次性处理，其处理价为500元/件，最后计算结果示于表3-16。,2 不确定型问题的动态规划算法 （6）,表3-16 阶段0计算结果,2）设已到二月初，此时，必已知一月末的库存I1，针对不同的I1（状态），决定每一种可能的生产数量（决策），相应收益以及售出水平等。对每一种库存水平选择使期望收益最大的生产数量，其计算结果于表3-17。其中，*为最优决策值。,表3-17 阶段1计算结果,2 不确定型问题的动态规划算法 （
9、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 不确定型问题的动态规划算法 （8）,库存费用为0。 转移到0阶段的收益V0（I0）为0。 概率收益值为（40002000）0.35=700元。 同时也可算出当s1=0和s1=1时的概率收益分别为300和
10、160，其最后知I1=0，d1=2时的期望收益值为（700300+160）=560（元）。 同理知：d1=0 时，总期望收益为0。 d1=1时，总期望收益为600。 d1=3时，总期望收益为200。,2 不确定型问题的动态规划算法 （9）,最后知，当状态I1=0时，最优决策d1*(0)=1，V1(0)=600，当I1为其它值时，计算结果示于表3-18。,表3-18,3)退到一月初，此时初始存货为0，即I2=0，其计算方式同前，其结果示如表3-19。,表3-19 阶段2计算结果（I2=0）,2 不确定型问题的动态规划算法 （10）,综合结果知，当I2=0时，d2*(I2)=2，V2(I2)=16
11、00。 最后结果可归纳为决策树，具体示如图3-17。 从图3-17看出，从期望收益可找出一月初的最优决策，然而找不出向后走的确切轨迹，而需根据以后发生的事件从决策树中找出相应决策。根据决策树，便可回答前面提的2个问题： 一月初最优期望值收益决策为： 决策d2=2，期望收益为1600元。 当时间指向一月末（或二月初），此时决策取决于一月份销售量，即一月末存货量I1。 当I1=0，取决策d1=1。 当I1=1，2时，决策d1全为0。,3 总结动态规划的特点（1）,一、动态规划由于具有下述优点而得到广泛的应用 1对目标函数的形式不加限制。 2对于约束条件容易处理。 3所得结果，在理论上属绝对最优。（
12、对概率型，属概率意义上绝对最优） 4运算过程简单。 5计算结果为一个“解族”，即获得了整个决策树。这样，当由于干扰使运动过程离开了原最优轨迹，则可在新状态下沿已计算好的另一条轨迹行进。,例如，在图3-1中，从站到站的最优轨迹为。若旅客由于疏忽或其它原因，从走到了，则此时的余下路程应为。,3 总结动态规划的特点（2）,二、动态规划由于尚存下述问题而使其应用受到一定限制 1动态规划是一种方法，而不是算法。因此，在列写具体问题的递推公式时，必有很大的技巧性。 2当状态变量取值和阶段数太大时，会产生计算量太大的“维数灾难”。 3选择状态变量时要十分小心，一定要满足三性：可描述受控过程的演变性；过程的过去历史只能通过当前状态来影响未来的无后效性；状态值总可直接或间接得到的可知性。,
