管理运筹学-第5章--动态规划ppt课件.ppt

管理运筹学管理运筹学管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第五章第五章 动态规划动态规划 5.1. 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理5.2. 动态规划模型的建立与求解动态规划模型的建立与求解5.3. 动态规划在经济管理中的应用动态规划在经济管理中的应用管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用5.1. 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理例例1 1 最短路径问题最短路径问题下图表示从起点A到终点E之间各点的距离求A到E的最短路径BACBDBCDEC412312312322164724838675611063751管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用讨论：讨论： 1、以上求从、以上求从A到到E的最短路径问题，可以转化为四个性质完全相的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从同，但规模较小的子问题，即分别从Di 、、Ci、、Bi、、A到到E的最短路的最短路径问题。

径问题 第四阶段：两个始点第四阶段：两个始点D1和和D2，终点只有一个；，终点只有一个；分析得知：从分析得知：从D1和和D2到到E的最短路径唯一的最短路径唯一 阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) E D1 D2 10* 6 10 6 E E管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 第三阶段：有三个始点第三阶段：有三个始点C1，，C2，，C3，终点有，终点有D1，，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，，C2，，C3到到D1，，D2 的最短路的最短路径问题：径问题：分析得知：如果经过分析得知：如果经过C1，，则最短路为则最短路为C1-D2-E；； 如果经过如果经过C2，，则最短路为则最短路为C2-D2-E；； 如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。

阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点（决策）本阶段各终点（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第第二二阶阶段段：：有有4个个始始点点B1,B2,B3,B4，，终终点点有有C1,C2,C3对对始始点点和和终终点点进进行行分分析析和和讨讨论论分分别别求求B1,B2,B3,B4到到C1,C2,C3 的的最最短路径问题短路径问题：： 阶段阶段2本阶段始点本阶段始点（状态）（状态） 本阶段各终点（决策）本阶段各终点（决策）到到E的最短的最短距离距离本阶段最优终本阶段最优终点（最优决策点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 1213 14 12 C2 C3 C3 C3管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一阶段：只有第一阶段：只有1个始点个始点A，终点有，终点有B1,B2,B3,B4 。

对始点和终对始点和终点进行分析和讨论分别求点进行分析和讨论分别求A到到B1,B2,B3,B4的最短路径问题的最短路径问题： 最后可以得到：从最后可以得到：从A到到E的最短路径为的最短路径为A B4 C3 D1 E 阶段阶段1本阶段始本阶段始点点(状态状态) 本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 B4管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一、基本概念：一、基本概念： 1、阶段、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。

表示决策顺序的离散的量，阶段可以按时间或空间划分 2、、状状态态sk：：表表示示每每个个阶阶段段开开始始所所处处的的自自然然状状况况或或客客观观条条件件状状态态可可以以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的是数量，也可以是字符，数量状态可以是连续的，也可以是离散的 3、、决决策策xk：：从从某某一一状状态态向向下下一一状状态态过过渡渡时时所所做做的的选选择择决决策策是是所所在在状状态的函数，记为态的函数，记为xk(sk) 决策允许集合决策允许集合Dk(sk)：在状态：在状态sk下，允许采取决策的全体下，允许采取决策的全体 D3(C1)= ｛｛D1,D2｝｝ 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理例题中例题中K=？？s3=?管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4、、策策略略Pk,n(sk)：：从从第第k阶阶段段开开始始到到最最后后第第n阶阶段段的的决决策策序序列列，，称称k子策略。

子策略P1,n(s1)即为全过程策略即为全过程策略5、、状状态态转转移移方方程程 sk+1=Tk(sk, xk)：：某某一一状状态态以以及及该该状状态态下下的的决策，与下一状态之间的函数关系决策，与下一状态之间的函数关系 6、阶阶段段指指标标函函数数v vk k(s(sk k, , x xk k) )：：从从状状态态s sk k出出发发，，选选择择决决策策x xk k所所产产生生的的第第k k阶段指标阶段指标 过过程程指指标标函函数数V Vk,nk,n(s(sk k, , x xk k, , x xk+1k+1,…, ,…, x xn n) )：：从从状状态态s sk k出出发发，，选选择择决策决策x xk k,x,xk+1k+1, …, x, …, xn n所产生的过程指标所产生的过程指标 管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二、基本方程：二、基本方程： 最最优优指指标标函函数数fk(sk)：：从从状状态态sk出出发发，，对对所所有有的的策策略略Pk,n，过程指标，过程指标Vk,n的最优值，即的最优值，即对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为 终终端端条条件件：：为为了了使使以以上上的的递递推推方方程程有有递递推推的的起起点点，，必必须须要要设设定定最最优优指指标标的的终终端端条条件件，，一一般般最最后后一一个个状状态态n+1n+1下最优指标下最优指标f fn+1n+1(s(sn+1n+1) = 0) = 0。

