动态规划与最优控制模

#第四章最优控制模型管理、决策方面应用，因此可说管理决策模型)§1最优控制的问题提法：§1.1最优控制问题举例、例，详见最优控制课听课笔记第一节；§1.2最优控制数学模型最优控制模型问题的数学描述――最优控制模型。寻找u*(t)eU(开，闭)[t,tIt可以固定或自由，使得:0ffJtu*(t)]=minJtu(t)]ueUs.t3=f(x(t),u(t),t)dts.tx(t)=x00x(t)=x(t)=x00x(t)=xeM='x(t)x(t)eR,ffffg1g2(x(t(x(tf),),tftf)=0其中：X(t)eRn，且x(t)eCl(—阶连续可微)，U(t)eU<Rm,f[x(t),u,t]：向量值函数，且f(•)对x(t),u(t),t连续，对x(t),t连续可微。Jtu(t)1=®(x(t),t)+fL(x(t),u(t),t)dt,fft0沁(t」t」L[x(t),u(t),t1对x(t),t都可微。上述最优控制的离散模型：求｛u*(i),x*(i)｝，使得目标泛函：J=±iL(x(i),u(i),i)达到最小。i=0而且满足：x(k+x(k+1)=f(x(k),u(k),k)状态方程：4x(0)=x0x(k)eMf最优控制问题的求解方法：古典变分法：u开集；极大值原理：U闭集；现代变分法，把古典变分法看作特例动态规划：便于数值计算，并有通用算法；发展了变分法，结果是充分条件。§2最优控制模型的动态规划解法§2.1动态规划方法概述§2.2生产——库存——销售管理系统的动态规划解法§2.1动态规划方法概述某一类管理问题的数学模型(状态方程)是一个差分方程x(k+1)=f(x(k),u(k),k)状态方程：x(0)=x0x(k)eMf目标泛函：J=VL(x(i),u(i),i)达到最小。二0即：此为一个N阶决策问题：动态规划法是求这一决策问题的有效办法，具有明显优点：将一个N阶决策问题转化为多次一步决策问题，即数学上的嵌入原理——将求一条极值曲线问题，嵌入到求一族极值曲线的更广泛的类似问题中；大大简化了计算量；具有局部优，就是整体优的最优性原理：可广泛应用于运输系统、生产库存管理系统、生产计划制定及最优投资分配问题、最优价格制定问题。下面以最短路问题举例说明这种方法一、最短路问题(最小时间问题)1问题：若有一辆汽车以S城出发经过若干城市到达F城，如图：P,Q,i=1,2,3，ii是一些可以通过的城镇。图中两点间的数字：可以表示两城镇之间的距离(单位10公里)，也可以表示行驶两城镇所用时间(应综合考虑：距离远近，路面好坏，是否拥挤等情况)。

于是：汽车从S到F可经多种途径选择到达F。问题是：从多种途径选择方案中，决定一种使S到F所走路线最短。或者若图中数字表示时间，则决定一种路径使从S到F所用时间最短。2．方法：I.决策树法（穷举法）：决策树法是最容易想到的一种方法，但运算量很大——即把所有可能选择的路途所用的时间都求出来，然后取最小值，即有最优策略（最优决策）。即：SPi*即：SPi*Q*F=mini{sPQFi=1,2,3}ii因此有：因此有：1514161514131817因此，最终得出：SQPPF=min{SPQF|i=1,2,3}123ii困难：这样共有8条线路可选择，每条线路要作3次运算。第1次：STP/QTP/QTQ；第2次：P/QTP/Q112222233第3次：P或QTF33因此，共需24次运算：8X3=24次，若阶段更多，则计算量更大。II•“走一步瞧一步”（瞎子爬山？近视眼？）法：第一步：从S到P或Q:显然SP=4<SQ=5，因此取决策SP；11111第二步：从P到P或Q:显然PP=6=PQ，因此取PP,QQ均可，但从P到122121212122P或Q距离为1,而Q到PP距离为2,因此，第2步决策为P,因此取PP；33223212第三步：P到P或P到Q，均有PP=PQ=1，但Q到F的距离为3,因此第332323233步取路线PQ。23

