第一节多阶段决策过程的最优化

1、第七章第七章 动态规划动态规划7.17.1 多阶段决策过程的最优化7.27.2 动态规划的基本概念和求解思路7.3 7.3 离散型动态规划问题7.4 7.4 连续型动态规划问题7.5 7.5 动态规划方法应用举例7.1 多阶段决策过程的最优化动态规划是运筹学的重要分支，他的研究对象是多阶段决策问题。所谓多阶段决策问题，是指问题本身可以按照时间、空间等划分为若干个相互联系的阶段动态规划模型的分类：连续型 与 离散型确定型 与 随机型时间的 与 空间的 实际问题常常是复合的。本章主要研究动态与静态确定型的决策过程。7.17.1.1.1 多阶段决策问题动态规划的研究对象是多阶段决策问题。对于多阶段决

2、策问题，根据问题本身的特点可以将其求解过程划分为若干个相互联系的阶段。每个阶段都有若干个方案可供选择，因此每一阶段都需要做出决策。各个阶段确定的决策构成一个决策序列，称为一个策略在所有可供选择的策略中，对应效果最好的策略称为最优策略。7.17.1.2.2 多阶段决策问题举例（1）工厂生产过程（2）设备更新问题（3）连续生产过程的控制问题（1）资源分配问题（2）运输网络问题 与时间有关与时间无关7.17.1.3.3 动态规划求解的多阶段决策问题的特点 一般来说，系统在某个阶段的状态可能与系统过去经历的状态和决策有关 能用动态规划方法求解的多阶段决策问题必须具有“无后效性”的特点。 所谓“无后效性

3、”，即过去的历史不影响未来的发展 过往的历史仅仅体现在本阶段的初始状态上例例 最短线路问题A1B2B1C2C3C1D2DE3333444455666774从 地到 地铺设一条管道，中间经过三个中间站；第一中间站可选 或 ，第二中间站可选 、 或 ，第三中间站可选 或 ，问如何选择可使管线最短？A1B2B1C2C3C1D2DE7.17.1.3.3 动态规划方法导引枚枚举举法法A12BB 123CCC 12DD E123CCC 12DD 12DD 12DD 12DD 12DD EEEEEEEEEEE171916172017171914151815 221ABCDE局部最优法局部最优法A1B2B1C

4、2C3C1D2DE3333444455666774（贪婪算法）（贪婪算法）（动态规划的逆序法）：1.先确定第四个阶段的最短子路线1:DE2:DE1(,)3d DE 2(,)4d DE 记作：4142()3()4fDfD 其中， 表示从第k 阶段的起点 X 到终点E 的最短路线.()kfXA1B2B1C2C3C1D2DE3333444455666774（分四个阶段）动态规划法动态规划法2.再确定最后两个阶段的最短子路线11:CDE11411242(,)()min(,)()d CDfDd CDfD 313233()()()fCfCfC 53min64 8 21412242(,)()min(,)()

5、d CDfDd CDfD 43min44 7 31413242(,)()min(,)()d CDfDd CDfD 73min34 7 21:CDE32:CDE31()8fC 32()7fC 33()7fC A1B2B1C2C3C1D2DE33334444556667743.确定后三个阶段的最短子路线113112321333(,)()min(,)()(,)()d B CfCd B CfCd B CfC 2122()()fBfB 68min 6777 13 121:BCDE21()13fB 22()10fB 213122322333(,)()min(,)()(,)()d B CfCd B CfCd

6、 B CfC 58min 3747 10 221:BCDEA1B2B1C2C3C1D2DE33334444556667743.综合四个阶段的最短子路线121222(,)()min(,)()d A BfBd A BfB 1()fA 313min410 14 221:ABCDE1()14fA A1B2B1C2C3C1D2DE3333444455666774分析：2211:()14ABCDEfA 1212122122:()13:()10BCDEfBBCDEfB 141242:()3:()4DEfDDEfD 113121323233:()8:()7:()7CDEfCCDEfCCDEfC 第四阶段的最短

7、子路线三四阶段的最短子路线二三四 阶段的一至四 阶段的动态规划法的基本思路:把复杂问题分解为一系列同类型的便于求解的子问题动态规划法的特点/ /优点:整体最优蕴含阶段最优例例 设备分配问题100台相同的机器被分配来加工两种不同的产品A 和B；已知：11015加工A产品时，机器每周的损坏率为 ，加工B产品时，机器每周的损坏率为 ；生产A产品时，每台每周的收益为1000元，B产品每台每周的收益为700元；问采取怎样的分配方案可使四周内总收益最大？第一阶段（即第一周）第一阶段（即第一周）机器总台数为1100s 设用于加工A产品的机器台数为 台求得第一阶段的总收益为则用于加工B产品的机器台数为 台1x

8、1100 x g sxxsx 111111(,)1000700()11700300sx 动态规划的顺序法：第二阶段（即第二周）第二阶段（即第二周）机器总台数为2s 设该阶段用于加工A产品的机器台数为 台求得该阶段的总收益为则用于加工B产品的机器台数为 台gsxxsx 222222(,)1000700()22700300sx 111()10sx 1115sx 2x22sx 11911010sx 第三阶段（即第三周）第三阶段（即第三周）机器总台数为3s 设该阶段用于加工A产品的机器台数为 台求得该阶段的总收益为则用于加工B产品的机器台数为 台gsxxsx 333333(,)1000700()337

9、00300sx 221()10sx 2215sx 3x33sx 22911010sx 第四阶段（即第四周）第四阶段（即第四周）机器总台数为4s 设该阶段用于加工A产品的机器台数为 台求得该阶段的总收益为则用于加工B产品的机器台数为 台gsxxsx 444444(,)1000700()44700300sx 331()10sx 3315sx 4x44sx 33911010sx 综上所述综上所述每一阶段开始时机器总台数为1191 (2,3,4)1010iiissxi 设该阶段用于加工A产品的机器台数为 台该阶段的总收益为则用于加工B产品的机器台数为 台iiiiig sxsx (,)700300ixiisx 1100s