ch5动态规划.

Page1第五章动态规划第一节多阶段决策过程及实例Page2动态规划是运筹学的重要分支之一，它是解决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼（R.Bellman）等人在本世纪50年代首先提出的。R.Bellman于1957年发表的“动态规划”一书是动态规划方面的第一本著作。目前，动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。Page3动态规划引例1：某旅客需从A号站到达E号站，试指出一条最短路径。交通状况如图所示。箭头表示旅行路线，箭头旁边数字表示距离。[解]一种习惯求解法是首先计算所有可能路线的距离，然后经比较选出一条最短路线，这称为显枚举或穷举法，当维数增大时，该法计算量将急剧增大，从而变得不可行。动态规划是采用递推方式计算,分4个阶段。Page4动态规划最短路径为：A→B1→C3→D2→E24ED1D2C3C2C1B2B1A533766452123第4阶段第3阶段第2阶段第1阶段18Page5动态规划引例2：机器负荷分配问题（P155例2）制订五年计划，可以看做一个五阶段动态规划问题。Page6第二节动态规划的基本概念Page71.阶段（stage）原问题可分为若干个子问题，每一子问题称为一个阶段，用k表示。k=1,2，….，n称为阶段变量。2.状态(state)每一阶段开始时所处的状态（位置），称为状态，用表示。如引例1中，状态集第二节动态规划的基本概念Sk3123{,,}SCCCPage8动态规划的基本概念3.决策(decision)从某一阶段某一状态出发，向下一阶段某一状态演变的选择。表示第k个阶段从出发的决策变量。表示第k个阶段从出发的允许决策集合。如：():kkUSD():kkSkSkS21123D()={C,,}BCC211U()=CBPage94.策略(policy)一个按顺序排列的决策组成的集合。从第一阶段开始至终止：从第k阶段开始至终止：111122nn()={U(S),U(S),......,U(S)}nPSkkk+1k+1nn()={U(S),U(S),......,U(S)}knkPS（后部子策略）动态规划的基本概念Page105.状态转移由一个状态转移到下一个状态的演变过程，用方程1kkk=T(S,U)kS（状态转移方程）若状态给定，决策变量确定，则第k+1阶段的状态就确定了。T称为状态转移函数。kSkU1kS动态规划的基本概念Page116.指标函数阶段指标：k阶段中，评价从状态出发作出决策所产生效果的数量指标。记为：动态规划的基本概念kSkU(,)kkkVSU如：211211()(,)3UBCVBC指B1到C1的路长指标函数：评价由k阶段状态出发到终点的后部子策略产生效果的数量指标。记为：kS()knkPSkkk+1k+1nn+1={S,U,S,U,......,U,S}knknVVPage12动态规划的基本概念最优指标函数：从k阶段状态出发到终点的所有后部子策略中指标函数值的最优者。kSknkkkkk+1k+1nn+1(U,...,U)f(S)={S,U,S,U,......,U,S}optknVkkf(S)称为的最优指标函数kS11f(S)表示全过程的最优指标函数，相应的策略即为最优策略。Page13如：动态规划的基本概念31f(C)表示从第三阶段状态C1出发至终点的最优指标函数。312412f(C)=4=V(,,)CDE21f(B)1f(A)表示从第二阶段状态B1出发至终点的最优指标函数。表示从第一阶段状态A出发至终点的最优指标函数。21f(B)=61f(A)=11Page14第三节最优性原理与递推方程Page15最优性原理与递推方程Bellman的最优性原理一个过程的最优策略是这样的。即无论过去状态和决策如何，对前面决策形成的状态而言，余下的策略必构成最优策略。（最优策略的子策略必最优）下面求引例1的递推解法：Page16动态规划最短路径为：A→B1→C3→D2→E24ED1D2C3C2C1B2B1A533766452123第4阶段第3阶段第2阶段第1阶段18引例1Page17最优性原理与递推方程动态规划是通过求解下面递推过程1nkkkkk+1k+1(U,...,U)n+1n+1f(S)=(S,U)+f(S)](),1,2,...,(S)=0opt[kkkkVUDSknf求得最优策略及最优指标函数的。上式称为动态规划的递推方程或基本方程。（逆序解法）Page18最优性原理与递推方程用递推法求解动态规划的方法：1.规定过程的分段，构造出状态，定义状态变量；2.定义决策变量，确定允许决策集合；3.确定状态转移规律，写出转移方程；4.定出指标函数，写出递推方程，求解。Page19第四节动态规划应用举例Page20一、资源分配问题：所谓分配问题，就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等)，恰当地分配给若干个使用者，而使目标函数为最优。动态规划应用举例Page21动态规划应用举例例1.资源连续分配问题某工厂有100台机器，拟分四期使用，在每一期有两种生产任务。根据经验，要把台机器投入第一种任务，则在一个生产周期中将有台机器报废；余下的机器全部投入第二种任务，则在一个生产周期中将有台机器报废。如果在一个周期中用于第一种任务，每台机器可收益10；用于第二种任务，每台机器可收益7。问怎样分配机器使总收益最大？x13x110xPage22解：构造动态规划模型如下：阶段变量k：运行周期（k=1,2,3,4），其中k=1表示第一期初，…，依次类推；k=4表示第四期初。状态变量Sk：第k期初完好的机器数（k=1,2,3,4），决策变量xk：第k期初投入第一种任务的机器数；则第k期初投入第二种任务的机器数：Sk-xk状态转移方程：（0xkSk）阶段指标：Vk(xk,Sk)=10xk+7(Sk-xk)边界条件：f5(S5)=0动态规划应用举例921310()kkkkSxSxPage23则递推方程为：动态规划应用举例kkkkkk+1k+10x55f(S)=10+7(S-x)+f(S)]1,2,...,4(S)=0max[kkSxkf注：允许决策集是整数集，但不可能一一列举，计算量太大。此时可认为状态变量和决策变量都是连续的，得到最优解后再做取整处理。Page24动态规划应用举例k=4时：f4(S4)=max{10x4+7(S4-x4)+f5(S5)}0x4S4=max{3x4+7S4}(取x4*=S4)=10S4,k=3时：f3(S3)=max{10x3+7(S3-x3)+f4(S4)}0x3S3=max{10x3+7(S3-x3)+10[2/3x3+9/10(S3-x3)]}=max{2/3x3+16S3}=50/3S3(取x3*=S3)Page25动态规划应用举例k=2时：f2(S2)=max{10x2+7(S2-x2)+f3(S3)}0x2S2=max{10x2+7(S2-x2)+50/3[2/3x2+9/10(S2-x2)]}=max{-8/9x2+22S2}=22S2(取x2*=0)Page26动态规划应用举例k=1时：f1(S1)=max{10x1+7(S1-x1)+f2(S2)}0x1S1=max{10x1+7(S1-x1)+22[2/3x1+9/10(S1-x1)]}=max{-2.13x1+26.8S1}=26.8S1(取x1*=0)Page27最优策略为：动态规划应用举例*11100,0Sx*2290,0Sx*3381,81Sx*4454,54Sx最大收益为：1(100)2680fPage28动态规划应用举例练习.资源分配问题某施工单位有500台挖掘设备，在超负荷施工情况下，年产值为20万元/台，但其完好率为0.4；正常负荷施工情况下，年产值为15万元/台，完好率为0.8。在四年内合理安排两种不同负荷下施工的挖掘机设备数量，使四年年末仍有160台设备保持完好，并使产值最大。Page29解：构造动态规划模型如下：阶段变量k：运行周期（k=1,2,3,4）；状态变量Sk：第k期初完好的挖掘机台数（k=1,2,3,4），决策变量xk：第k期初用于超负荷施工的机器数；则第k期初用于正常负荷施工的机器数：Sk-xk状态转移方程：（0xkSk）阶段指标：Vk(xk,Sk)=20xk+15(Sk-xk)=5xk+15Sk边界条件：f5(S5)=0动态规划应用举例10.40.8()kkkkSxSxPage30则递推方程为：动态规划应用举例kkkkk+1k+10x4455f(S)=5+15S+f(S)]1,2,...,402400(S)=0max[kkSxkxSf5440.40.8160SxS注：要考虑160台Page31动态规划应用举例k=4时：f4(S4)=max{5x4+15S4+f5(S5)}0x42S4-400=max{5x4+15S4}=25S4-2000(取x4*=2S4-400)k=3时：f3(S3)=max{5x3+15S3+f4(S4)}0x3S3=max{5x3+15S3+25[-0.4x3+0.8S3]-2000}=max{-5x3+35S3-2000}=35S3-2000(取x3*=0)Page32动态规划应用举例k=2时：f2(S2)=max{5x2+15S2+f3(S3)}0x2S2=max{5x2+15S2+35[-0.4x2+0.8S2]-2000}=max{-9x2+43S2-2000}=43S2-2000(取x2*=0)Page33动态规划应用举例k=1时：f1(S1)=max{5x1+15S1+f2(S2)}0x1S1=max{5x1+15S1+43[-0.4x1+0.8S1]-2000}=max{-12.2x1+49.4S1-2000}=49.4S1-2000(取x1*=0)Page34最优策略为：动态规划应用举例*11500,0Sx*22400,0Sx*33320,0Sx*44256,112Sx11()22700fS最大收益为：Page35动态规划应用举例例2.资源平行分配问题(投资分配)某工业部门根据国家计划安排，拟将某种高效率的设备5台分配给甲乙丙三个工厂，各厂获得这台设备后，可以盈利如下表。问如何分配可使盈利最大？甲乙丙000013542710639111141211125131112工厂设备数Page36动态规划应用举例1kkkssx()kkVx解:将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1、2、3阶段变量：k=1,2,3状态变量：Sk表示为分配给第k个工厂至第n个工厂的设备台数。决策变量：xk表示为分配给第k个工厂的设备台数。表示为xk台设备分配到第k个工厂所得的盈利值。状态转移方程：(0)kkxS阶段指标：Page37动态规划应用举例11044()max()(),3,2,1()0kkkkkkkkxsfsVxfSkfs逆推方程为：Page383333334433()max()()max[()]xxfsVxfxVx下面从最后一个阶段开始向前逆推计算。k=3时：因为此时只有一个工厂，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表。动态规划应用举例Page39动态规划应用举例（填表）s3x3V3(x3)s4f4(s4)V3(x3)+f4(s4)f3(s3)x3*表中x3*表示使f3(s3)为最大值时的最优决策。Page40动态规划应用举例s3x3V3(x3)s4f4(s4)V3(x3)+f4(s4)f3(s3)x3*000000001140044122600662331100111134412001212455120012125表中x3*表示使f3(s3)为最大值时的最优决策。Page