动态规划(理论部分).pptVIP

(5)状态转移方程 式中的“opt”（optimization）可根据具体问题的实际意而取min或max。 例3：逆推解法求解下面问题: 令最优值函数f k(sk)表示为第k阶段的初始状态为sk时，从第k阶段到第3阶段所得到的最大值。 例４：正推解法求解下面问题: 作业用动态规划法求解： k = n－1时，动态规划的基本方程是 因所有的 都已经求出，因此可以根据 就阶段n-1每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。 因所有 都已求出，因此可以根据 就阶段n-2每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。 k = n－2时，动态规划的基本方程是 k=1时，动态规划的基本方程是 由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1) 就阶段1每个可能状态s1 ,求条件最优决策及相应的条件最优目标函数值 f1(s1) . 依次下去 …………. 最后，顺序地求出最优目标值、最优策略和最优路线 解 该问题可以作为三段决策过程。对A、B、C三个部门分配资金分别形成1，2，3三个阶段。sk表示给部门k分配资金时拥有的资金数。uk表示给部门k分配的资金数（万元为单位）。状态转移方程是 sk+1=sk- uk。目标函数是阶段效应求和。 例2：某公司拟将5百万元资金投放下属A、B、C三个部门，其中A与C的投资额不超过4百万元，B的投资额不超过3百万元，C投资额至少是1百万元。各部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以百万元为单位）。 15 11 8 4 C 12 10 5 0 B 12 10 6 3 0 A 收 益 （万元） 4 3 2 1 投放资金(万元) 0 递归方程为： （1）K=3时（第3阶段） 注意到C的投资额不超过4百万元， 至少是1百万元. 允许状态集合 S3＝{ 1, 2, 3, 4 }, 即用剩余额S3＝1，2，3，4 投资部门C，得到的收益为： （2） K=2时（第2阶段） 注意到C的投资额至少是1百万元， 允许状态集合 S2＝{ 1, 2, 3, 4, 5 }, 下面是各种可能方案的列表 3 1 3 2 2 2 2 1 2 3 1 3 1 2 1 1 1 4 0 4 0 3 0 2 0 1 B C B C B C B C B C s2＝ 5 s2＝ 4 s2＝ 3 s2＝ 2 s2＝1 故 （3）K=1时 （第1阶段） S1 ={ 5 } 允许决策集合 D1(S1)＝{ 0, 1, 2, 3, 4}, 应用顺序追踪可知：最优方案有两个： 方案 1： 方案 2： 最大收益都为21百万元。 解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s1，s2，s3，s4。并记s1＝c；令变量x1，x2，x3为决策变量；各阶段指标按乘积方式结合。即令: 设: s3= x3, s3+ x2=s2, s2+ x1=s1=c 则有：x3=s3, 0≤x2≤s2, 0≤x1≤s1=c 即状态转移方程为： s3=s2－x2, s2 =s1－x1 由逆推解法， 即最优解x3＊=s3, 由　　　　　　　　　　,得　　　　 　 和　　　（舍去） 又　　　　　　　　，而　　　　　　　　　 故为　　　　　极大值点。 所以　　　　　　　 ，即　　　　　最优解。 求导并令导数等于0可得：　　　，故 由于s1=c，∴　　　　， 由s2 =s1－x1＊，∴　　　　　　　, 由s3 =s2－x2＊，∴　　　　　　， 因此最优解为：　　　　，　　　　，　　　　， 最大值为： 解：设s4＝c，决策变量仍为x1，x2，x3；最优值函数f k(sk+1)表示为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的最大值。 设: s2= x1, s2+ x2=s3, s3+ x3=s4=c 则有：x1=s2, 0≤x2≤s3, 0≤x3≤s4=c 即状态转移方程为： s2=s3－x2, s3=s4－x3 由顺推解法，