第章 动态规划.pptVIP

§3　动态规划的应用(1) 当n=1时， 最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。 * x1 s1 f1(s1)=P1(x1) ·f2*(s1-x1) f1*(s1) x1* 0 1 2 2 0．064 0．060 0．072 0．060 1 §4　动态规划的应用(2)* 一、连续确定性动态规划 对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。 * §4　动态规划的应用(2)* 机器负荷分配问题 例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70％的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。 * §4　动态规划的应用(2)* 解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。 状态转移方程为 sk+1=0.7xk+0.9(sk-xk) 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 ，其 中k=1,2,3,4,5。 f6(s6)=0。 * §4　动态规划的应用(2)* 第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5， 于是有f5(s5)=8s5。 第4阶段： * §4　动态规划的应用(2)* 同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ， f4(s4)=13.6s4。 对前几个阶段依次类推，可得 x3*=s3 f3(s3)=17.5s3， x2*=0 f2(s2)=20.75s2， x1*=0 f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s1 ＝23720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产， 后三年应把年初完好机器完全投入高负荷生产。 * §4　动态规划的应用(2)* 下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有: * §4　动态规划的应用(2)* 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得 * §4　动态规划的应用(2)* 显然，由于固定了终点的状态，x5的取值受到了 约束。因此有 类似的， 容易解得 ，f4(s4)=21.7s4-7500。 * §4　动态规划的应用(2)* 依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500