管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用三、最优化原理三、最优化原理 作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略就是说，最优策略的策必定构成最优子策略就是说，最优策略的任意子策略都是最优的任意子策略都是最优的管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一、资源分配问题一、资源分配问题 例例2:某某公公司司拟拟将将某某种种设设备备5台台，，分分配配给给所所属属的的甲甲、、乙乙、、丙丙三三个个工工厂厂,各各工工厂厂获获得得此此设设备备后后，，预预测测可可创创造造的的利利润润如如表表所所示示，，问问这这5台台设备应如何分配给这设备应如何分配给这3个工厂，使得所创造的总利润为最大个工厂，使得所创造的总利润为最大？ 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 125.2 5.2 动态规划模型的建立与求解动态规划模型的建立与求解管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。

设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3)　 xk=分配给第k个设备台数　 已知s1=5, 并有　　　　 　从　与　的定义，可知　　　　　　　　　　　　　以下我们从第三阶段开始计算管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 第三阶段: 显然将　　　　　　　　台设备都分配给第3工厂时，也就是　　　时，第3阶段的指标值（即第3厂的盈利）为最大，即　　　　　　　 由于第3阶段是最后的阶段，故有 其中　可取值为0,1,2,3,4,5其数值计算见表　　　　　 管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　0　　　1　　　2　　　3　　　4　　　　5　　0　0　　－　 －　　－　 －　 －　　　　　　　　　　　　　　　　　　　00　1－　　4　　－　　－　－　－　41　2－　　－　　 6　 －　　－　 －62　3－　　－　 －　　 11　　－　－　 113　4－　　－　 －　　－　　 12　－　 124　5－　　－　 －　 －　－　　12125管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 第二阶段：第二阶段： 当把　　　　　　　　台设备分配给第2工厂和第3工厂时，则对每个　值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用因为　　　　上式也可写成因为　　　　上式也可写成其数值计算如表所示。

其数值计算如表所示　　　　　　　　　　　　　　　　　　 　　　　　　　　　　　0　　　 1　　　 2　　　　3　　　　　4　　　　5　　0　　　　 －　　　－　　　　－　　　　－　　　－　　　　　　　　　　　　　　　　　　　00　10＋4　　　　　　 －　　 －　　　 －　　　 －　51　20＋6 　　 5＋4　　　　　　 －　　　 －　　　 －102　30＋11 　 5＋6 　　　　　　 11＋0　　　－　　　 －　142　40＋12 　　　　　　　　　　 11＋4　　11＋0　　　 －　161,2　50＋12 　 5＋12 　　　　　 11＋6　　11＋4　　 11＋0　　　　　212管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用　　　　第一阶段：把　　　　台设备分配给第第一阶段：把　　　　台设备分配给第1 1、第、第2 2、第、第3 3厂时，最厂时，最大大盈盈利利为为　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 　　 其其中中　　 可可取取值值0,1,2,3,4,5.0,1,2,3,4,5.数值计算见表数值计算见表 然后按计算表格的顺序推算，可知最优分配方案有两个：甲：0台 乙：2台 丙：3台甲：2台 乙：2台 丙：1台 x1s1r1(5,x1)+f2(5-x1)f1(x)X1*01234550+213+167+149+1012+513+0210,2管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用背包问题背包问题 设有设有n种物品，每一种物品数量无限。

第种物品，每一种物品数量无限第i种物品每种物品每件重量为件重量为wi公斤，每件价值公斤，每件价值ci元现有一只可装载重量元现有一只可装载重量W公斤的背包，求各种物品应各取多少件放入背包，使背公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高包中物品的价值最高 这个问题可以用整数规划模型来描述设这个问题可以用整数规划模型来描述设xi为第为第i种种物品装入背包的件数（物品装入背包的件数（i =1, 2, …, n），背包中物品的总），背包中物品的总价值为价值为z，则，则 Max z = c1x1+c2x2+ … +cnxn s.t. w1x1+w2x2+…+wnxn≤W x1, x2, …, xn 0 且为整数且为整数5.3 5.3 动态规划的应用动态规划的应用管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例3:3:某某咨咨询询公公司司有有1010个个工工作作日日可可以以去去处处理理四四种种类类型型的的咨咨询询项项目目，，每每种种类类型型的的咨咨询询项项目目中中待待处处理理的的客客户户数数量量、、处处理理每每个个客客户户所所需需工工作作日日数数以以及及所所获获得得的的利利润润如如表表所所示示。

