《(数学建模教材)4第四章动态规划_.docx》由会员分享，可在线阅读，更多相关《(数学建模教材)4第四章动态规划_.docx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 (数学建模教材)4第四章动态规划_ (数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划第四章动态规划1引言1.1动态规划的发展及研究内容动态规划dynamicprogramming是运筹学的一个分支，是求解决策经过decisionprocess最优化的数学方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策经过(multistepdecisionprocess)的优化问题时，提出了著名的最优性原理principleofoptimality，把多阶段经过转化为一系列单阶段问题，逐个求解，创立了解决这类经过优化问题的新方法动态规划。1957年出版了他的名著（Dynam
2、icProgramming），这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短道路、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。固然动态规划主要用于求解以时间划分阶段的动态经过的优化问题，但是一些与时间无关的静态规划如线性规划、非线性规划，只要人为地引进时间因素，把它视为多阶段决策经过，可以以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法如线性规划是一种算法。因此，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则
3、，而必须对详细问题进行详细分析处理。因而，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。例1最短道路问题图1是一个线路网，连线上的数字表示两点之间的距离或费用。试寻求一条由A到G距离最短或费用最省的道路。图1最短道路问题例2生产计划问题工厂生产某种产品，每单位千件的成本为1千元，每次开工的固定成本为3千元，工厂每季度的最大生产能力为6千件。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4千件。假如工厂在第一、二季度将全年的需求都生产出来，自然能够降低成本少付固定成本费，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的
4、存储费为0.5千元。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用生产成本和存储费最少。1.2决策经过的分类根据经过的时间变量是离散的还是连续的，分为离散时间决策经过discrete-time-56-(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划decisionprocess和连续时间决策经过continuous-timedecisionprocess；根据经过的演变是确定的还是随机的，分为确定性决策经过deterministicdecisionprocess和随机性决策经过stochasticdecisionprocess，其中应
5、用最广的是确定性多阶段决策经过。2基本概念、基本方程和计算方法2.1动态规划的基本概念和基本方程一个多阶段决策经过最优化问题的动态规划模型通常包含下面要素。2.1.1阶段阶段(step)是对整个经过的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,L,n表示。在例1中由A出发为k=1，由Bi(i=1,2)出发为k=2，依此下去从Fi(i=1,2)出发为k=6，共n=6个阶段。在例2中根据第一、二、三、四季度分为k=1,2,3,4，共四个阶段。2.1.2状态状态state表示每个阶段开场时经过所处的自然状况。它应能描绘经过的特征并且无后效
6、性，即当某阶段的状态变量给定时，这个阶段以后经过的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接能够观测的。描绘状态的变量称状态变量statevariable。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用xk表示第k阶段的状态变量，它能够是一个数或一个向量。用Xk表示第k阶段的允许状态集合。在例1中x2可取B1,B2，或将Bi定义为i(i=1,2)，则x2=1或2，而X2=1,2。n个阶段的决策经过有n+1个状态变量，xn+1表示xn演变的结果。在例1中x7取G，或定义为1，即x7=1。根据经过演变的详细情况，状态变量能够是离散的或连续的。为
7、了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。2.1.3决策当一个阶段的状态确定后，能够作出各种选择进而演变到下一阶段的某个状态，这种选择手段称为决策decision，在最优控制问题中也称为控制control。描绘决策的变量称决策变量decisionvariable，变量允许取值的范围称允许决策集合setofadmissibledecisions。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示xk的允许决策集合。在例1中u2(B1)可取C1,C2或C3，可记作u2(1)=1,2,3，而U2(1)=1,2,
8、3。决策变量简称决策。2.1.4策略决策组成的序列称为策略policy。由初始状态x1开场的全经过的策略记作p1n(x1)，即p1n(x1)=u1(x1),u2(x2),L,un(xn).由第k阶段的状态xk开场到终止状态的后部子经过的策略记作pkn(xk)，即pkn(xk)=uk(xk),L,un(xn)，k=1,2,L,n-1.类似地，由第k到第j阶段的子经过的策略记作-57-(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划pkj(xk)=uk(xk),L,uj(xj).可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用P1n
9、(x1),Pkn(xk),Pkj(xk)表示。2.1.5.状态转移方程在确定性经过中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程equationofstatetransition表示这种演变规律，写作xk+1=Tk(xk,uk),k=1,2,L,n.在例1中状态转移方程为xk+1=uk(xk)。2.1.6.指标函数和最优值函数指标函数(objectivefunction)是衡量经过优劣的数量指标，它是定义在全经过和所有后部子经过上的数量函数，用Vk,n(xk,uk,xk+1,L,xn+1)表示，k=1,2,L,n。指标函数应具有可分离性，即Vk,n可表为xk,uk,V
10、k+1,n的函数，记为Vk,n(xk,uk,xk+1,L,xn+1)=?k(xk,uk,Vk+1,n(xk+1,uk+1,L,xn+1)并且函数?k对于变量Vk+1,n是严格单调的。经过在第j阶段的阶段指标取决于状态xj和决策uj，用vj(xj,uj)表示。指标函数由vj(j=1,2,L,n)组成，常见的形式有：阶段指标之和，即nVk,n(xk,uk,xk+1,L,xn+1)=vj(xj,uj)，j=k阶段指标之积，即nVk,n(xk,uk,xk+1,L,xn+1)=vj(xj,uj)，j=k阶段指标之极大或极小，即1Vk,n(xk,uk,xk,L,x1)=max(min)vj(xj,uj).
11、+n+1kjn这些形式下第k到第j阶段子经过的指标函数为Vk,j(xk,uk,L,xj+1)。根据状态转移方程指标函数Vk,n还能够表示为状态xk和策略pkn的函数，即Vk,n(xk,pkn)。在xk给定时指标函数Vk,n对pkn的最优值称为最优值函数optimalvaluefunction，记为fk(xk)，即fk(xk)=optVk,n(xk,pkn)，pknPkn(xk)其中opt可根据详细情况取max或min。2.1.7最优策略和最优轨线使指标函数Vk,n到达最优值的策略是从k开场的后部子经过的最优策略，记作p*=u,L,u。p是全经过的最优策略，简称最优策略optimalpolicy
12、。从初始knkn1n状态x(=x*)出发，经过根据p*和状态转移方程演变所经历的状态序列111n*x,x,L,x称最优轨线optimaltrajectory。12-58-n+1(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划2.1.8递归方程如下方程称为递归方程?fn+1(xn+1)=0或2?f(x)=(x,u)?f(x),k=n,L,1optvk+1k+1?kkkkkuU(x)kkk在上述方程中，当?为加法时取fn+1(xn+1)=0；当?为乘法时，取fn+1(xn+1)=1。动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程1
13、和递归方程2求解动态规划的经过，是由k=n+1逆推至k=1，故这种解法称为逆序解法。当然，对某些动态规划问题，可以采用顺序解法。这时，状态转移方程和递归方程分别为：rxk=T(xk+1,uk),k=1,L,n，k?f0(x1=0或?f(x)=optv(x,u)?f(x),k=1,L,nkk+1kk+1kk-1k?uUr+(xk+)kk11例3用lingo求解例1最短道路问题。model:TitleDynamicProgramming;sets:vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L;road(vertex,vertex)/
14、AB1,AB2,B1C1,B1C2,B1c3,B2C2,B2C3,B2C4,C1D1E1D1,C1E1,D1F1,E1D2,C2E2,D2F2,E2D1,C2E2,D2F1,E2D2,C3E3,D3F2,E3D2,C3E2,D3F1,E3D3,C4D2,C4D3,E3,F2,F1G,F2G/:D;endsetsdata:D=533151522333663368876462382543;L=0,;enddatafor(vertex(i)|i#GT#1:L(i)=min(road(j,i):L(j)+D(j,i);end纵上所述，假如一个问题能用动态规划方法求解，那么，我们能够按下列步骤，首先建立
15、起动态规划的数学模型：i将经过划分成恰当的阶段。ii正确选择状态变量xk，使它既能描绘经过的状态，又知足无后效性，同时确定允许状态集合Xk。iii选择决策变量uk，确定允许决策集合Uk(xk)。iv写出状态转移方程。v确定阶段指标vk(xk,uk)及指标函数Vkn的形式阶段指标之和，阶段指标之积，阶段指标之极大或极小等。vi写出基本方程即最优值函数知足的递归方程，以及端点条件。3逆序解法的计算框图-59-(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。一般化的自由终端条件为fn
16、+1(xn+1,i)=?(xn+1,i),i=1,2,L,nn+1(3)其中?为已知。固定始端条件可表示为X=x=x*。111假如状态xk和决策uk是连续变量，用数值方法求解时需根据精度要求进行离散化。设状态xk的允许集合为Xk=xki|i=1,2,L,nk,i=1,2,L,nk,k=1,2,L,n.决策uki(xki)的允许集合为=u|j=1,2,L,nki,i=1,2,L,nk,k=1,2,L,n.(j)(j)Ukiki状态转移方程和阶段指标应对x的每个取值x和u的每个取值u计算，即kkikiki(j)(j)Tk=Tk(,，vk=v(x,u)。最优值函数应对xk的每个取值xki计算。基本方
17、xkiuki程能够表为kikif(j)(x)=v(x,u(j)+f(T(x,u(j),kkikkikik+1kkikif(x)=optf(j)(x),4kkikkijj=1,2,L,nki,i=1,2,L,nk,k=n,L,2,1.图2解法框图-60-(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划根据3，4逆向计算出f(x*)，为全经过的最优值。记状态x的最优决策为11kiu*(x)，由x*和u*(x)根据状态转移方程计算出最优状态，记作x*。并得到相应的kiki1kikik*最优决策，记作u(x)。于是最优策略为u(x),u(x),L,u(x)。kk1122nn算法程序的框
18、图如图2所示。图的左边部分是函数序列的递推计算，可输出全经过最优值f(x*)，假如需要还11*能够输出后部子经过最优值函数序列f(x)和最优决策序列u(x)。计算经过中存kkifk(xki)是备计算fk-1之用，在fk-1算完后可用kki*fk-1将kf替换掉；存u(x)是备右边kki部分读u*(x*)之用。kk图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略*u(x),u(x),L,u(x)和最优轨线x,x,L,x。1122nn12n4动态规划与静态规划的关系动态规划与静态规划线性和非线性规划等研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上能够互
19、相转换。动态规划能够看作求决策u1,u2,L,un使指标函数V1n(x1,u1，u2,L,un)到达最优最大或最小的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上能够用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就能够用动态规划方法求解。下面用例子讲明。例4用动态规划解下列非线性规划nmaxgk(uk)；k=1nuk=a,uk0.s.t.k=1其中gk(uk)为任意的已知函数。解按变量uk的序号划分阶段，看作n段决策经过。设状态为x1,x2,L,xn+1，取问题中的变量u1,u2,L,un为决策。状态转移方程为x1=a,xk+1=xk-uk
20、,k=1,2,L,n.取gk(uk)为阶段指标，最优值函数的基本方程为注意到xn+1=0fk(xk)=maxgk(xk)+fk+1(xk+1)；0ukxk0xka,k=n,n-1,L,2,1；fn+1(0)=0.*根据逆序解法求出对应于x每个取值的最优决策u(x)，计算至f1(a)后即可利kkk用状态转移方程得到最优状态序列x*和最优决策序列u*(x*)。k与静态规划相比，动态规划的优越性在于：kki能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即便指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全经过化为-61-(数学建模教材)4第四章动态规划(数学建模教材
21、)4第四章动态规划一系列构造类似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。十分是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，能够对每个子经过用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。ii能够得到一族最优解。与非线性规划只能得到全经过的一个最优解不同，动态规划得到的是全经过及所有后部子经过的各个状态的一族最优解。有些实际问题需要这样的解族，即便不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族能够用来寻找次优
22、策略。iii能够利用经历提高求解效率。假如实际问题本身就是动态的，由于动态规划方法反映了经过逐段演变的前后联络和动态特征，在计算中能够利用实际知识和经历提高求解效率。如在策略迭代法中，实际经历能够帮助选择较好的初始策略，提高收敛速度。动态规划的主要缺点是：i没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判定一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行详细分析，构造详细的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵敏的技巧性，这就带来了应用上的局限性。ii用数值方法求解时存在维数灾curseofdimensionality。若一维状
23、态变量有m个取值，那么对于n维问题，状态xk就有m个值，对于每个状态值都要计算、存储函数fk(xk)，对于n稍大的实际问题的计算往往是不现实的。目前还没有克制维数灾的有效的一般方法。n5若干典型问题的动态规划模型5.1最短道路问题对于例1一类最短道路问题shortestPathProblem，阶段按经过的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有xk+1=uk(xk)，阶段指标为相邻两段状态间的距离dk(xk,uk(xk)，指标函数为阶段指标之和，最优值函数fk(xk)是由xk出发到终点的最短距离或最小费用，基本方程为fk(xk)=mindk(xk,uk(xk)+fk
24、+1(xk+1),k=n,L,1;uk(xk)fn+1(xn+1)=0.利用这个模型能够算出例l的最短道路为AB1C2D1E2F2G，相应的最短距离为18。5.2生产计划问题对于例2一类生产计划问题Productionplanningproblem，阶段按计划时间自然划分，状态定义为每阶段开场时的储存量xk，决策为每个阶段的产量uk，记每个阶段的需求量已知量为dk，则状态转移方程为xk+1=xk+uk-dk,xk0,k=1,2,L,n.(5)设每阶段开工的固定成本费为a，生产单位数量产品的成本费为b，每阶段单位数量产品的储存费为c，阶段指标为阶段的生产成本和储存费之和，即?a+bu,u0kkv
25、(x,u)=cx+?(6)kkkk?0-62-(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划指标函数Vkn为vk之和。最优值函数fk(xk)为从第k段的状态xk出发到经过终结的最fk(xk)=minvk(xk,uk)+fk+1(xk+1),k=n,L,1.ukUk其中允许决策集合Uk由每阶段的最大生产能力决定。若设经过终结时允许存储量为x，则终端条件是n+1f(x0)=0.7n+1n+157构成该问题的动态规划模型。5.3资源分配问题一种或几种资源包括资金分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题resourceallocatingProblem能够是多
26、阶段决策经过，可以以是静态规划问题，都能构造动态规划模型求解。下面举例讲明。例5机器能够在高、低两种负荷下生产。u台机器在高负荷下的年产量是g(u)，在低负荷下的年产量是h(u)，高、低负荷下机器的年损耗率分别是a1和b100，即高、低负荷下每台机器的年产量分别为和，结果将有什么特点。解年度为阶段变量k=1,2,L,n。状态xk为第k年初完好的机器数，决策uk为第k年投入高负荷运行的台数。当xk或uk不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。机器在高、低负荷下的年完好率分别记为a和b，则a=1-a1，b=1-b1，有a(数学建模教材)4第四章动态规划(数学建模教
27、材)4第四章动态规划品，则纯收入为5x，若投入y台机器生产B种产品，则纯收入为4y，又知：生产A种产品机器的年折损率为20%，生产B产品机器的年折损率为10%，问在5年内怎样安排各年度的生产计划，才能使总收入最高？解年度为阶段变量k=1,2,3,4,5。令xk表示第k年初完好机器数，uk表示第k年安排生产A种产品的机器数，则xk-uk为第k年安排生产B种产品的机器数，且0ukxk。则第k+1年初完好的机器数xk+1=(1-0.2)uk+(1-0.1)(xk-uk)=0.9xk-0.1uk12令vk(xk,uk)表示第k年的纯收入，fk(xk)表示第k年初往后各年的最大利润之和。显然f6(x6)
28、=0则13fk(xk)=maxvk(xk,uk)+fk+1(xk+1)0ukxk=max5uk+4(xk-uk)+fk+1(xk+1)=maxuk+4xk+fk+1(xk+1)140ukxk1k=5时，由13、14式得0ukxkf5(x5)=maxu5+4x50u5x5u5+4x5关于u5求导，知其导数大于零，所以u5+4x5在u5等于x5处获得最大值，即u5=x5时，f5(x5)=5x5。2k=4时，由12、14式得f4(x4)=maxu4+4x4+5x50u4x4=maxu4+4x4+5(0.9x4-0.1u4)=max0.5u4+8.5x40u4x4当u4=x4时，f4(x4)=9x43
29、k=3时，0u4x4f3(x3)=maxu3+4x3+9x40u3x3=maxu3+4x3+9(0.9x3-0.1u3)=max0.1u3+12.1x30u3x3当u3=x3时，f3(x3)=12.2x34k=2时，0u3x3f2(x2)=maxu2+4x2+12.2x3=max-0.22u2+14.98x20u2x2当u2=0时，f2(x2)=14.98x2。5k=1时，0u2x2f1(x1)=maxu1+4x1+14.98x2=max-0.498u1+17.482x10u1x10u1x1当u1=0时，f1(x1)=17.482x1。由于x1=1000台-64-(数学建模教材)4第四章动态规
30、划(数学建模教材)4第四章动态规划所以由12式，进行回代得x2=0.9x1-0.1u1=900台x3=0.9x2-0.1u2=810台x4=0.9x3-0.1u3=648台x5=0.9x4-0.1u4=518.4台注：x5=518.4台中的0.4台应理解为有一台机器只能使用0.4年将报废。例7求解下面问题2maxz=uuu123?u1+u2+u3=c(c0)?ui0i=1,2,3解：按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为x1,x2,x3,x4，并记x1=c；取问题中的变量u1,u2,u3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(xk)表示第k阶段
31、的初始状态为xk，从k阶段到3阶段所得到的最大值。设x3=u3，x3+u2=x2，x2+u1=x1=c则有u3=x3，0u2x2，0u1x1用逆推解法，从后向前依次有*f3(x3)=maxu3=x3及最优解u=x33u3=x322f2(x2)=maxuf(x)=maxu(x-u2)=maxh2(u2,x2)233220u2x20u2x20u2x2dh由2du22x3=2ux-3u2=0，得u=和u=0舍去222222d2h22=2x2-6u2=-2x2(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划所以2x3=1c，f(x)=1c316u*=22222由x=x-u*=3c-1c
32、=1c322424所以=1c，f(x)=1cu*33344因而得到最优解为：u*=1c，u*=1c，u*=1c；123424最大值为：maxz=f(c)=1c4。164习题四1.用Matlab编程求例6的解。2.有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如表1所示。表1问指派哪个人去完成哪项工作，可使总的消耗时间为最小？试对此问题用动态规划方法求解。3.为保证某一设备的正常运转，需备有三种不同的零件E1,E2,E3。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000元。已知备用零件数与它的可靠性和费用的关系如表2所示。表2现要求在既不超
33、出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？4.某工厂购进100台机器，准备生产I、II两种产品，若生产产品I，每台机器每年可收入45万元，损坏率为65；若生产产品II，每台机器每年收入为35万元，损坏率为35，估计三年后将有新型机器出现，旧的机器将全部淘汰。试问每年应怎样-66-备件数增加的可靠性设备的费用千元E1E2E3E1E2E31230.30.40.50.20.50.90.10.20.7123356234工作工人ABCD甲15182124乙19232218丙26171619丁19212317(数学建模教材)4第四章动态规划(数学建模教材)4第四章动态规划安排生产，使在三年内收入最多？53名商人各带1名随从乘船渡河，一只小船只能包容2人，由他们本人划行。随从们密约，在河的任一岸，一旦随从人数比商人多，就杀商人。此密约被商人知道，怎样乘船渡河的大权把握在商人们手中，商人们如何安排每次乘船方案，才能安全渡河呢？6某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间单位：天如表3所示，试求最优的加工顺序和总加工天数。表3-67-任务车间123456印刷车间装订车间381012592695112