西安电子科技大学数学建模讲义第八讲.ppt

,Email:mxw1334,数学建模讲义,数学建模专题讲座,最优化模型-动态规划,动态规划,1动态规划的基本概念和方法基本概念与名词解释最优化原理与动态规划的基本方法2动态规划模型的建立与求解步骤建立动态规划模型的基本要求动态规划的求解步骤3动态规划的应用举例定价问题资源分配问题生产存储问题,第一节动态规划的基本概念与方法1动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划(D.P.DynamicProgram)：多阶段决策问题最优化的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划(D.P.)的起源：1951年,美国数学家R.Bellman(贝尔曼)等人提出最优化原理，从而建立动态规划，他的名著动态规划于1957年出版。,四、动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。,名词解释,例1某公司欲将一批货物从城市A运到城市E去，如图所示，走哪条路线最好？,1、阶段(stage)k：把所给问题的过程，恰当地分成若干个相互联系的阶段。描述阶段的变量称为阶段变量，常用k表示。k=1、2、3、4。2、状态(state)Sk：状态表示每个阶段开始所处的状态,即是每一阶段的出发位置.阶段的起点.通常一个阶段有多个状态.记为Sk.S1=A，S2=B1,B2,B3，S3=C1,C2,C3,S4=D1,D2。,3、决策(decision)uk(sk)：从一个阶段某状态演变到下一个阶段某状态的选择.常用uk(sk)表示第k阶段当状态处于sk时的决策变量.决策集用Dn(Sk)表示.就是阶段的终点.D1(S1)=u1(A)=B1,B2,B3=S2，D2(S2)=U2(B1),U2(B2),U2(B3)=C1,C2;C1,C2,C3;C2,C3=C1,C2,C3=S3，D3(S3)=U3(C1),U3(C2),U3(C3)=D1,D2;D1,D2,D3;D1,D2,D3=D1,D2,D3=S4，D4(S4)=U4(D1),U4(D2),U4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5，D5(S5)=X5(E1),X5(E2)=F;F=F。,4、策略(policy)：全过程中各个阶段的决策Un组成的有序总体Un.如AB2C1D1E5、子策略(sub-policy)：剩下的M个阶段构成M子过程,相应的决策系列叫M子策略.如C1D1E6、状态转移方程：前一阶段的终点(决策)是后前一阶段的起点(状态).Uk=Sk+17、指标函数：各个阶段的数量指标,记为Vk,n(sk,Uk).如上例中,用dk(sk,Uk)表示距离.d2(B3,C2)=8,d3(C2,D2)=2等.8、目标函数:策略的数量指标值,记为Z=optv1(s1,u1)*vn(sn,un).其中：opt为max或min，*为运算符号.如上例中，Z=mind1(s1,u1)+dn(sn,un)=mind1+d2+dn,一、R.Bellman最优化原理：作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。,最优化原理,二、指标递推方程：fn*(Sn)=optvn(sn,un)*vn(sn,un),xnDn(Sn)如上例：fn*(Sn)=minvn(sn,un)+fn+1*(Sn+1),n=3、2、1xnDn(Sn)f4*(S4)=minv4(s4,u4)x4D4(S4)三、求解过程：用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，形成最优策略，获得最优策略指标值。,一、建立动态规划模型的基本要求,将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。,二、动态规划的求解步骤,正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。,例2：求下列图中A到F的最短路线及最短路线值。,1、阶段(stage)n：n=1、2、3、4、5。2、状态(state)Sn：S1=A，S2=B1,B2,B3，S3=C1,C2,C3，S4=D1,D2,D3，S5=E1,E2。3、决策(decision)Xn：决策集Dn(Sn)。D1(S1)=X1(A)=B1,B2,B3=S2，D2(S2)=X2(B1),X2(B2),X2(B3)=C1,C2;C1,C2,C3;C2,C3=C1,C2,C3=S3，D3(S3)=X3(C1),X3(C2),X3(C3)=D1,D2;D1,D2,D3;D1,D2,D3=D1,D2,D3=S4，D4(S4)=X4(D1),X4(D2),X4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5，D5(S5)=X5(E1),X(E2)=F;F=F。,4、状态转移方程：Xn=Sn+15、指标函数(距离)：dn(sn,xn).d2(B3,C2)=1,d3(C2,D3)=6等。6、指标递推方程：fn*(Sn)=mindn(sn,Xn)+fn+1*(Sn+1)，n=4、3、2、1UnDn(Sn)f5*(S5)=minV5(s5,X5)X5D5(S5),1,1,F,2,2,F,4+1=5,2+2=4,4,E2,6+1=7,9+2=11,7,E1,7+1=8,5+2=7,7,E2,1+4=5,5+7=12,/,5,D1,8+4=12,4+7=11,6+7=13,11,D2,4+4=8,4+7=11,2+7=9,8,D1,9+5=14,5+11=16,/,14,C1,4+5=9,3+11=14,5+8=13,9,C1,/,1+11=12,7+8=15,12,C2,3+14=17,5+9=14,4+12=16,14,B2,最短路线值为：f1*(s1)=14最短路线求解如下：,即：AB2C1D1E2F,第三节动态规划的应用举例,定价问题资源分配问题生产存储问题,一、定价问题,某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。表3-2每年预计利润额,建立数学模型,按年划分阶段，k=1,2,.,5每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是：采用逆序算法，因此状态转移方程是最优值函数递推方程为,进行各阶段的计算,采用逆序法，设当k=5时，S5=(5,6,7,8)，由表3-1得到当k=4时，S4=(5,6,7,8)，由递推方程得,继续求解,同理得其它各阶段的最优解,反推得最优路线,按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。最大利润值为92万元。,也可用决策图求解,二、资源分配问题,某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂利用设备后可产生如表3-2所示的利润，应怎么分配设备可使公司总利润最大？,建立数学模型,按工厂次序划分阶段，k=1，2，3，4状态变量为各阶段可用于分配的设备总台数决策变量是分配给第k工厂的设备数采用逆序算法，状态转移方程最优值函数递推方程,第4阶段的最优解,当k=4时，S4=(0,1,2,3,4,5),第3阶段的最优解,当k=3时，S3=(0,1,2),第3阶段的最优解（续）,当k=3时，S3=3,第3阶段的最优解（续）,当k=3时，S3=4,第3阶段的最优解（续）,当k=3时，S3=5,第2阶段的最优解,当k=2时，S2=(0,1,2),第2阶段的最优解（续）,k=2时，S2=3,第2阶段的最优解（续）,当k=2时，S2=4,第2阶段的最优解（续）,当k=2时，S2=5,第1阶段的最优解（续）,当k=1时，S1=5,反向求最佳状态路线,三、生产存储问题,某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。,已知的其它条件,已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。设第k月的生产量uk，存储量为Sk,则总成本为,建立数学模型,以月划分阶段，k=1,2,3,4各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。采用逆序算法，则状态转移方程为最低成本递推公式是,第四阶段的最优解,当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4),第三阶段最优解,当k=3时，由于，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6),第