广东工业大学运筹学第6章 动态规划

第六章动态规划,动态规划的基本概念最优化原理经济管理问题举例,多阶段决策过程,动态规划的分类：离散确定型离散随机型连续确定型连续随机型,决策1,决策2,决策n,应用：最优调度、资源分配、最优路径最优控制、设备更新、库存问题,动态规划的基本概念,k=2,k=1,k=3,k=4,1、阶段阶段变量：k阶段数记作n2、状态每个阶段开始所处的自然状态或客观条件状态变量：sk状态集合：SkskSk,无后效性：如果某阶段的状态给定，这阶段以后过程的发展不受这阶段以前各阶段状态的影响,3、决策、策略（1）决策：某阶段状态确定后，为确定下一阶段的状态，所作出的决定（选择）。决策变量：uk(sk)表示第k阶段状态为sk时的决策,允许决策集合：Dk(sk)uk(sk)Dk(sk)（2）策略：由决策组成的序列就称为策略。p1n(sk)=u1(s1),u2(s2),un(sn)子策略：由过程的第k个阶段开始到第n个阶段为止的决策序列pkn(sk)=uk(sk),uk+1(sk+1),un(sn)允许策略集合Pkn(sk)：pkn(sk)可选择的范围最优策略：p*1n,4、状态转移方程状态转移方程：sk+1=Tk(sk,uk)若k阶段处于sk状态，选择了决策uk(sk)第k+1阶段处于sk+1状态。5、效益函数、最优效益函数：衡量策略优劣的数量指标（1）阶段效益函数：wk(sk,uk)表示第k阶段，从状态sk出发，采取决策uk时的效益值,（2）效益函数Vkn(sk,pkn)：从第k阶段状态sk开始到终点，采用某个子策略pkn时，所获得的效益值。Vkn(sk)=Vkn(sk,pkn)=wk(sk,uk)wk+1(sk+1,uk+1)wn(sn,un),全过程的最优效益函数,第k阶段到第n阶段的最优效益函数,动态规划求解的基本思路,求解离散确定型动态规划，以最短路问题为例,逆序法：,(0),(7),(6),(8),(16),(14),(14),(17),(21),(20),(22),(26),解：该问题划分为4个阶段k=1,2,3,4sk表示各阶段的状态，fk(sk)表示从第k阶段状态sk到终点E的最短距离,k=4,k=3,k=2,k=1,所以最优策略为：,最短路长为26。,动态规划的基本方程（逆序法）：,fk(sk)表示从第k阶段状态sk到终点E的最短距离,动态规划的基本方程（顺序法）：,最优化原理,最优化原理：最优策略的子策略总是最优的,动态规划求解问题的基本思路,（1）划分阶段n（2）定义状态变量sk、写出各阶段的可选状态集合Sk；（3）定义决策变量uk、写出各阶段各状态下的可选决策集合Dk(sk)；（4）写出状态转移方程sk+1=Tk(sk,uk)。（5）定义阶段效益函数和效益函数，按照动态规划基本方程寻求最优策略。,（1）关键：将多阶段过程划分阶段，确定状态变量、决策变量、指标函数（2）求解：从边界条件开始，逐渐递推寻优，每个子问题求解时都要用它前面已求出的子问题的最优结果，最后一个子问题的最优解即整个问题的最优解（3）每段最优决策的选取是从全局考虑的，与该段的最优选择一般不同,最优化原理：最优策略的子策略总是最优的,动态规划问题特点,例：用动态规划方法求解,动态规划求解连续问题,解：建模：用逆序法,s1,s2,s3,s4,x1,x2,x3,k=1,k=2,k=3,s1=12,s2=12-x1=s1-x1,s3=12-x1-x2=s2-x2,s4=12-x1-x2-x3=s3-x3,0x1s1,0x2s2,0x3s3,f4(s4)=min(x42)f3(s3)=minx32+f4(s4)f2(s2)=minx22+f3(s3)f1(s1)=minx12+f2(s2),s5,x4,k=4,s5=12-x1-x2-x3-x4=s4x4,x4=s4,按问题变量个数划分为4个阶段；状态变量为s1,s2,s3,s4并记s1=12；x1,x2,x3,x4为决策变量；状态转移方程：sk+1=skxk最优效率函数：fk(sk)递推关系：,当k=4时f4(s4)=minx42x4=s4x4*=s4f4(s4)=s42当k=3时f3(s3)=minx32+f4(s4)0x3s3f3(s3)=minx32+s42s4=s3x3=minx32+(s3x3)2x3*=1/2s3f3(s3)=1/2s32当k=2时f2(s2)=minx22+f3(s3)0x2s2f2(s2)=minx22+1/2s32s3=s2x2=minx22+(s2x2)2x2*=1/3s2f2(s2)=1/3(s2)2,当k=1时f1(s1)=minx12+f2(s2)0x1s1=12f1(s1)=minx12+1/3s22s2=s1x1=minx12+1/3(s1x1)2x1*=3f1(s1)=36x1*=3f1(s1)=36s1=12s2=s1x1=9x2*=1/3s2=3f2(s2)=1/3(s2)2=27s3=s2x2=6x3*=1/2s3=3f3(s3)=1/2s32=18s4=s3x3=3x4*=s4=3f4(s4)=s42=9z*=f1(s1)=36,动态规划的应用举例,不确定价格采购问题例：某厂必须在5周内采购一批原料，其浮动价格和概率已测得，试求在哪一周以什么价格购入，使采购价格的数学期望值最小，并求出期望值。周浮动价格及概率如下表：,解：阶段数n=5，每个星期为一个阶段决策变量：状态变量sk:第k周的价格可选状态集合为Sk=500，600，700状态转移方程：无。每周的价格与上周的价格、决策无关ykE=Efk+1(yk+1)：当第k阶段选择不采购时以后阶段均选用最优子策略购入价格的期望值。指标函数fk(yk)：第k周实际价格为yk时，则第k周至第5周末采用最优子策略购入价格的期望值。递推方程：fk(yk)=minyk,ykE,yksk,k=1,2,3,4,5f5(y5)=y5,y5s5,ykE=Efk+1(yk+1)=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)k=1、2、3、4逆序法求解当k=5时，S5=500，600，700f5(500)=500，x5(500)=1f5(600)=600，x5(600)=1f5(700)=600，x5(700)=1,当k=4时，S4=500，600，700,当k=3时，S3=500，600，700,当k=2时，S2=500，600，700,当k=1时，S1=500，600，700,最优采购策略为：第1，2，3周若价格为500就购入，否则等待；第4周若价格为500，600时应购入，否则等待；第5周无论什么价格均要购入。采用以上策略时，单位价格的数学期望值为0.3*500+0.7*536.26=525.382。,专家数,盈利,商店,资源分配问题某公司拟聘请4-6名商业专家，分配给其甲、乙、丙三个商店任用。各商店分的不同数量的专家后，预测可创造的利润如表所示，问该公司聘请几名专家并如何分配，可使得所创造的总利润最大？,解：阶段数n=3，3个阶段分别决定甲、乙、丙三个商店的专家数；状态变量sk：第k阶段初还剩余的专家数；k=1,2,3决策变量xk：分配给第k个商店的专家数；允许决策集合：Xk=xk|0xksk状态转移方程：sk+1=sk-xk阶段效益函数vk(sk,xk)：给第k个商店xk个专家能够获得的盈利；最优过程效益函数fk(sk):第k阶段初还剩余sk个专家能够获得的总利润。递推方程：,当k=3时,当k=2时,当k=1时,当k=2时,所以最优策略为甲、乙、丙三家商店分别聘用3、1、2位专家，总利润为15。,当k=3时,复合系统的可靠性问题为保证某设备正常运转，需对串联工作的三种零部件A1、A2、A3分别确定备件数量。若增加备用零件的数量，可提高设备正常运转的可靠性，但费用增加，而总投资额为8万。已知备用零件数与他的可靠性和费用关系如表所示，求A1、A