《数学模型10：动态规划模型.doc》由会员分享，可在线阅读，更多相关《数学模型10：动态规划模型.doc（52页珍藏版）》请在三一文库上搜索。
1、救学建模写数学实验动冬规妇Email: sunyl 决策决策状态动态规划:运筹学的一个分支:求解多阶段决策过程的最优化数学方法:研究对象：一项任务需要分几个阶段完成，每个阶段都有多种 选择，即多阶段决策.:动态：时间空间:创始人:R.E.Bellman20世纪50年代富淖迢J舜许沦沛人:4 ii-X例最短路问题A D:问应选择什么样的路线，可使总路线最短？例2誓输西题:运输公司：500辆卡车:计划时间：5年年利润损坏率超负荷25 （万元/辆）0.3%低负荷16 （万元/辆）0.1 %每年年初分配卡车二问：怎样分配（超，低）负荷使总利润最大分析：例1最短路问题:四个阶段初始状态最佳线路分析：例1
2、最短路问题最佳线路分析：例1最短路问题CjDk-EA Bit1第一阶段最佳线路分析：例1最短路问题最佳线路分析：例1最短路问题3个B中选择:决策：:1 : 单阶段决策:局部1I:多阶段决策:整体:I线路：3X2 X3 Xl=18条:I II最佳线路BlDICl3B2ED235C2B3D32A-Bi - Cj - DkE则:Bi Cj Dk - E为Bi至E最佳水 甲孚阶策逻序法四个阶段：fk (xk)最优值函数(xkE最短路长)Cl-DI-E:d3 (Cl,Dl)+f4 (DI) =5ClD2E: d3 (Cl, D2) +f4 (D2) =6ClD2E: d3 (Cl, D3) +f4 (D
3、3) =8 k=4 5 D15D25D3D1-E:f4(D1)=3D2-E:f4(D2)=1D3-E:f4(D3)=5 k二3, C1,C2ClE: f3(Cl) =DICl3ED25C2D32不考虑一E 怎样实现 k=3, C1,C2C1-E: f3(C1)= 5C2-E: f3(C2)=min(d3(C2,Di)+f4(Di)=min(4,5,7)=4 k=2, Bl, B2, B3B1-E: f2(Bl)= 7B2-E: f2(B2)= 6B3E: f2 (B3)= 8 k=15 Af1 (A)=min(d(A,Bi)+f2(Bi)=min(10,8,9)=8AE:最短路径:A -B2
4、-C1 D1 -Ef2(Bl)二 7f 2 (B2) = 6f 2(B3)= 8特点:无后效性局部最优决策过程与全过程:每阶段最优决策：直接效果:阶段内间接效果:后阶段递推基本理论(一)基本概念 :阶段、阶段变量k 2.状态、状态变量xk) = E1,E2,w(D2) = E,E2,m(D3) = ,2 W(E1) = F,W(E2) = F:动态规划求解：按照动态规划递推公式倒推，逐个阶 段求解。:解 f(E1)=mind(E1,F)+f(F)=min3+0=3, u*(E1)=Ff(E2)=mind(E2,F)+f(F)=min6+0=6, u*(E2)=F3 + 32 + 6kH 6=
5、(DI) H E-6nin 忘(D;(D-)+)-H minLd(DL)+r(a) d(D=0)+r(0)n minr(D2TminsD2MD2) + r(AD2 三2nel)+r-rr4+3 一 一d(D2b)+r(0)j 一 3+2D3TminsD3MD3)+AD3)二M(D3b)+r(E2)、d(pD一 )+D一) 一 -8H minrp匸2) + 7(D2 )Hmin一 3 + 7H1 on (c一td-d(pD3) + r(D3)J -6 + 7r(c2Tmin 忘(c2MC2) + r(Ac2)_2七(c2) + r(“-rm 匚 4 + 6 M(cl3) + r(D3)j 一 7
6、 + 7r(c3Tminsc3M(c3) + r(Ac3)-m 昱(cm-rm 皂+ 7 M(cl3) + r(D3)J 一 8 + 7H las(C3) H/(BJ = min d(Bu力(d，cj+/(cj、:G3+10min =min7 + 15V丿=13, w (Bj) = C62)3/(B2) = mintZ(B2,w(B2) + /(w(B2) r (B2,C2) + /(C2) 6/(B2,C3) + /(C3)/： /(A) = min (A, w(A) + /(w(A)= mm1(4,坊)+ /(坊):最短路长V(A)=19 o=min=mm=min= min =12山(B2
7、) = C2i6 + 13 = 9”(A)=7 + 12最优路径 A B1C1D2E1F A B2C2D1E1F:最短路长V(A)=19不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必构成最优子策略。“Bellman 1957fk(X Fax Vk(Xk, Uk) +fk+1(Xk+1)f6 仗6）二徨欵淖迢J舜神三小兀& m2：&仝应用 例2:5年-年利润损坏率500辆超负荷25 （万元/辆）0.3%:解：卡车低负荷16 （万元/辆）0.1 %阶段k=状态变量xk:1,2, 3, 4,5（年初一年末）车完好f数量决策变量山：超负荷f数量 低负荷：Xk 一 uk状态转移
8、方程为：Xk+1 =(l-o. 3)uk+(l-0. 1) (xk-uk) =0. 9 xk- 0. 2 uk阶段效益：Vk (xk, uk) =25 uk+16 (xk-uk)=16 xk+ 9 uk第k年度至5年末 采用最优策略时产 生的最大利润：求解金当k=5fk(x =max Vk (Xk，uk) +fk+1(Xk+1) f6 仅6)=0: xk+1 =0. 9 xk- 0. 2 uk -II Vk_(Xk，iik)二16 Xr+ 9 ilkf5(x5)=maxv5(x5, u5)+f6(x6) (0 u5 x5)=max16 x5+9 u5+ 0有：最优决策u5=? x5最优值函数f
9、5(x5)=?25 x5=max38. 5 x4+4 u4有:u4*= x4 f4 (x4)=42. 5 x4(0 u3 x3)(0 u2 x2)(0u1 x1)继续当 k=3f3(x3)=maxv3(x3, u3)+f4(x4) =max54.5 x3+0.5 u3 u3 = x3 f3(x3)=54.75 x3 当 k=2f2(x2)=maxv2(x2, u2)+f3(x3) =max65.275 x2- 1.95 u2 u2 = 0 f2(x2)= 65.275 x2 当 k=1f1(x1)=maxv1(x1, u1)+f2(x2) =max74.7475x1-4.055 u1 u1=0
10、 f1(x1)= 65.275 x1丄而:xl=5005年末尚余好车:优点：奇计算量:多阶段过程转化为一系列单阶段问题能够得到全局最优解可以得到一族最优解 a 静态原理简单，适用性广:缺点：无统一的标准模型用数值方法求解时存在维数灾应用举:离散系统最优控制:连续系统最优控制min J=JL( X ,u ,t)dtX=fX(t),u(t),t随机最优控制处淖迢淞舜伸H几:4 *上例31生产与库存辻划问题:某厂生产计划：四季度订单：一二三四（季度）2324（千件）生产费用:开工费3千元（不开工0千元）成本2千元/千件库存费用：1千元/千件季度最大生产能力：6千件设:年初，年末无库存:问:如何合理安
11、排各季节的产量，使全年总费用最小？ 阶段？状态？决策？转移方程？阶段效益解:阶段 k= 1,2,3,4（季度）:状态 xq库存 x1=0 x5=0:决策山：生产量0 uk 00，uk=0fk（x =max Vk 傀，uk） +f如1 （Xk+J 5（X5）-0例4:资源分配问题:某市电讯局有四套设备，准备分给甲、乙、丙三支局， 在各支局的收益为（万元）：设备数01234甲3841486066乙4042506066丙4864687878问：应如何分配，使总收益最大?分析：分给甲、乙、丙：ill、u2、u3,则:+g3 (u3)+g3 (u3)收益：gl (ul) +g2 (u2) min Z=
12、gl (ul) +g2 (u2) s. t: ul+ u2 + u3= 4ul, u2, u3=0解:阶段k = 3,阶段初剩设备全分给丙 k = 2,阶段初剩设备分给乙丙 k= 1,阶段初剩设备分给甲乙丙:状态xq阶段初剩设备数x1=4 x4=0 :决策山：分给k阶段的设备数:转移方程阶段效益:基本方程Xk+1=Xk-Ukvk(xk5uk)=gk(uk)fk(x 二max vk (xk, uk) +fk+1 (xk+1) f4 (x4) =04?U r “:法fn+1-h, k- nJ i=lk=lfk(j) (xkl)=vk(xkl,uklJ)(Tk(XkpiiJ)*_ *xk _X1j=j+l+fk+l旦丄i 二 i+l?nkfk xki)=max 耳(xQYY输 fl(xl)k=lN 1k=k-lyk=nk=k+lxk+i*=Tk（x，u）输k, xk*, uk*