因此使用这种方法得到的决策为：SPPQF=4+6+1+3=14123显然不是“最优决策”，同时还有：SQPPF=14123问题出现在“局部优不能代替整体优”的问题。III.动态规划：即可把每一步决策都看成一个状态的转移，而每一种状态的转移又影响到下一阶段的状态，因此又是动态的，故称为动态规划法。将上述问题分为四个阶段的多阶决策问题，故可将问题分为四阶段问题来考虑：第一阶段问题：StP/Q11第二阶段问题：第一阶段问题：StP/Q111122tFtF解题方法从最后一个阶段开始：1°分别计算P,Q至UF的最小代价，此处花费代价为时间，记为J，用J[p1J[Q]分别333表示P或Q到F的代价，则显然有:33J*[P1=4J*[Q1=3332°由后往前，考虑倒数第二阶段（即第三阶段），再把第三阶段和第四阶段联合作为一个子问题来考虑，若从P出发到F，则有两种可能:2PPF23PQF23J=1+J*[P3]=1+4=5J=2+J*Iq]=1+3=43线路PQF最短，且J*[P]=4，故将线路PQF记成P2®Q32322323类似以Q出发到F，则有两种可能:2Q2P3FJ=2+J[P3]=2+4=6、QQFJ=2+J[q]=2+3=5233线路QQF最短’贝Uj=J*[q]=5'故将线路QQF记成Q⑤Q2322323.3°再由2、3、4这三个阶段构成的子问题：若从P出发到F有两种可能：1PPF12PQF12J=6+J*[P2]=6+4=610J=6+J*[Q]=6+5=112有线路ppF最短，且J*[P]=10，故将PPF记成：P⑩P1211212若从Q出发到F有两种可能:1QPF12QQF12J=4+J*[P2]=4+4=8J=7+J*[Q]=7+5=12

2...有线路QPF最短，则J*[Q]=8，故将QPF记成：Q⑧P12112124°把由1、2、3、4阶段作为子问题来考虑：从S出发到F有两种可能:sPF1SQF1且J=4+J*4+10=14且J=5+J*[Q]=5+8=131故：SQ1315°因此有最优策略：SQF1即：SQF=SQPQF，J*[S]=131123s@第1阶段第2阶段第3阶段第4阶段除“二决一”比较之外，且运算只用了10次，而穷举法则算了24次，上次这种动态规划的办法：是将把一个四阶段决策问题化为四个互相嵌入子问题，逐一进行简化的计算方法，即数学上嵌入定理。IV.最优性原理“最优策略的一部分也是最优策略”例如：上例中知：SQPQF是最优决策，则QPQF也一定是从Q]出发到F的最优1231231决策：证明[反证法]:设SQ]P2Q3F是最优决策，则Q]P2Q3F不是最优决策，则必存在另一个最优决策，不妨设为Q1Q2Q3F为最优决策。因而，SQ1Q2Q3F是整体最优决策，因而与SQ]P2Q3F是最优决策相矛盾，因而原结论正确。一般有最优性原理；如果u*(0),u*(1),…,u*(N-1)是N阶决策问题的最优策略序列，那么：u*(l),…,u*(N-1)也是一个最优策略序列，其初始状态为：x(1)=f(x(0),u*(0))证明：同最短路.4．多阶段决策问题的一般想法：设某系统的状态方程为：fx(i+1)=f(x(i),u(i),i)x(0)=x设某系统的状态方程为：0目标函数为：J=±-1L(x(i),u(i),i)，J表示控制N步时的目标函数值。NNi=0最优控制问题，即：求最优决策序列｛u*(i)｝=缶*(0),…,u(N-1)｝，使J取最小(大)N值。为简化假定为定常状态，即L不明显还有时间变量ifx(i+1)=f(x(i),u(i))(1)因而有：＜1x(0)=x0(2)J=SL(x(i),u(i))Ni=0(3)对目标函数(3)逐次应用(1)式有：JN=L(x(0),u(0))+L(x(1),u(1))+…+L(x(N—1),u(N—1)),=L(x(0),u(0))+L(f(x(0),u(0)),u(1)),+•••+L(f(f(…(f(x(0),u(0)),u(1))•••,u(N—2),u(N—1))))因此，可以由上式看出：J只依赖于：x(0),u(1),…,u(N-1)N因而可写成：J=J(x(0),u(1),…,u(N—1))又若用某种方法求出了最优决策：u*(0),…,u*(N-1)，贝l」J的最小值只依赖于初N始值x(0)，记为J*(x(0))，它可用下式来定义：NJ*(x(0))=minJ(x(0),u(l),…，u(N一1))Nu(0),u(1),…，u(N-1)N初始值是可变化的，因此：J*(x(0))表示初始状态为x(0)时，控制N步的目标函数最小值。N5．动态规划的基本方程：动态规划的基本方程，给出N阶决策问题的目标函数最优值与它的子问题(N-1阶决策问题)目标函数最优值之间的递推关系式，它是用动态规划解一切多阶决策问题的基础。设u*(0)已求出，则求序列｛u*(1),u*(2),…,u*(N-1)｝的问题，构成一个以x⑴二f(x(0),u(0))为初始条件的N-1阶决策问题，若记这一子问题的目标函数最小值为：J*(x(1))；又若记J*(x(0))为N阶决策问题最小值，则我们可以导出J*(x(0))N-1NN与J*(x(1))之间的关系：N-1由于J*(x(0))=minL(x(k),u(k))|NTOC\o"1-5"\h\zu(0),u(1),…,u(N-1)I0Jk—0=min<L(x(0),u(0))+Sl(x(k),u(k))]u(0)-u(N-1)〔k—1则第一项：minL(x(0),u(0))—minL(x(0),u(0))u(0),…,u(N-1)u(0)第二项：min<士L(x(k),u(k))>并不明显依赖u(0)，u(0),u(1)…,u(N-1)〔k—1J但由状态方程：x(1)—f(x(0),u(0))x(N-1)—f(x(N-2),u(N-2))可知：实际上第二项仍依赖于u(0),u(1),…,u(N-1)，因此，第二项可写成：min£L(x(k),u(k))u(0),…,u(N-1)、k=0丿=min<mm为L(x(k),u(0)u(k))>=minu(0)u(1)，…，u(N-1)N-1因此有：动态规划基本方程:J*(x(0))=min(x(0),u(0))+J*(x(1))^NN-1…21u(0此给出了J*(x⑴)与J*(x(0))之间的递推关系。它是动态规划的基本方程。N-1N类似有动态规划更一般的基本方程：J*(x(i))=min(x(i),u(i))+J*(x(i+1))^(**)N—iN-i-1I1因此依据基本递推方程的递推关系：可以把一个多阶决策问题化为若干个子问题，而在决策的每一个阶段中只须对一个变量进行最优化决策即可。例如：J*(x(N-1))=min£(x(N-1),u(N-1))}1u(N-1)是对一个单变量u(N-1)的优化问题，当J*(x(N-1))求出后，由基本递推方程(**)式可得:1J*(x(N-2))=min£(x(N-2),u(N-2))+J*(x(N-1))}

