ch5动态规划讲解.pptVIP

动态规划应用举例 i=1 i=2 i=3 R C R C R C 1 0.6 1 0.7 3 0.5 2 2 0.8 2 0.8 5 0.7 4 3 0.9 3 0.9 6 0.9 5 解：可看作一个三阶段动态规划问题 （非线性规划） 设备的总可靠性 阶段变量k： 状态变量Sk： 决策变量xk： 状态转移方程：  阶段指标: 动态规划应用举例 k=1,2,3；(表示元件号) 表示设计k号元件前剩有的资金数 选择k号元件的并联数 第k号元件的并联数为 时的可靠性 则递推方程为： 动态规划应用举例 注：剩余的资金至少可以买一个。 下面从最后一个阶段开始向前逆推计算： k=3时： 动态规划应用举例 动态规划应用举例(填表) s3 x3 R3(x3) S4 f4(s4) R3f3 f3 x3* 2 3 4 5 6 动态规划应用举例 s3 x3 R3(x3) S4 f4(s4) R3f4 f3 x3* 2 1 0.5 0 1 0.5 0.5 1 3 1 0.5 1 1 0.5 0.5 1 4 1 2 0.5 0.7 2 0 1 1 0.5 0.7 0.7 2 5 1 2 3 0.5 0.7 0.9 3 0 1 1 1 1 0.5 0.7 0.9 0.9 3 6 1 2 3 0.5 0.7 0.9 4 2 1 1 1 1 0.5 0.7 0.9 0.9 3 （填表）(k=2时) S2 x2 R2 S3 f3 R2f3 f2 x2* 5 1 6 1 7 1 2 8 1 2 3 9 1 2 3 (k=2时) S2 x2 R2 S3 f3 R2f3 f2 x2* 5 1 0.7 2 0.5 0.35 0.35 1 6 1 0.7 3 0.5 0.35 0.35 1 7 1 2 0.7 0.8 4 2 0.7 0.5 0.49 0.4 0.49 1 8 1 2 3 0.7 0.8 0.9 5 3 2 0.9 0.5 0.5 0.63 0.4 0.45 0.63 1 9 1 2 3 0.7 0.8 0.9 6 4 3 0.9 0.7 0.5 0.63 0.56 0.45 0.63 1 (k=1时) S1 x1 R1 S2 f2 R1f2 f1 x1* 10 1 2 3 0.6 0.8 0.9 9 8 7 0.63 0.63 0.49 0.378 0.504 0.441 0.504 2 最优安排为： 应用：生产存储问题，背包问题，货郎担问题，求解静态规划问题等等 动态规划没有统一的公式和求解方法，需具体分析题目。 动态规划应用举例 动态规划应用举例 k=4时： f4(S4)=max{5x4+15S4+f5(S5)} 0?x4?2S4-400 =max{5x4+15S4} =25S4-2000 (取x4*=2S4-400) k=3时： f3(S3)=max{5x3+15S3+f4(S4)} 0?x3?S3 =max{5x3+15S3 +25[-0.4x3+0.8S3]-2000} = max{-5x3+35S3 -2000 } = 35S3 -2000 (取x3*=0) 动态规划应用举例 k=2时： f2(S2)=max{5x2+15S2+f3(S3)} 0?x2?S2 =max{5x2+15S2 +35[-0.4x2+0.8S2]-2000} = max{-9x2+43S2-2000 } = 43S2-2000 (取x2*=0) 动态规划应用举例 k=1时： f1(S1)=max{5x1+15S1+f2(S2)} 0?x1?S1 =max{5x1+15S1 +43[-0.4x1+0.8S1]-2000} = max{-12.2x1+49.4S1 -2000}