运筹学教程五动态规划素材.ppt

《运筹学教程五动态规划素材.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第五章动态规划不要过河拆桥2动态规划Dynamicprogramming五十年代贝尔曼(B.E.Bellman)为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式5.1动态规划的最优化原理及其算法5.1.1求解多阶段决策过程的方法例5.1.1最短路问题3决策树法可以枚举出20条路径，其中最短的路径长度为164例5.1.1最短路问题表现为明显的阶段性一条从A到B的最短路径中的任何一段都是最短的每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关因此我们可以从B向回搜索最短路标记法如何找出最短路径55.1.2动态规划的

2、基本概念及递推公式1、基本概念1）阶段；把多阶段决策问题分为若干个相互联系的阶段，常用k表示2）状态：每一阶段开始时所处的状态。某一阶段某一状态用状态变量sk表示，第k阶段的所有状态集合用Sk表示，各阶段所有状态集合用S表示，则skSkS，动态规划中的状态必须满足无后效性。3）决策：某一阶段k某一状态sk所作出的决策用决策变量xk（sk）表示，第k阶段状态sk的允许决策集合用Dk（sk）表示，第k阶段各状态的允许决策集合用Dk表示，所有各阶段各状态的允许决策集合用D表示。则有xk（sk）Dk（sk）DkD4）策略：指某一阶段某一状态到终点的顺序排列的决策组合的

3、集合。用Pk（sk）={xk（sk），xk-1（sk-1），…，x1（s1）}表示从第k阶段状态sk出发到终点的一个子策略。从第k阶段状态sk出发到终点的允许策略集合为P。则Pk（sk）P。5）状态转移方程：反映相邻两个阶段的状态和决策变量之间的相互关系sk-1=Tk[sk，xk（sk）]=g(sk,xk)65.1.2动态规划的基本概念及递推公式6）直接效果函数：它是状态变量sk和决策变量xk（sk）的函数，记为：dk[sk，xk（sk）]。7）总效果函数：从第k阶段状态sk出发到终点的子策略Pk（sk）的函数。记为：Vk=Vk[Pk（sk）]8）最优效果函数：表示在

4、某一阶段某一状态下，采取最优策略后到终点的最优效果值。记为2、最优化原理和动态规划递推关系1、最优化原理：最优策略的子策略也是最优的。2、递推关系：73、动态规划的步骤1)划分阶段将所研究的问题划分为K个阶段，并对阶段进行编号。一般按逆向编号；2)确定状态变量sk正确确定状态变量sk，使它既能描述过程的演变又能满足无后效性；3)确定决策变量xk（sk）及其允许的决策集合Dk（sk）；4)写出状态转移方程sk-1=g(sk,xk)；5)确定直接效果函数6)列出最优指标函数的递推关系式7)确定边界条件85.2动态规划模型举例5.2.1资源分配问题例5.2.1某公司有4个推销

5、员在北京、上海和广州三个市场推销货物，这三个市场里推销人员数与收益的关系如表5.2.1所示，试作出使总收益最大的分配方案。表5.2.1推销人员数与收益推销员市场01234北京2032475766上海4050607182广州5061728483解1、划分阶段分成3个阶段，即K=3，并按逆向编号，广州k=1，上海k=2，北京k=3，分配推销员的优先顺序为北京—上海—广州；2、确定状态变量sk状态变量sk表示第k阶段初尚未分配的推销员数。显然有s3=4，s2和s1的可能取值范围为0—4。93、确定决策变量xk决策变量xk表示分配给第k阶段市场的推销员数。显然有，xksk；4

6、、确定状态转移方程根据前面定义的状态变量sk和决策变量xk的意义，可得其状态转移方程为sk-1=sk-xk；5、确定直接效果函数dk(sk，xk)它表示第k阶段初有推销员数sk，分配给第k市场xk个推销员时所产生的直接效益。这些效益指标由表5.2.1给出；6、最优指标函数由于三个市场的总效益等于三个市场的效益之和，即其指标函数为累加形式。所以最优指标函数为7、边界条件f0(s0)=0。各阶段计算过程见教材P（138—139）105.2.2项目选择问题某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额wk及其投资后的收益vk如右表所示。投资总额为30万元，问如何

7、选择项目才能使总收益最大。上述问题的静态规划模型如下：这是一类0-1规划问题该问题是经典的旅行背包问题(Knapsack)该问题是NP-complete11解：设项目选择的顺序为A,B,C,D;1、阶段k=1,2,3,4分别对应D,C,B,A项目的选择过程2、第k阶段的状态sk，代表第k阶段初尚未分配的投资额3、第k阶段的决策变量xk,，代表第k阶段项目是否入选4、状态转移方程为sk–1=sk–wkxk5、直接效益dk(sk,xk)=vk或06、总效益递推公式该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策