Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,管 理 运 筹 学 马 越 峰,管理运筹学,主讲教师：马越峰,第五章 动态规划,5.1.动态规划的基本概念和最优化原理,5.2.动态规划模型的建立与求解,5.3.动态规划在经济管理中的应用,5.1.动态规划的基本概念和最优化原理,例1 最短路径问题,下图表示从起点A到终点E之间各点的距离。求A到E的最,短路径。,B,A,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,讨论：,1、以上求从A到E的最短路径问题，可以转化为四个性质完全相,同，但规模较小的子问题，即分别从D,i,、C,i,、B,i,、A到E的最短路,径问题。,第四阶段：两个始点D,1,和D,2,，终点只有一个；,分析得知：从D,1,和D,2,到E的最短路径唯一。,阶段4,本阶段始点,（状态）,本阶段各终点（决策）,到E的最短距离,本阶段最优终点,（最优决策),E,D,1,D,2,10*,6,10,6,E,E,第三阶段：有三个始点C,1,，C,2,，C,3,，终点有D,1,，D,2,，对始点,和终点进行分析和讨论分别求C,1,，C,2,，C,3,到D,1,，D,2,的最短路,径问题：,分析得知：如果经过C,1，,则最短路为C,1,-D,2,-E；,如果经过C,2，,则最短路为C,2,-D,2,-E；,如果经过C,3,，则最短路为C,3,-D,1,-E。,阶段3,本阶段始点,（状态）,本阶段各终点（决策）,到E的最短距离,本阶段最优终点,（最优决策),D,1,D,2,C,1,C,2,C,3,8+10=18,7+10=17,1+10=11,6+6=12,5+6=11,6+6=12,12,11,11,D,2,D,2,D,1,第二阶段：有4个始点B,1,B,2,B,3,B,4,，终点有C,1,C,2,C,3,。对始点和终点进行分析和讨论分别求B,1,B,2,B,3,B,4,到C,1,C,2,C,3,的最短路径问题,：,阶段2,本阶段始点,（状态）,本阶段各终点（决策）,到E的最短距离,本阶段最优终点（最优决策),C,1,C,2,C,3,B,1,B,2,B,3,B,4,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,12,13,14,12,C,2,C,3,C,3,C,3,第一阶段：只有1个始点A，终点有B,1,B,2,B,3,B,4,。对始点和终,点进行分析和讨论分别求A到B,1,B,2,B,3,B,4,的最短路径问题,：,最后可以得到：从A到E的最短路径为A,B,4,C,3,D,1,E,阶段1,本阶段始点(状态),本阶段各终点（决策）,到E的最短距离,本阶段最优终点(最优决策),B,1,B,2,B,3,B,4,A,4+12=,16,3+13=,16,3+14=,17,2+12=,14,14,B,4,一、基本概念：,1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。,2、状态s,k,：表示每个阶段开始所处的自然状况或客观条件。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。,3、决策x,k,：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为x,k,(s,k,)。,决策允许集合D,k,(s,k,)：在状态s,k,下，允许采取决策的全体。,D,3,(C,1,)=,D,1,D,2,基本概念、基本方程与最优化原理,例题中K=？,s,3,=?,4、策略P,k,n,(s,k,)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P,1,n,(s,1,)即为全过程策略。,5、状态转移方程 s,k+1,=T,k,(s,k,x,k,)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,6、,阶段指标函数v,k,(s,k,x,k,)：从状态s,k,出发，选择决策x,k,所产生的第k阶段指标。,过程指标函数V,k,n,(s,k,x,k,x,k+1,x,n,)：从状态s,k,出发，选择决策x,k,x,k+1,x,n,所产生的过程指标。,二、基本方程：,最优指标函数,f,k,(s,k,)：从状态s,k,出发，对所有的策略P,k,n,，过程指标V,k,n,的最优值，即,对于可加性指标函数，上式可以写为,终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标,f,n+1,(s,n+1,)=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,12,5.2 动态规划模型的建立与求解,解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设,s,k,=分配给第k个厂至第3个厂的设备台数（k=1、2、3),x,k,=分配给第k个设备台数。,已知s,1,=5,并有,从与的定义，可知,以下,我们从第三阶段开始计算。,第三阶段:,显然将台设备都分配给第3工厂时，,也就是时，第3阶段的指标值（即第3厂的盈利）,为最大，即,由于第3阶段是最后的阶段，故有,其中可取值为0,1,2,3,4,5。其数值计算见表。,012345,0,0 ,0,0,1,4,4,1,2,6 ,6,2,3,11,11,3,4,12,12,4,5,12,12,5,第二阶段：,当把台设备分配给第2工厂,和第3工厂时，则对每个值，有一种最优分配方案，,使最大盈利即最优2子过程最优指标函数值为,因为上式也可写成,其数值计算如表所示。,0 1 2345,0,0,0,1,04,5,1,2,06 54 ,10,2,3,011 56 110 ,14,2,4,012 114110,16,1,2,5,012 512 116114 110,21,2,第一阶段：把台设备分配给第1、第2、第3厂时，最,大盈利为 其中 可取值0,1,2,3,4,5.数值计算见表,然后按计算表格的顺序推算，可知最优分配方案有两个：,甲：0台 乙：2台 丙：3台,甲：2台 乙：2台 丙：1台,x,1,s,1,r,1,(5,x,1,)+f,2,(5-x,1,),f,1,(x),X,1,*,0,1,2,3,4,5,5,0+21,3+16,7+14,9+10,12+5,13+0,21,0,2,背包问题,设有,n,种物品，每一种物品数量无限。第,i,种物品每,件重量为,w,i,公斤，每件价值,c,i,元。现有一只可装载重量,W,公斤的背包，求各种物品应各取多少件放入背包，使背,包中物品的价值最高。,这个问题可以用整数规划模型来描述。设,x,i,为第,i,种,物品装入背包的件数（,i,=1,2,n,），背包中物品的总,价值为,z,，则,Max z=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t.w,1,x,1,+w,2,x,2,+w,n,x,n,W,x,1,x,2,x,n,0,且为整数。,5.3 动态规划的应用,例3:某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？,咨询项目类型,待处理客户数,处理每个客户所需工作日数,处理每个客户所获利润,1,2,3,4,4,3,2,2,1,3,4,7,2,8,11,20,解：用动态规划来求解此题。,我们把此问题分成四个阶段，第一阶段我们决策将,处理多少个第一种咨询项目类型中的客户，第二阶段决,策将处理多少个第二种咨询项目类型中的客户，第三阶,段、第四阶段我们也将作出类似的决策。我们设,分配给第k种咨询项目到第四种咨询项目的所,有客户的总工作日（第k阶段的状态变量）。,=在第k种咨询项目中处理客户的数量（第k阶段,的决策变量）。,已知10,并有,因为至多为10，其数值计算见表,01,0,00,1,00,2,00,3,00,4,00,5,00,6,00,7,0,201,8,0,201,9,0,201,10,0,11,第四阶段：,0 1 2,0,0,0,1,0,0,2,0,0,3,0,0,4,00,11,1,5,00,11,1,6,00,11,1,7,11+0 ,20,0,8,020 11+0,22,2,9,020 11+0,22,2,10,020 11+0,22,2,第三阶段：,第二阶段：,第一阶段：,最优解,：,1.,石油输送管道铺设最优方案的选择问题.下图中A为出,发点,E为目的地,B,C,D分别为三个必须建立油泵加压,站的地区,图中的线段表示管道可铺设的位置,线段旁,的数字为铺设管道线所需的费用.问如何铺设管道才使,总费用最小.,练习.,B,3,B,1,B,2,A,C,1,C,2,C,3,D,1,D,2,E,3,5,4,6,3,5,3,2,4,4,1,5,2,5,7,4,5,4,3,4,2.,某公司有资金400万元,向A,B,C三个项目追加投资,三个,项目可以有不同的投资额度,相应的效益值如下,问如何,分配资金,才使总效益最大.,效益 投资,值 额,项目,0,1,2,3,4,A,B,C,47,49,46,51,52,70,59,61,76,71,71,88,76,78,88,3.,某厂为扩大生产能力，拟订购某种成套设备46套,以,分配给所辖1,2,3三个分厂使用,预计各分厂分得不同套数,的设备后每年创造的利润如下表.该厂应订购几套设备并,如何分配,才能使每年预计创利润总额最大.,利润 套,数,分厂,0,1,2,3,4,5,6,1,2,3,0,0,0,3,4,2,5,6,5,6,7,9,7,8,8,6,9,8,5,10,7,4.某厂生产三种产品,各种产品的重量与利润关系如下表,所示.现将三种产品运往市场出售.运输能力总量不超过,10吨.问如何安排运输使得总利润为最大.,种类,重量,利润(元/件),1,2,3,2,3,4,100,140,180,