第8章动态规划基本方法例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g＝g(u)，这时机器的年完好率为a（0<a<1)；在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h＝h(v)，这时机器的年完好率为b（a<b<1）。假定开始生产时完好的机器数量为s，要求制定一个五年计划，在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总产量最高。多阶段决策问题和前面遇到的决策问题不同，它是和时间有关的，状态（所处自然状况和客观条件）是随着决策进程而变化的，故有“动态”的含义。与时间有关的活动过程称为动态过程，处理它的方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的处理方法称为静态规划。第2节动态规划的基本概念和基本方程描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内，称为允许决策集，记为Dk(sk)。（5）状态转移方程动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数。2.2动态规划的基本方程于是，得基本方程例最短路问题现在把动态规划法的步骤归纳如下：例：机器负荷问题某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为g=8u,这时机器的年完好率为a=0.7。在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h=5v,这时机器的年完好率为b=0.9。假定开始生产时完好的机器数量为1000，要求制定一个五年计划，在每年开始时决定机器在两种不同负荷下生产的数量，使五年产品的总产量最高。状态转移方程sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk当k=3时：第4节动态规划和静态规划的关系基本方程为fk(sk)=max{vk(xk)+fk+1(sk+1)}k=3,2,10≤xk≤sk⁄ak例用动态规划法求解maxz=x1.x22.x3x1+x2+x3=cxi≥0i=1,2,3当k=2时: