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

第七章动态规划7.1

多阶段决策过程的最优化7.2

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

多阶段决策问题动态规划的研究对象是多阶段决策问题。对于多阶段决策问题，根据问题本身的特点可以将其求解过程划分为若干个相互联系的阶段。每个阶段都有若干个方案可供选择，因此每一阶段都需要做出决策。各个阶段确定的决策构成一个决策序列，称为一个策略．在所有可供选择的策略中，对应效果最好的策略称为最优策略。7.1.2

多阶段决策问题举例（1）工厂生产过程（2）设备更新问题（3）连续生产过程的控制问题（1）资源分配问题（2）运输网络问题与时间有关与时间无关7.1.3

动态规划求解的多阶段决策问题的特点一般来说，系统在某个阶段的状态可能与系统过去经历的状态和决策有关．能用动态规划方法求解的多阶段决策问题必须具有“无后效性”的特点。所谓“无后效性”，即过去的历史不影响未来的发展．过往的历史仅仅体现在本阶段的初始状态上．例

最短线路问题从地到地铺设一条管道，中间经过三个中间站；第一中间站可选或，第二中间站可选、或，第三中间站可选或，问如何选择可使管线最短？7.1.3

动态规划方法导引枚举法局部最优法（贪婪算法）（动态规划的逆序法）：1.先确定第四个阶段的最短子路线记作：其中，表示从第k阶段的起点X

到终点E的最短路线.（分四个阶段）动态规划法2.再确定最后两个阶段的最短子路线3.确定后三个阶段的最短子路线3.综合四个阶段的最短子路线分析：第四阶段的最短子路线三四阶段的最短子路线二三四阶段的…一至四阶段的…√√√√动态规划法的基本思路:把复杂问题分解为一系列同类型的便于求解的子问题动态规划法的特点/优点:整体最优蕴含阶段最优例

设备分配问题100台相同的机器被分配来加工两种不同的产品A和B；已知：加工A产品时，机器每周的损坏率为，加工B产品时，机器每周的损坏率为；生产A产品时，每台每周的收益为1000元，B产品每台每周的收益为700元；问采取怎样的分配方案可使四周内总收益最大？第一阶段（即第一周）机器总台数为设用于加工A产品的机器台数为台求得第一阶段的总收益为则用于加工B产品的机器台数为台动态规划的顺序法：第二阶段（即第二周）机器总台数为设该阶段用于加工A产品的机器台数为台求得该阶段的总收益为则用于加工B产品的机器台数为台第三阶段（即第三周）机器总台数为设该阶段用于加工A产品的机器台数为台求得该阶段的总收益为则用于加工B产品的机器台数为台第四阶段（即第四周）机器总台数为设该阶段用于加工A产品的机器台数为台求得该阶段的总收益为则用于加工B产品的机器台数为台综上所述每一阶段开始时机器总台数为设该阶段用于加工A产品的机器台数为台该阶