《运筹学》课件运筹五.ppt
《《运筹学》课件运筹五.ppt》由会员分享,可在线阅读,更多相关《《运筹学》课件运筹五.ppt(28页珍藏版)》请在文库网上搜索。
1、1第五章第五章 动态规划动态规划不要过河拆桥不要过河拆桥2动态规划动态规划 Dynamic programming五十年代贝尔曼五十年代贝尔曼(B.E.Bellman)为代表的研究成果为代表的研究成果属于现代控制理论的一部分属于现代控制理论的一部分以长远利益为目标的一系列决策以长远利益为目标的一系列决策最优化原理,可归结为一个递推公式最优化原理,可归结为一个递推公式5.1 动态规划的最优化原理及其算法5.1.1 求解多阶段决策过程的方法求解多阶段决策过程的方法例例5.1.1 最短路问题最短路问题3 决策树法决策树法可以枚举出可以枚举出20条路径,其中最短的路径长度为条路径,其中最短的路径长度为
2、164 例例5.1.1 最短路问题最短路问题表现为明显的阶段性表现为明显的阶段性一条从一条从A 到到B 的最短路径的最短路径中的任何一段都是最短的中的任何一段都是最短的 每步的决策只与相邻阶段状态有关,每步的决策只与相邻阶段状态有关,而与如何达到这一状态无关而与如何达到这一状态无关因此我们可以从因此我们可以从B向回搜索最短路向回搜索最短路标记法标记法如何找出最短路径如何找出最短路径5 5.1.2 动态规划的基本概念及递推公式动态规划的基本概念及递推公式1、基本概念、基本概念1)阶段)阶段;把多阶段决策问题分为若干个相互联系的阶段,常用;把多阶段决策问题分为若干个相互联系的阶段,常用k表示表示
3、2)状态:)状态:每一阶段开始时所处的状态。某一阶段某一状态用状态变量每一阶段开始时所处的状态。某一阶段某一状态用状态变量s k表示,第表示,第k阶段的所有状态集合用阶段的所有状态集合用S k表示,各阶段所有状态集合用表示,各阶段所有状态集合用S表示,则表示,则 s k S k S,动态规划中的状态必须满足无后效性。动态规划中的状态必须满足无后效性。3)决策:)决策:某一阶段某一阶段k某一状态某一状态s k所作出的决策用决策变量所作出的决策用决策变量x k(s k)表示,第)表示,第k阶段状态阶段状态s k的允许决策集合用的允许决策集合用D k(s k)表示,第)表示,第k阶段各状态的允许决策
4、阶段各状态的允许决策集合用集合用D k表示,所有各阶段各状态的允许决策集合用表示,所有各阶段各状态的允许决策集合用D 表示。则有表示。则有 x k(s k)D k(s k)D k D4)策略:)策略:指某一阶段某一状态到终点的顺序排列的决策组合的集合。用指某一阶段某一状态到终点的顺序排列的决策组合的集合。用 Pk(s k)=x k(s k),),x k-1(s k-1),),x 1(s 1)表示从第表示从第k阶段状态阶段状态s k出发到终点的一个子策略。从第出发到终点的一个子策略。从第k阶段状态阶段状态s k出发出发到终点的允许策略集合为到终点的允许策略集合为P。则。则Pk(s k)P。5)状
5、态转移方程:)状态转移方程:反映相邻两个阶段的状态和决策变量之间的相互关系反映相邻两个阶段的状态和决策变量之间的相互关系 s k-1=Tks k,x k(s k)=g(sk,xk)65.1.2 动态规划的基本概念及递推公式动态规划的基本概念及递推公式6)直接效果函数:)直接效果函数:它是状态变量它是状态变量s k和决策变量和决策变量x k(s k)的函数,记为:)的函数,记为:d ks k,x k(s k)。7)总效果函数:)总效果函数:从第从第k阶段状态阶段状态s k出发到终点的子策略出发到终点的子策略 Pk(s k)的函数。记为:)的函数。记为:Vk=Vk Pk(s k)8)最优效果函数:
6、)最优效果函数:表示在某一阶段某一状态下,采取最优策略后到终点的最优效表示在某一阶段某一状态下,采取最优策略后到终点的最优效果值。记为果值。记为2、最优化原理和动态规划递推关系、最优化原理和动态规划递推关系1、最优化原理:、最优化原理:最优策略的子策略也是最优的。最优策略的子策略也是最优的。2、递推关系:、递推关系:7 3、动态规划的步骤、动态规划的步骤1)划分阶段划分阶段 将所研究的问题划分为将所研究的问题划分为K个阶段,并对阶个阶段,并对阶段进行编号。一般按逆向编号;段进行编号。一般按逆向编号;2)确定状态变量确定状态变量s k 正确确定状态变量正确确定状态变量s k,使它既能描,使它既能
7、描述过程的演变又能满足无后效性;述过程的演变又能满足无后效性;3)确定决策变量确定决策变量x k(s k)及其允许的决策集合)及其允许的决策集合 D k(s k););4)写出状态转移方程写出状态转移方程 s k-1=g(s k,x k);5)确定直接效果函数确定直接效果函数6)列出最优指标函数的递推关系式列出最优指标函数的递推关系式7)确定边界条件确定边界条件 85.2 动态规划模型举例动态规划模型举例5.2.1 资源分配问题资源分配问题例例 5.2.1某某公公司司有有4个个推推销销员员在在北北京京、上上海海和和广广州州三三个个市市场场推推销销货货物物,这这三三个个市市场场里里推推销销人人员
8、员数数与与收收益益的的关关系系如如表表5.2.1所示,试作出使总收益最大的分配方案。所示,试作出使总收益最大的分配方案。表表5.2.1推销人员数与收益推销人员数与收益 推销员推销员市场市场01234北京北京2032475766上海上海4050607182广州广州506172 8483解解 1、划分阶段、划分阶段 分成分成3个阶段,即个阶段,即K=3,并按逆向编号,广,并按逆向编号,广州州k=1,上海,上海k=2,北京,北京k=3,分配推销员的优先顺序为北京,分配推销员的优先顺序为北京上海上海广州;广州;2、确定状态变量、确定状态变量s k 状态变量状态变量s k 表示第表示第k阶段初尚未分配的
9、推阶段初尚未分配的推销员数。显然有销员数。显然有 s3=4,s2和和s1的可能取值范围为的可能取值范围为0 4。93、确定决策变量、确定决策变量x k 决策变量决策变量x k 表示分配给第表示分配给第k阶段市场阶段市场的推销员数。显然有,的推销员数。显然有,x k s k;4、确定状态转移方程、确定状态转移方程 根据前面定义的状态变量根据前面定义的状态变量s k和决策和决策变量变量x k的意义,可得其状态转移方程为的意义,可得其状态转移方程为s k-1=s k-x k;5、确定直接效果函数、确定直接效果函数 d k(s k,x k)它表示第它表示第k阶段初有推阶段初有推销员数销员数s k,分配
10、给第,分配给第k市场市场x k个推销员时所产生的直接效个推销员时所产生的直接效益。这些效益指标由表益。这些效益指标由表5.2.1给出;给出;6、最优指标函数、最优指标函数 由于三个市场的总效益等于三个市场的由于三个市场的总效益等于三个市场的效益之和,即其指标函数为累加形式。所以最优指标函效益之和,即其指标函数为累加形式。所以最优指标函数为数为7、边界条件、边界条件 f0(s 0)=0。各阶段计算过程见教材各阶段计算过程见教材P(138139)10 5.2.2项目选择问题项目选择问题 某工厂预计明年有某工厂预计明年有A,B,C,D四个新四个新建项目,每个项目的投资额建项目,每个项目的投资额 wk
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 课件 运筹