显显然然该该公公司司在在1010天天内内不不能能处处理理完完所所有有的的客客户户，，它它可可以以自自己己挑挑选选一一些些客客户户，，其其余余的的请请其其他他咨咨询询公公司司去去做做，，应应如如何何选选择择客客户户使使得得在这在这1010个工作日中获利最大？个工作日中获利最大？　　　　　　　　　 咨询项目类型咨询项目类型待处理客户数待处理客户数处理每个客户所处理每个客户所需工作日数需工作日数处理每个客处理每个客户所获利润户所获利润　　1　　2　　3　　4　　　　4　　　　3　　　　2　　　　2　　　　　　1　　　　　　3　　　　　　4　　　　　　7　　　　2　　　　8　　　　11　　　　20管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用　　　　解：用动态规划来求解此题解：用动态规划来求解此题　　我们把此问题分成四个阶段，第一阶段我们决策将　　我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。

我们设段、第四阶段我们也将作出类似的决策我们设　　　　＝分配给第　　　　＝分配给第k种咨询项目到第四种咨询项目的所种咨询项目到第四种咨询项目的所有客户的总工作日（第有客户的总工作日（第k阶段的状态变量）阶段的状态变量）　　　　 =在第在第k种咨询项目中处理客户的数量（第种咨询项目中处理客户的数量（第k阶段阶段的决策变量）的决策变量）　　已知　＝　　已知　＝10　　并有　　并有　　　　 管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用　　因为　至多为10，其数值计算见表　　　　　　　　　　　　　　0　　　　　　　　1　　0　　　　　　　　　　　　－　　　　　　　 　　0　　　　　　　　0　　1　　　　　　　　　　－　　0　　　　　　　　0　　2　　　　　　　　　　－　　　　　　 　　0　　　　　　　　0　　3　　　　　　　　　　－　　　　0　　　　　　　　0　　4　　　　　　　　　　－　　　　　0　　　　　　　　0　　5　　　　　　　　　　　－　　　　　0　　　　　　　　0　　6　　　　　　　　　　－　　　　0　　　　　　　　0　　　　7　　0　　　　　　　20　　　　　　　1　　8　　0　　　　　20　　　　　　　1　　9　　0　　20　　　　　　　1　　　10　　0　　1　　　　　　　　1第四阶段：第四阶段：管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 0 1 2　0　　　　　　　　　－　　　　　　　－　　0　　0 1 －　　　　　　　－　　0　　0 2　　　　　　　　　－　　　　　　　－　　　0　　0 3　　　　　　　　　－　　　　　　　－　　0　　0 4　0＋0　　　　　　　　　　　　　　－　　　11 1 5　0＋0　　　　　　　　　　　　　　－　　11 1 6　0＋0　　　　　　　　　　　　　　－　　11 1 7 　　　　　　　　　 11+0　　　 　－ 20 0 8　0＋20 　　　 11+0　 22 2 9　0＋20 　　 11+0　 22 2 10　0＋20 　　　11+0　 22 2第三阶段：第三阶段：管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二阶段：第二阶段：管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用　　 第一阶段：第一阶段：　　　最优解最优解：：管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1.石油输送管道铺设最优方案的选择问题石油输送管道铺设最优方案的选择问题.下图中下图中A为出为出 发点发点,E为目的地为目的地,B,C,D分别为三个必须建立油泵加压分别为三个必须建立油泵加压 站的地区站的地区,图中的线段表示管道可铺设的位置图中的线段表示管道可铺设的位置,线段旁线段旁 的数字为铺设管道线所需的费用的数字为铺设管道线所需的费用.问如何铺设管道才使问如何铺设管道才使 总费用最小总费用最小.练习练习.管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用B3B1B2AC1C2C3D1D2E35463532441525745434管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2.某公司有资金某公司有资金400万元万元,向向A,B,C三个项目追加投资三个项目追加投资,三个三个 项目可以有不同的投资额度项目可以有不同的投资额度,相应的效益值如下相应的效益值如下,问如何问如何 分配资金分配资金,才使总效益最大才使总效益最大.效益 投资 值 额项目01234ABC474946515270596176717188767888管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.某厂为扩大生产能力，拟订购某种成套设备某厂为扩大生产能力，拟订购某种成套设备4—6套套,以以 分配给所辖分配给所辖1,2,3三个分厂使用三个分厂使用,预计各分厂分得不同套数预计各分厂分得不同套数的设备后每年创造的利润如下表的设备后每年创造的利润如下表.该厂应订购几套设备并该厂应订购几套设备并如何分配如何分配,才能使每年预计创利润总额最大才能使每年预计创利润总额最大.利润 套 数分厂01234561230003425656797886985107管管 理理 运运 筹筹 学学 – 马马 越越 峰峰经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用4.某厂生产三种产品某厂生产三种产品,各种产品的重量与利润关系如下表各种产品的重量与利润关系如下表所示所示.现将三种产品运往市场出售现将三种产品运往市场出售.运输能力总量不超过运输能力总量不超过10吨吨.问如何安排运输使得总利润为最大问如何安排运输使得总利润为最大.种类种类重量重量利润利润(元元/件件)123234100140180。