2u(N-2)1这又是对u(N-2)的最优化决策问题，因而把原来N阶决策问题化成一系列对单变量的最优化决策问题，从而使问题简化。§2.2生产库存——库存管理决策问题的解设某工厂生产某种产品，四个季度定货量为：一季一季二季四季600件700件500件1200件生产费用与产品平方成正比，即比例系数为0.005，C(x)=0.005u2(元)库存费每件每季为：1.0元。第i季度库存量为：x(i)件；第i季度生产量为：u(i)件；第i季度销售量为：s(i)=定货量一季一季二季四季600件700件500件1200件因此有：下季度库存是：x(i+1)=本季度库存量是x(i)+本季生产量u(i)—本季销售量S(i)且要求年初、年终都没有存货即销售已空。x(0)=x(5)=0最优管理问题：求每季度的最优生产量u(1),u(2),u(3),u(4)，使之能正好完成订货计划且使生产费与库存费总和最小。即：求｛u*(i)｝使Jlu*(i)Jlu*(i)]<J04i二11.005u2(i)+x(i)1)fx(i+1)=fx(i+1)=x(i)+u(i)-s(i)i=1,2,3,4s.t\x(0)=0|x(5)=0解：使用动态规划的办法：(2)(3)(4)先由最后一个季度考虑起：J=0.005u2(4)+x(4)1由(2)x(4+1)=x(4)+u(4)-s(4)及(4)x(5)=0得0=x(4)+u(4)—(4)—1200得u*(4)=1200-x(4)代入(1)J*[x(4)]=0.005(1200-x(4))2+x(4)=7200-11x(4)+0.005x2(4)4再考虑3－4两个季度，由基本递推方程知：其中即有J*(x(3))=min(3),u(3))其中即有J*(x(3))=min(3),u(3))+J*[x(4)卩21u(3)=min{.005u2(3)+x(3)+J*(x(4)Pu(3)1=min{.005u2(3)+x(3)+7200-11x(4)+0.005x2(4)^u(3)x(4)=x(3)+u(3)-s(3)=x(3)+u(3)-500代入上式J*(x(3))=2min0.005u2(3)+x(3)+7200u(3)-11(x(3)+u(3)-500)+0.005(x(3)+u(3)-500)2而u(3)应使上式取最小值，因此有:Q{・}/du(3)=0即：即：即有凡}=0.02u(3)-16+0.01x(3)=0du(3)u*(3)=80-00.5x(3)为使u*(3)>0，必须有x(3)<1600，把u*(3)代入J*(x(3))2J*x(3))=0.005u*(3)+x(3)+7200-11(x(3)+u*(3)-500)+0.005(x(3)+u*(3)-500)22=7550-7x(3)+0.0025x2(3)

(2),u(2))+J*(x(3)/(2),u(2))+J*(x(3)/J*(x(2))=3minu(2)—7x(3)+0.0025x2(3)min0.005u2—7x(3)+0.0025x2(3)u(2)其中x(3)=其中x(3)=x(2)+u(2)-700代入上式J*(x(2))3J*(x(2))=3min{.005u2(2)+x(2)+7550-7(x(2)-u(2)-700)+0.0025(x(2)J*(x(2))=3u(2)aj*(x(2))/au(2)=0得ajaj*(x(2))a{・}——3—au(2)=0.015u(2)-7+0.005(x(2)-700)=0au(2)u*(2)=701-x(2)3再代J*(x(2))得30.005J*(x(2))=10,000-6x(2)+334.再考虑1—2—3—4季度，由递推基本方程知：min((x(1),u(1