西安电子科技大学数学建模讲义第八讲省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢,主讲人:穆学文,西安电子科技大学数学系,Email:mxw1334,数学建模讲义,第1页,数学建模专题讲座,最优化模型,-,动态规划,第2页,动态规划,1 动态规划基本概念和方法,基本概念与名词解释,最优化原理与动态规划基本方法,2 动态规划模型建立与求解步骤,建立动态规划模型基本要求,动态规划求解步骤,3 动态规划应用举例,定价问题,资源分配问题,生产存放问题,第3页,第一节 动态规划基本概念与方法,1 动态规划基本概念,一、动态决议问题：,决议过程含有阶段性和时序性(与时间相关)决议问题。即决议过程可划分为显著阶段。,二、什么叫动态规划(D.P.Dynamic Program)：,多阶段决议问题最优化一个方法。,广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。,三、动态规划(D.P.)起源：,1951年,美国数学家R.Bellman(贝尔曼),等人提出最优化原理，从而建立动态规划，他名著动态规划于1957年出版。,第4页,四、动态决议问题分类：,1、按数据给出形式分为：,离散型动态决议问题。,连续型动态决议问题。,2、按决议过程演变性质,分为：,确定型动态决议问题。,随机型动态决议问题。,第5页,名词解释,例1 某企业欲将一批货物从城市A运到城市E去，如图所表示，走哪条路线最好,？,第6页,1、阶段(stage),k,：把所给问题过程，恰当地分成若干个相互联络阶段。描述阶段变量称为阶段变量，惯用,k,表示。,k,=1、2、3、4。,2、状态(state)S,k,：状态表示每个阶段开始所处状态,即是每一阶段出发位置.,阶段起点,.通常一个阶段有多个状态.记为S,k,.,S,1,=A，S,2,=B,1,B,2,B,3,，S,3,=C,1,C,2,C,3,S,4,=D,1,D,2,。,第7页,3、决议(decision),u,k,(s,k,),：从一个阶段某状态演变到下一个阶段某状态选择.惯用,u,k,(s,k,)表示第k阶段当状态处于s,k,时决议变量.,决议集用D,n,(S,k,)表示.就是,阶段终点.,D,1,(S,1,)=u,1,(A)=B,1,B,2,B,3,=S,2,，,D,2,(S,2,)=U,2,(B,1,),U,2,(B,2,),U,2,(B,3,)=C,1,C,2,;C,1,C,2,C,3,;C,2,C,3,=C,1,C,2,C,3,=S,3,，,D,3,(S,3,)=U,3,(C,1,),U,3,(C,2,),U,3,(C,3,)=D,1,D,2,;D,1,D,2,D,3,;D,1,D,2,D,3,=D,1,D,2,D,3,=S,4,，,D,4,(S,4,)=U,4,(D,1,),U,4,(D,2,),U,4,(D,3,)=E,1,E,2,;E,1,E,2,;E,1,E,2,=E,1,E,2,=S,5,，,D,5,(S,5,)=X,5,(E,1,),X,5,(E,2,)=F;F=F。,第8页,4、,策略(policy)：全过程中各个阶段决议U,n,组成有序总体,U,n,.如 A,B,2,C,1,D,1,E,5、子策略(sub-policy),：剩下M个阶段组成M子过程,对应,决议系列叫M子策略.如 C,1,D,1,E,6、状态转移方程：前一阶段终点(决议)是后前一阶段起点,(状态).U,k,=S,k+1,7、指标函数：各个阶段数量指标,记为V,k,n,(s,k,U,k,).如上例中,用d,k,(s,k,U,k,)表示距离.d,2,(B,3,C,2,)=8,d,3,(C,2,D,2,)=2 等.,8、目标函数:策略数量指标值,记为,Z=optv,1,(s,1,u,1,)*,*,v,n,(s,n,u,n,).,其中：opt为max或min，*为运算符号.如上例中，,Z=mind,1,(s,1,u,1,)+,+,d,n,(s,n,u,n,)=mind,1,+d,2,+,d,n,第9页,一、R.Bellman最优化原理：,作为整个过程最优策略，不论过去状态和决议怎样，对前面决议形成状态而言，余下诸决议必组成最优策略。,即：若M是从A到B最优路线上任一点，则从M到B路线也是最优路线。,A,M,B,最优化原理,第10页,二、指标递推方程：,f,n,*,(S,n,)=opt v,n,(s,n,u,n,)*v,n,(s,n,u,n,),x,n,D,n,(S,n,),如上例：,f,n,*,(S,n,)=min v,n,(s,n,u,n,)+f,n+1,*,(S,n+1,),n=3、2、1,x,n,D,n,(S,n,),f,4,*,(S,4,)=min v,4,(s,4,u,4,),x,4,D,4,(S,4,),三、求解过程：,用反向嵌套递推法：从最终一个阶段开始，依次对各子过程寻优，直至取得全过程最优，形成最优策略，取得最优策略指标值。,第11页,一、建立动态规划模型基本要求,将问题划分成若干阶段。有问题阶段性很显著，有则不显著，需要分析后人为假设。,确定各阶段状态变量，并给出状态转移方程，状态转移方程形式应该与递推次序一致。,状态变量应该满足无后效性要求。,明确指标函数，给出最优函数递推方程，递推方程形式应该与递推次序一致。,第12页,二、动态规划求解步骤,正确划分阶段。,确定状态变量和决议变量，并给出状态变量和决议变量可行集合。,确定求解递推次序，给出状态转移方程。,确定阶段、子过程(子策略)指标函数，确定最优值函数递推方程和边界条件。,递推求解。,与递推过程反向求出最优策略(最优决议变量值系列)和最优状态改变路线。,第13页,例2：求以下图中A到F最短路线及最短路线值。,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,第14页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,1、阶段(stage)n：n=1、2、3、4、5。,2、状态(state)S,n,：,S,1,=A，S,2,=B,1,B,2,B,3,，S,3,=C,1,C,2,C,3,，,S,4,=D,1,D,2,D,3,，S,5,=E,1,E,2,。,3、决议(decision)X,n,：决议集D,n,(S,n,)。,D,1,(S,1,)=X,1,(A)=B,1,B,2,B,3,=S,2,，,D,2,(S,2,)=X,2,(B,1,),X,2,(B,2,),X,2,(B,3,)=C,1,C,2,;C,1,C,2,C,3,;C,2,C,3,=C,1,C,2,C,3,=S,3,，,D,3,(S,3,)=X,3,(C,1,),X,3,(C,2,),X,3,(C,3,),=D,1,D,2,;D,1,D,2,D,3,;D,1,D,2,D,3,=D,1,D,2,D,3,=S,4,，,D,4,(S,4,)=X,4,(D,1,),X,4,(D,2,),X,4,(D,3,)=E,1,E,2,;E,1,E,2,;E,1,E,2,=E,1,E,2,=S,5,，,D,5,(S,5,)=X,5,(E,1,),X(E,2,)=F;F=F。,第15页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,4、状态转移方程：X,n,=S,n+1,5、指标函数(距离)：d,n,(s,n,x,n,).,d,2,(B,3,C,2,)=1,d,3,(C,2,D,3,)=6 等。,6、指标递推方程：,f,n,*,(S,n,)=min d,n,(s,n,X,n,)+f,n+1,*,(S,n+1,)，,n=4、3、2、1 U,n,D,n,(S,n,),f,5,*,(S,5,)=min V,5,(s,5,X,5,)X,5,D,5,(S,5,),第16页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,1,1,F,2,2,F,4+1=5,2+2=4,4,E,2,6+1=7,9+2=11,7,E,1,7+1=8,5+2=7,7,E,2,第17页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,1+4=5,5+7=12,/,5,D,1,8+4=12,4+7=11,6+7=13,11,D,2,4+4=8,4+7=11,2+7=9,8,D,1,9+5=14,5+11=16,/,14,C,1,4+5=9,3+11=14,5+8=13,9,C,1,/,1+11=12,7+8=15,12,C,2,第18页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,3+14=17,5+9=14,4+12=16,14,B,2,最短路线值为：f,1,*,(s,1,)=14,最短路线求解以下：,第19页,1,1,F,2,2,F,4+1=5,2+2=4,4,E,2,6+1=7,9+2=11,7,E,1,7+1=8,5+2=7,7,E,2,1+4=5,5+7=12,/,5,D,1,8+4=12,4+7=11,6+7=13,11,D,2,4+4=8,4+7=11,2+7=9,8,D,1,9+5=14,5+11=16,/,14,C,1,4+5=9,3+11=14,5+8=13,9,C,1,/,1+11=12,7+8=15,12,C,2,3+14=17,5+9=14,4+12=16,14,B,2,第20页,A,B,1,B,2,B,3,C,1,C,2,C,3,D,1,D,2,D,3,E,1,E,2,F,3,5,4,9,5,4,3,5,1,7,1,5,8,4,6,4,4,2,2,2,6,9,7,5,1,4,即：,A,B,2,C,1,D,1,E,2,F,第21页,第三节 动态规划应用举例,定价问题,资源分配问题,生产存放问题,第22页,一、定价问题,某企业考虑为某新产品定价，该产品单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度变动，该产品预计畅销五年，据预测不一样价格下各年利润如表3-1所表示。,表3-2 每年预计利润额,单价,第一年,第二年,第三年,第四年,第五年,5元,6元,7元,8元,10,12,14,16,12,13,14,15,15,16,16,15,20,20,18,14,25,24,18,14,第23页,建立数学模型,按年划分阶段，k=1,2,.,5,每阶段状态变量为本年(上一年已确定)价格，状态变量可行集合S,k,=(5,6,7,8)。,决议变量为每年依据当年价格为下一年度决定价格，依据题意决议变量可行集合是：,采取逆序算法，所以状态转移方程是,最优值函数递推方程为,第24页,进行各阶段计算,采取逆序法，设,当k=5时，S,5,=(5,6,7,8)，由表3-1得到,当k=4时，S,4,=(5,6,7,8)，由递推方程,得,第25页,继续求解,同理得其它各阶段最优解,第26页,反推得最优路线,按照与求最优值函数方向相反次序求最优状态路线：最优决议变量。即从第一年单价应为8元开始，向后推算。,得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。,最大利润值为92万元。,第27页,也可用决议图求解,第28页,二、资源分配问题,某企业将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂利用设备后可产生如表3-2所表示利润，应怎么分配设备可使企业总利润最大,？,工厂,设备数,甲,乙,丙,丁,0,1,2,3,4,5,0,6,7,10,12,15,0,3,7,9,12,13,0,5,10,11,11,11,0,4,6,11,12,12,第29页,建立数学模型,按工厂次序划分阶段，k=1，2，3，4,状态变量为各阶段可用于分配设备总台数,决议变量是分配给第k工厂设备数,采取逆序算法，状态转移方程,最优值函数递推方程,第30页,第4阶段最优解,当k=4时，S,4,=(0,1,2,3,4,5),0,1,2,3,4,5,0,1,2,3,4,5,0,4,6,11,12,12,0,4,6,11,12,12,0,1,2,3,4,5,第31页,第3阶段最优解,当k=3时，S,3,=(0,1,2),0,0,0,0,0,0,0,1,0,1,0,5,4,0,4,5,5,1,2,0,1,2,0,5,10,6,4,0,6,9,10,10,2,第32页,第3阶段最优解（续）,当k=3时，S,3,=3,3,0,1,2,3,0,5,10,11,11,6,4,0,11,11,14,11,14,2,第33页,第3阶段最优解（续）,当k=3时，S,3,=4,4,0,1,2,3,4,0,5,10,11,11,12,11,6,4,0,12,16,16,15,11,16,1，2,第34页,第3阶段最优解（续）,当k=3时，S,3,=5,5,0,1,2,3,4,5,0,5,10,11,11,11,12,12,11,6,4,0,12,17,21,17,15,11,21,2,第35页,第2阶段最优解,当k=2时，S,2,=(0,1,2),0,0,0,0,0,0,0,1,0,1,0,3,5,0,5,3,5,0,2,0,1,2,0,3,7,10,5,0,10,8,7,10,0,第36页,第2阶段最优解（续）,k=2时，S,2,=3,3,0,1,2,3,0,3,7,9,14,10,5,0,14,13,12,9,14,0,第37页,第2阶段最优解（续）,当k=2时，S,2,=4,4,0,1,2,3,4,0,3,7,9,12,16,14,10,5,0,16,17,17,14,12,17,1，2,第38页,第2阶段最优解（续）,当k=2时，S,2,=5,5,0,1,2,3,4,5,0,3,7,9,12,13,21,16,14,10,5,0,21,19,21,19,17,15,21,0，2,第39页,第1阶段最优解（续）,当k=1时，S,1,=5,5,0,1,2,3,4,5,0,6,7,10,12,15,21,17,14,10,5,0,21,23,21,20,17,15,23,1,第40页,反向求最正确状态路线,方案一,方案二,工厂名,分配设备数,工厂名,分配设备数,甲,乙,丙,丁,1,1,2,1,甲,乙,丙,丁,1,2,2,0,第41页,三、生产存放问题,某企业生产并销售某产品。依据市场预测，今后四个月市场需求量如表3-7所表示。,时期（月）,需求量（d,k,）,1,2,3,4,2,3,2,4,第42页,已知其它条件,已知生产一件产品成本是1千元，每批产品生产准备成本是3千元，每个月仅能生产一批，每批6件。每件存放成本为0.5千元，且第一个月初无存货，第四个月末存货要求为零。求最优生产计划。,设第k月生产量u,k,，存放量为S,k,则总成本为,第43页,建立数学模型,以月划分阶段，k=1,2,3,4,各阶段决议变量为该阶段生产量u,k,，状态变量为该阶段存放量S,k,。,采取逆序算法，则状态转移方程为,最低成本递推公式是,第44页,第四阶段最优解,当k=4时，d,4,=4,因第四阶段末无存货，所以S,4,=(0,1,2,3,4),S,4,u,4,本期成本,C,4,S,5,f,5,(S,5,),f,4,(S,4,),生产,存放,0,1,2,3,4,4,3,2,1,0,7,6,5,4,0,0,0.5,1,1.5,2,7,6.5,6,5.5,2,0,0,0,0,0,0,0,0,0,0,7,6.5,6,5.5,2,第45页,第三阶段最优解,当k=3时，因为 ，且第三阶段需求量d,3,=2，S,3,=(0,1,2,3,4,5,6),S,3,u,3,本期成本,C,3,S,4,f,4,(S,4,),f,3,(S,3,),生产,存放,0,2,3,4,5,6,5,6,7,8,9,0,0,0,0,0,5,6,7,8,9,0,1,2,3,4,7,6.5,6,5.5,2,12,12.5,13,13.5,11,第46页,第三阶段最优解:S,3,=1,S,3,u,3,本期成本,C,3,S,4,f,4,(S,4,),f,3,(S,3,),生产,存放,1,1,2,3,4,5,4,5,6,7,8,0.5,0.5,0.5,0.5,0.5,4.5,5.5,6.5,7.5,8.5,0,1,2,3,4,7,6.5,6,5.5,2,11.5,12.0,12.5,13.0,10.5,第47页,第三阶段最优解:S,3,=2,S,3,u,3,本期成本,C,3,S,4,f,4,(S,4,),f,3,(S,3,),生产,存放,2,0,1,2,3,4,0,4,5,6,7,1,1,1,1,1,1,5,6,7,8,0,1,2,3,4,7,6.5,6,5.5,2,8,11.5,12.0,12.5,10.0,第48页,第三阶段最优解:S,3,=3,4,S,3,u,3,本期成本,C,3,S,4,f,4,(S,4,),f,3,(S,3,),生产,存放,3,0,1,2,3,0,4,5,6,1.5,1.5,1.5,1.5,1.5,5.5,6.5,7.5,1,2,3,4,6.5,6,5.5,2,8,11.5,12.0,9.5,4,0,1,2,0,4,5,2,2,2,2,6,7,2,3,4,6,5.5,2,8,11.5,9,第49页,第三阶段最优解:S,3,=5,6,S,3,u,3,本期成本,C,3,S,4,f,4,(S,4,),f,3,(S,3,),生产,存放,5,0,1,0,4,2.5,2.5,2.5,6.5,3,4,5.5,2,8,8.5,6,0,0,3,3,4,2,5,第50页,第二阶段最优解,当k=2时，d,2,=3，因为最大生产能力为6，而d,1,=2，所以S,2,=(0,1,2,3,4),S,2,u,2,本期成本,C,2,S,3,f,3,(S,3,),f,2,(S,2,),生产,存放,0,3,4,5,6,6,7,8,9,0,0,0,0,6,7,8,9,0,1,2,3,11.0,10.5,8.0,8.0,17,17.5,16,17,第51页,第二阶段最优解:S,2,=1,S,2,u,2,本期成本,C,2,S,3,f,3,(S,3,),f,2,(S,2,),生产,存放,1,2,3,4,5,6,5,6,7,8,9,0.5,0.5,0.5,0.5,0.5,5.5,6.5,7.5,8.5,9.5,0,1,2,3,4,11.0,10.5,8.0,8.0,8.0,16.5,17,15.5,16.5,17.5,第52页,第二阶段最优解:S,2,=2,S,2,u,2,本期成本,C,2,S,3,f,3,(S,3,),f,2,(S,2,),生产,存放,2,1,2,3,4,5,6,4,5,6,7,8,9,1,1,1,1,1,1,5,6,7,8,9,10,0,1,2,3,4,5,11.0,10.5,8.0,8.0,8.0,8.0,16.0,16.5,15.0,16.0,17.0,18.0,第53页,第二阶段最优解:S,2,=3,S,2,u,2,本期成本,C,2,S,3,f,3,(S,3,),f,2,(S,2,),生产,存放,3,0,1,2,3,4,5,6,0,4,5,6,7,8,9,1.5,1.5,1.5,1.5,1.5,1.5,1.5,1.5,5.5,6.5,7.5,8.5,9.5,10.5,0,1,2,3,4,5,6,11.0,10.5,8.0,8.0,8.0,8.0,5.0,12.5,16.0,14.5,15.5,16.5,17.5,15.5,第54页,第二阶段最优解:S,2,=4,S,2,u,2,本期成本,C,2,S,3,f,3,(S,3,),f,2,(S,2,),生产,存放,4,0,1,2,3,4,5,0,4,5,6,7,8,2,2,2,2,2,2,2,6,7,8,9,10,1,2,3,4,5,6,10.5,8.0,8.0,8.0,8.0,5.0,12.5,14,15,16,17,15,第55页,第一阶段最优解,当k=1时，d,1,=2，S,1,=0,S,1,u,1,本期成本,C,1,S,2,f,2,(S,2,),f,1,(S,1,),生产,存放,0,2,3,4,5,6,5,6,7,8,9,0,0,0,0,0,5,6,7,8,9,0,1,2,3,4,16.0,15.5,15.0,12.5,12.5,21,21.5,22,20.5,21.5,第56页,最优解,从第一阶段向后反推最优路线，总结可得,时期,K,期初存货,期末存货,最优生产量,该期成本,总成本,S,k,S,k+1,1,2,3,4,0,3,0,4,3,0,4,0,5,0,6,0,8,1.5,9,2,20.5,12.5,11,2,第57页,