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

《西安电子科技大学数学建模讲义第八讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲人:穆学文西安电子科技大学数学系Email:mxw1334@126.com数学建模讲义数学建模专题讲座最优化模型---动态规划动态规划1动态规划的基本概念和方法基本概念与名词解释最优化原理与动态规划的基本方法2动态规划模型的建立与求解步骤建立动态规划模型的基本要求动态规划的求解步骤3动态规划的应用举例定价问题资源分配问题生产存储问题第一节动态规划的基本概念与方法1动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划(D.P.–DynamicProgram)：多阶段决策问题最优化的一

2、种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划(D.P.)的起源：1951年,美国数学家R.Bellman(贝尔曼)等人提出最优化原理，从而建立动态规划，他的名著《动态规划》于1957年出版。四、动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。名词解释例1某公司欲将一批货物从城市A运到城市E去，如图所示，走哪条路线最好？1、阶段(stage)k：把所给问题的过程，恰当地分成若干个相互联系的阶段。描述阶段的变量称为阶段变量，常

3、用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

4、,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}.如AB2C1D1E5、子策略(sub-policy)：剩下的M个阶段构成M子过程,相应的决策系列叫M子策略

5、.如C1D1E6、状态转移方程：前一阶段的终点(决策)是后前一阶段的起点(状态).Uk=Sk+17、指标函数：各个阶段的数量指标,记为Vk,n(sk,Uk).如上例中,用dk(sk,Uk)表示距离.d2(B3,C2)=8,d3(C2,D2)=2等.8、目标函数:策略的数量指标值,记为Z=opt[v1(s1,u1)*…*vn(sn,un)].其中：opt为max或min，*为运算符号.如上例中，Z=min[d1(s1,u1)+…+dn(sn,un)]=min[d1+d2+…+dn]一、R.Bellman最优化原理：作为整个过程的最优策略，无论过去的状态和决策如何，对

6、前面的决策形成状态而言，余下的诸决策必构成最优策略。即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。AMB最优化原理二、指标递推方程：fn*(Sn)=opt[vn(sn,un)*vn(sn,un)],xn∈Dn(Sn)如上例：fn*(Sn)=min[vn(sn,un)+fn+1*(Sn+1)],n=3、2、1xn∈Dn(Sn)f4*(S4)=min[v4(s4,u4)]x4∈D4(S4)三、求解过程：用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优，形成最优策略，获得最优策略指标值。一、建立动态规划模型的基本要求

7、将问题划分成若干阶段。有的问题的阶段性很明显，有的则不明显，需要分析后人为假设。确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。状态变量应当满足无后效性要求。明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。二、动态规划的求解步骤正确划分阶段。确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。确定求解的递推顺序，给出状态转移方程。确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。递推求解。与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。例2：求下