运筹学-动态规划讲述.ppt

第16章 动态规划 动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。该方法由美国数学家贝尔曼（R.E.Bellman）等人在20世纪50年代初提出的 §1 多阶段决策问题 多阶段决策问题例子： 例16-1 最短路径问题：求图16-1中从A到F的最短路径。 将问题可分为五个阶段 每个阶段都要作出一个决策，决定向哪个点前进一步。各阶段的决策有机的联系着，本阶段的决策影响着下一阶段的决策，以至于影响整体效果，决策者在做决策时，不应尽考虑本阶段最优，还应考虑对最终目标的影响。各阶段的决策形成一个决策序列，通常称之为一个策略，不同的策略，其效果也不同。现在的问题就是要在允许的策略中，求出A到F的距离最短的策略。 第一阶段：从到A或B; 第二阶段：从B到C; 第三阶段：从C到D; 第四阶段：从D到E; 第五阶段：从E到F; 可将该问题按年划分为五个阶段：第一阶段即第一年；第二阶段即第二年；第三阶段即第三年；第四阶段即第四年；第五阶段即第五年。设开始时完好机器数量为x1 ，第 k年能投入生产的机器数为xk，第 k年高负荷下工作的机器数为 uk 台，效益为 Rk ，则 例16-3部件的生产计划问题：某车间每月底要为下一个月提供出一定数量的部件给组装车间，各月份中生产这种部件所需工时不同，生产出来多余的部件可以存入库中，但库房的最高贮量为H=9，求某6个月中每月生产多少部件，才能使消耗的总工时最少？最小工时是多少？各月的需求量与单位工时如下表： 表7-1 ? 将该问题按月份划分为六个阶段， Sk为第k月开始时的库存， uk为第k 的生产量 。 例16-4 原料分配问题：利用已有的12吨原料制造A、B 两种产品，已知每制造一吨 A产品需要原料4吨，每制造一吨 B 产品需要原料2吨，而两种产品在市场上的价格分别为每吨8千元和1万元，求如何安排生产计划能使总效益最大？ 可将分配A、B两产品的产量看作两个阶段：第一阶段：确定生产A产品多少吨；第二阶段：确定生产B产品多少吨。求出使总效益最大的决策序列。 例16-5人员派谴问题：向三个售货区域派谴四名推销员，各区人数及效益如下表： 该问题可按区域分为三个阶段：第一阶段：确定向1区派几名推销员；第二阶段：确定向2区派几名推销员；第三阶段：确定向3区派几名推销员。求出使总效益最大的策略。 问如何派谴人员能使总效益最高？ 例16-6货物装载问题：某海轮的总装载能力为 w 千吨（不妨设w=0,1,2, …,18千吨）需装载四种货物，规定海轮上每种货物不超过2件，各种货物的单位重量，单位运费如下表，问怎样装这些货物，才能使总运费最大？ 表8-6 §2 动态规划的基本概念与基本原理 2.1?? 动态规划的基本概念 最短路问题中，每个阶段状态表示该阶段初始点的集合。 状态集合用Sk表示， S1={B1，B2} 指标函数应具有可分离性，一般的形式有： 5.指标函数（Return Function） 指标函数（最大收益函数-Maximum Return Function ，或最小成本函数-Minimum Cost Function）是反映策略优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的函数。 -表示初始状态为s1 采取策略p1,n时全过程的指标函数 -第k阶段状态为sk 采取策略pk,n时后部子过程的指标函数 6.最优策略和最优轨线 称为后部子过程中的最优策略。 称为全过程中的最优策略。 现在结合解决最短路线问题来介绍动态规划方法的基本思想，最短路线有一个重要特性： 如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达终点G的这条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。 16.2 动态规划的基本定理和基本方程 贝尔曼（R.E.Bellman）最优性原理如下： 作为整个过程的最优策略具有这样的性质： 即无论过去的状态和决策如何，对于先前决策所形成的状态而言，其后的所有决策应构成最优策略。 一般地： 人们逐步认识到： 对于不同类型问题所建立的严格定义的动态规划模型,必须对相应的最优性原理给以必要的验证。即是说，最优性原理不是对任何决策过程都普遍成立的。而且，“最优性原理”与动态规划基本方程并不是无条件等价的，两者之间也不存在确定的蕴含关系。 反映动态规划基本方程的是最优性定理，它是策略最优性的充要条件。 最优性原理仅仅是策略最优性的必要条件，它是最优性定理的推论。 动态规划的基本方程或者最优性定理作为动态规划的理论基础。 动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编号为k=1,…,n,初始状态为s1 ,允许策略 是最优策略