数学模型10动态规划模型.ppt

动态规划Email:数学实验与数学建模动态规划运筹学的一个分支:求解多阶段决策过程的最优化数学方法研究对象:一项任务需要分几个阶段完成,每个阶段都有多种选择,:时间空间创始人:→D问应选择什么样的路线,可使总路线最短?3533333**********B1B2B3AC1C2D1D2D3E例2运输问题运输公司:500辆卡车计划时间:5年每年年初分配卡车问:怎样分配(超,低)负荷使总利润最大年利润损坏率超负荷25(万元/辆)%低负荷16(万元/辆)%解分析:例1最短路问题四个阶段A→Bi→Cj→Dk→E初始状态第一阶段3个B中选择:决策单阶段决策:局部多阶段决策:整体线路:3×2×3×1=18条最佳线路性质:最佳:A→Bi→Cj→Dk→E则:Bi→Cj→Dk→E为Bi至E最佳ABiCjDkE3533333**********B1B2B3AC1C2D1D2D3E多阶段决策过程:逆序法k=4,{D1,D2,D3}D1→E:f4(D1)=3D2→E:f4(D2)=1D3→E:f4(D3)=5k=3,{C1,C2}C1→D1→E:d3(C1,D1)+f4(D1)=5C1→D2→E:d3(C1,D2)+f4(D2)=6C1→D2→E:d3(C1,D3)+f4(D3)=8C1→E:f3(C1)=min(d3(C1,Di)+f4(Di))=5四个阶段:fk(xk)最优值函数(xk→E最短路长)不考虑→E怎样实现315D1D2D3E331122455C1C2D1D2D3E继续k=3,{C1,C2}C1→E:f3(C1)=5C2→E:f3(C2)=min(d3(C2,Di)+f4(Di))=min(4,5,7)=4k=2,{B1,B2,B3}B1→E:f2(B1)=7B2→E:f2(B2)=6B3→E:f2(B3)=8333331112244555B1B2B3C1C2D1D2D3E331122455C1C2D1D2D3E继续k=1,{A}f1(A)=min(d(A,Bi)+f2(Bi))=min(10,8,9)=8A→E:最短路径:A→B2→C1→D1→E距离:8f2(B1)=7f2(B2)=6f2(B3)=83333331**********B1B2B3AC1C2D1D2D3E特点无后效性局部最优决策过程与全过程每阶段最优决策:直接效果:阶段内间接效果:后阶段递推基本理论(一)、、、决策变量uk(xk)、最优策略第k阶段始→终止状态(子过程)决策序列子策略pk,n(xk)={uk(xk),uk+1(xk+1),..,un(xn)}策略p1,n(x1)→最优p1,n*(x1)?33331112455B1B2B3AC1C2D