动态规划与最优控制模

1、精品文档你我共享 AAAAAA 第四章最优控制模型 (管理、决策方面应用，因此可说管理决策模型) 1最优控制的问题提法: 1.1最优控制问题举例 、例，详见最优控制课听课笔记第一节; 1.2最优控制数学模型 最优控制模型问题的数学描述一一最优控制模型。 寻找u*(t)壬U (开，闭)to，tf J tf可以固定或自由，使得: J u* (t) = min J u( t) 甩 d x (t)- S.t = f ( x(t), u (t), t ) dt gi(x(tf), tf )=0 gUx(tf), tf o x (t0 x0 x(tf) = * M =x(tf) x(tf)壬 R, 其中:

2、 x(t严Rn，且x(t)亡c1 (一阶连续可微)，U(t)亡URm fx(t), u, t ：向量值函数，且f ()对x(t), u(t), t连续，对x(t), t连续可微。 tf J u (t) =Q(x (tf), tf )+ JL (x(t), u(t), t )dt, t0 W(x(tf), tf , LX (t), u (t), t 对 x (t), t 都可微。 上述最优控制的离散模型： 求络*(i),x*(i) 使得 N -4 目标泛函：J=2 L(x(i), u(i), i )达到最小。 izO 而且满足: ：x(k +1) = f (x(k), u(k),k) 状态方程：

3、x(0) =x0 I x (kf)-M 最优控制问题的 求解方法： 1. 古典变分法：U开集； 2. 极大值原理：U闭集；现代变分法，把古典变分法看作特例 3. 动态规划：便于数值计算，并有通用算法； 发展了变分法，结果是充分条件。 2最优控制模型的动态规划解法 2.1动态规划方法概述 2.2生产一一库存一一销售管理系统的动态规划解法 2.1动态规划方法概述 某一类管理问题的数学模型(状态方程)是一个差分方程: x(k+1) = f (x(k), u(k),k) 状态方程：x(0) =x0 I x (kf)刖 N 目标泛函：J=5； L(x(i), u(i), i )达到最小。 i=0 即：

4、此为一个N阶决策问题： 动态规划法是求这一决策问题的有效办法，具有明显优点： (i) 将一个 N阶决策问题转化为多次一步决策问题，即数学上的嵌入原理一一将求 一条极值曲线问题，嵌入到求一族极值曲线的更广泛的类似问题中； (ii) 大大简化了计算量； (iii) 具有局部优，就是整体优的最优性原理： 可广泛应用于运输系统、生产库存管理系统、生产计划制定及最优投资分配问题、最优 价格制定问题。 下面以最短路问题举例说明这种方法 、最短路问题(最小时间问题) 1问题：若有一辆汽车以S城出发经过若干城市到达 F城，如图：Pi, Qi, 1, 2, 3 , F 是 图中两点间的数字： 可以表示两城镇之间

5、的距离 (单位10公里)，也可以表示行驶两城 镇所用时间(应综合考虑：距离远近，路面好坏，是否拥挤等情况) 于是：汽车从S到F可经多种途径选择到达 FO 问题是：从多种途径选择方案中，决定一种使S到F所走路线最短。或者若图中数字表 示时间，则决定一种路径使从 S到F所用时间最短。 2.方法： I .决策树法（穷举法）： 决策树法是最容易想到的一种方法，但运算量很大一一即把所有可能选择的路途所用的 然后取最小值，即有最优策略（最优决策） 时间都求出来， 即: sp * Qi * F =min SRQjF i =1, 2, 3) 因此有: Pi 6 P Q3 P3 4F 15 14 Q S 因此，

6、最终得出： SQ1P2P3min .P3 4 F 16 Q 3 F 15 P3 4- F 14 Q3 - 3- F 13 P3 4 F 18 Q3 3 F 17 spQjF i=1, 2, 3 2 困难：这样共有8条线路可选择，每条线路要作 3次运算。 第 1 次：St p/Qj T P2/Q2T Q2 ;第 2 次：P2/Q2TP3/Q3 ; 第3次：P3或QsT F 因此，共需24次运算：8X3= 24次，若阶段更多，则计算量更大。 II “走一步瞧一步”（瞎子爬山？近视眼？）法: 第一步：从 S到Pi或Qi :显然 SR =4SQi =5，因此取决策SPi ; 第二步：从 Pi到P2或Q

7、2 :显然PiP2 =6=PiQ2，因此取PP2, QiQ2均可，但从P2到 P3或Q3距离为 i，而Q2到P2P3距离为2,因此，第2步决策为P2，因此取PiP2 ； 第三步：P2到P3或P2到Q3 ,均有P2P3 =P2Q3 =1，但Q3到F的距离为3，因此第3 步取路线p2q3 O 因此使用这种方法得到的决策为: SpP2Q3F=4+6+1 +3=14 显然不是“最优决策”，同时还有: SQ1F2P3F =14 问题出现在“局部优不能代替整体优” 的问题。 III .动态规划： 即可把每一步决策都看成一个状态的转移，而每一种状态的转移又影响到下一阶段的 状态，因此又是动态的，故称为动态规

8、划法。 故可将问题分为四阶段问题来考虑: 将上述问题分为四个阶段的多阶决策问题， 第一阶段问题：StPi/Qi ； 第二阶段问题: Pi / Qi T P2 / Q2 ； 解题方法从最后一个阶段开始: 1分别计算P3, Q3到F的最小代价，此处花费代价为时间, 记为J，用J 3 I J匕3 分别 表示P3或Q3到F的代价，则显然有: J* PJ=4 J* QJ=3 2由后往前，考虑倒数第二阶段（即第三阶段），再把第三阶段和第四阶段联合作为一个 子问题来考虑，若从 P2出发到F，则有两种可能: P2P3F P2Q3F J=1 +J* 卜3 =1 +4=5 J=2 +J* Q3 = 1+3=4 线

9、路P2Q3F最短，且J*目=4，故将线路P2Q3F记成P2Q3. 类似以Q2出发到F，则有两种可能: 精品文档你我共享 Q2P3F Q 2 Q 3F J =2+J 3 1=2+4=6 J=2+J bs =2+3=5 二 线路b2b3F最短，则J=J* bj=5，故将线路b2b3F记成b2b3. 再由2、3、4这三个阶段构成的子问题: 若从Pi出发到F有两种可能: P1P2F P1Q2F J = 6+J* P2 =6 +4=610 J=6 +J* b2 】 = 6+5 = 11 /.有线路P1P2F最短，且J* 匕=10，故将P1P2F记成：P1P2 若从Qi出发到F有两种可能: 孑 Q1P2F

10、 Jqqf J=4+J* PJ= 4+ 4=8 J =7 +J* bj = 7 +5=12 二有线路Q1P2F最短，则J* QJ=8，故将Q1P2F记成：Q1P2 III AAAAAA 把由1、2、3、4阶段作为子问题来考虑: 从S出发到F有两种可能: 且J=4+J* P =4 +10=14 且 J=5+J* br = 5+8=13 故: SQ1F最短，且 J* S=13 因此有最优策略：SQ1F 即: SQ1SQ1P2Q3F，J* S=13 7 F 2 4 Q3F Q1 P2 I F3 P P26 B iC Q3 7 Q2 Q32 第1阶段！第2阶段：第3阶段 精品文档你我共享 AAAAAA

11、 除“二决一”比较之外，且运算只用了 10次，而穷举法则算了 24次，上次这种动态规 划的办法：是将把一个四阶段决策问题化为四个互相嵌入子问题，逐一进行简化的计算方法， 即数学上嵌入定理。 IV.最优性原理 “最优策略的一部分也是最优策略” 例如：上例中知: SQ1F2Q3F是最优决策，则 Q1P2Q3F也一定是从Q1出发到F的最优 决策： 证明反证法: 个最优决策，不妨设为 设SQ1P2Q3F是最优决策，则 Q1P2Q3F不是最优决策，则必存在另一 Q1Q2Q3F为最优决策。因而， SQ1Q2Q3F是整体最优决策，因而与 SQ1P2Q3F是最优决策相矛盾，因而原结论正确。 般有最优性原理：

12、如果u*(0), u* (1),，u*(N -1)是N阶决策问题的最优策略序列，那么： u*(1),，u*(N -1)也是一个最优策略序列，其初始状态为: x(1)=f(x(0),u*(0) 证明：同最短路. 4.多阶段决策问题的一般想法: 设某系统的状态方程为：FwzwiME 1x(0) = X0 N -1 目标函数为：JZ L(x(i),u(i),i ), Jn表示控制N步时的目标函数值。 i =0 最优控制问题，即：求最优决策序列t* (i)=tu* (0),，u(N-1)，使Jn取最小(大) 值。 为简化假定为定常状态，即L不明显还有时间变量i 因而有：NiTfxQ),，) 1X(0)

13、 =X0 (1) N Jn =5： L(x(i), u(i) i=0 (3) 对目标函数逐次应用(1)式有: Jn =L(x(0), u(0)+L(x(1), u(1) )+ + L(x(N-1), u(N1) = L(x(0), u(0)+L(f(x(0), u(0) u(1)+- + L(f (f L (f (x(0), u(0) ) u(1)厂,u(N -2), u(N -1) 因此，可以由上式看出：Jn只依赖于：x(0), u(1),u(N -1) 因而可写成： Jn = Jn(x(0), u(1),u(N -1) 又若用某种方法求出了最优决策:u* (0),，u* (N -1)，则J

14、n的最小值只依赖于初 始值x(0)，记为JN *(X (0),它可用下式来定义: JN*(x(0)九0)需曲(0)，u(1)，小-1) 初始值是可变化的，因此: JN *(X (0)表示初始状态为x(0)时，控制N步的目标函数最小值。 5.动态规划的基本方程： 动态规划的基本方程，给出N阶决策问题的目标函数最优值与它的子问题 (N -1阶决策问题目标函数最优值之间的递推关系式，它是用动态规划解一切多阶决策问 题的基础。 设u*(0)已求出，则求序列u *(1), U * (2),，U * (N-1)的问题，构成一个以 x(1) =f (x(0), u(0)为初始条件的N -1阶决策问题，若记这

15、一子问题的目标函数最小值 为：Jn J(x (1)；又若记JN *(x(0)內N阶决策问题最小值，则我们可以导出JN *(x(0) 与 JNA* (x(1) 之间的关系: N-1 由于 JN*(X(0) ) = u(0),u(minu(N2L(X(k), u(k) N -1 =卿-1)L(x(0), u(0)+S L( x (k), u (k) I心 则第一项: minL(x(0), u(0) )=min L(x(0), u(0) u(0),u(N4)u(0)、 第二项: .机存(x(k),u(k3并不明显依赖u(0)， 但由状态方程: x(1)=f(x(0), u(0) x(N -1) =f

16、(x(N -2), u(N 2) 可知：实际上第二项仍依赖于 u(0), u(1),，u(N 1), 因此，第二项可写成： fN-1r min Jz L(X (k), u (k) u(0),:u(N 3) jk八 * rN-1r min s L ( x (k), u (k) u(1),:u(N)7 八 丿 I2 =mon = min jN(x(1) u(0)亠 * 因此有：动态规划基本方程: jl(x(o)Amin 5(x(0), u(o)+jl_i(x(i)】 此给出了 jN(x)与JN(x(0)之间的递推关系。它是动态规划的基本方程。 类似有动态规划更一般的基本方程: jN_L(x(i)

17、Amin 忙(x(i), u(i)+jN_L_i(x(i +1)5) 伫) 因此依据基本递推方程的递推关系：可以把一个多阶决策问题化为若干个子问题，而 在决策的每一个阶段中只须对一个变量进行最优化决策即可。例如： j；(x(N -1)AjminAwN -1), u(N -1)9 是对一个单变量u(N 1)的优化问题，当J； (x(N _1)求出后，由基本递推方程(*)式可得: J；(x(N -2)=俪2)0，必须有 x(3) 1600 ,把 u * (3)代入 J；(x(3) j/xQ) )=0.005u* (3) +x(3) +720011(x(3) +u* (3) 500)+0.005(x

18、(3) +u* (3) 500 f = 75507x(3) +0.0025x2(3) 3.再考虑2-3-4，由递推基本方程知： J：/(2) )=niint(x(2),u(2) )+J；(x(3) j =mi 门匕005|?(2) +x(2) +7550-7x(3)+0.0025x2(3) u(2) 其中 x(3) =x(2) +u(2) -700代入上式J；(x(2) J； (x(2) )=mmb005u2 (2) +x(2) +7550 -7(x(2) -u(2) -700 户0.0025(x(2)-u(2) -700f j3(x(2)yu(2)=0 得 J；(x)= =0.015u(2)

19、 _7+0.005(x(2) 700)=0 cu(2)4(2) u*(2) =7 0-x(2)再代j3(x(2)得 3 4.再考虑 *0 005 2 J3(x(2) )=10,0006x(2)+ x (2) 3 1-2 3 4季度，由递推基本方程知： j4(x(1) AminL(x(1),u(1)+J；(x(2)y u(1) =min j0.005u2(1) +x(1) +10,000-6x(2) +0005x2(2) 又由于 x(2) =x(1) +u(1) -s(1) =0 +u(1) -600 =u(1) -600 并代入上式 J4(x(1) 得 j4(x(1) )=min j0.005u2(1) + x(1) +10,000 -6(u(1) -600 )+(u(1)-600 I3 0.01u(1)-6 +001(u(1)-600)=0 3