《广东工业大学运筹学第6章 动态规划》由会员分享，可在线阅读，更多相关《广东工业大学运筹学第6章 动态规划（35页珍藏版）》请在金锄头文库上搜索。
1、第六章 动态规划动态规划的基本概念 最优化原理 经济管理问题举例多阶段决策过程动态规划的分类：离散确定型 离散随机型 连续确定型 连续随机型决策1状态1 决策2状态2决策n状态3状态n应用：最优调度、资源分配、最优路径最优控制、设备更新、库存问题动态规划的基本概念k=2k=1k=3k=4AB1B3C1C2C3C4D1D2D3E557767 689888 88976 B281、阶段 阶段变量：k阶段数记作n 2、状态 每个阶段开始所处的自然状态或客观条件 状态变量：s k 状态集合：S k s k S k无后效性：如果某阶段的状态给定，这阶段以后 过程的发展不受这阶段以前各阶段状态的影响3、决策
2、、策略 （1）决策：某阶段状态确定后，为确定下一阶段的状 态，所作出的决定（选择）。决策变量：u k(s k) 表示第k阶段状态为s k时的决策允许决策集合：D k ( s k ) u k(s k) D k ( s k ) （2）策略：由决策组成的序列就称为策略。p1n(sk)= u 1(s 1) , u 2(s 2) , , u n(s n) 子策略：由过程的第k个阶段开始到第n个阶段为 止的决策序列 pkn(sk)= u k(s k) , u k+1(s k+1) , , u n(s n) 允许策略集合Pkn(sk)：pkn(s k)可选择的范围最优策略： p* 1 n 4、状态转移方程
3、状态转移方程：sk+1 = Tk( sk , uk ) 若k阶段处于sk状态，选择了决策uk(sk)第k+1阶段 处于sk+1状态。 5、效益函数、最优效益函数：衡量策略优劣的数量指标 （1）阶段效益函数：wk(sk,uk ) 表示第k阶段，从状态s k 出发，采取决策u k 时的 效益值（2）效益函数 V k n ( s k , p k n )：从第k阶段状态 s k 开始到终点，采用某个子策略p k n 时，所获得的效益值。 Vkn(sk) = V kn ( sk , p kn ) = wk(sk,uk) wk+1(sk+1,uk+1) wn(sn,un) 全过程的最优效益函数第k阶段到第
4、n阶段的最优效益函数动态规划求解的基本思路求解离散确定型动态规划，以最短路问题为例 逆序法：AB1B3C1C2C3C4D1D2D3E557767 689888 88976 B28(0)(7)(6)(8)(16)(14)(14)(17)(21)(20)(22)(26)解：该问题划分为4个阶段 k=1,2,3,4 sk 表示各阶 段的状态， f k ( sk)表示从第k阶段状态sk到终点E 的最短距离AB1B3C1C2C3C4D1D2D3E5577 67689888 8897 6 B28k = 4k = 3k=2k=1所以最优策略为： 最短路长为26 。 AB1B3C1C2C3C4D1D2D3E5
5、57767 689888 88976 B28动态规划的基本方程（逆序法）：f k ( sk)表示从第k阶段状态sk到终点E的最短距离动态规划的基本方程（顺序法）：最优化原理最优化原理：最优策略的子策略总是最优的动态规划求解问题的基本思路（1）划分阶段n （2）定义状态变量sk、写出各阶段的可选状态集合 Sk； （3）定义决策变量uk 、写出各阶段各状态下的可 选决策集合Dk(sk)； （4）写出状态转移方程sk+1=Tk(sk,uk)。 （5）定义阶段效益函数和效益函数，按照动态规 划基本方程寻求最优策略。（1）关键：将多阶段过程划分阶段，确定状态变 量、决策变量、指标函数（2）求解：从边界条
6、件开始，逐渐递推寻优，每 个子问题求解时都要用它前面已求出的子问题的 最优结果，最后一个子问题的最优解即整个问题 的最优解（3）每段最优决策的选取是从全局考虑的，与该 段的最优选择一般不同最优化原理：最优策略的子策略总是最优的动态规划问题特点例：用动态规划方法求解动态规划求解连续问题解：建模：用逆序法s1s2s3s4x1x2x3k=1k=2k=3 s1=12s2=12 - x1= s1 - x1s3=12 - x1 - x2= s2 - x2s4=12 - x1 - x2 - x3= s3 - x3 0x1s10x2s20x3s3f4(s4) = min (x42 ) f3(s3) = min
7、 x32 + f4(s4) f2(s2) = min x22 + f3(s3) f1(s1) = min x12 + f2(s2) s5x4k=4s5=12 - x1 - x2 - x3- x4= s4 x4x4= s4s1s2s3s4x1x2x3k=1k=2k=3 s1=12s2=12 - x1= s1 - x1s3=12 - x1 - x2= s2 - x2s4=12 - x1 - x2 - x3= s3 - x3s5x4k=4s5=12 - x1 - x2 - x3- x4= s4 x4按问题变量个数划分为4个阶段；状态变量为s1 , s2 , s3 , s4 并记s1=12； x1 ,
8、 x2 , x3 , x4为决策变量； 状态转移方程：s k+1 = s k x k 最优效率函数：fk ( sk )递推关系：当k=4时 f4(s4) = min x42 x4 = s4 x4* =s4 f4(s4) = s42 当k=3时 f3(s3) = min x32 + f4(s4) 0x3s3 f3(s3) = min x32 + s42 s4 = s3 x3= min x32 + ( s3 x3 ) 2 x3* =1/2s3 f3(s3) = 1/2s32 当k=2时 f2(s2) = min x22 + f3(s3) 0x2s2 f2(s2) = min x22 + 1/2s3
9、2 s3 = s2 x2= min x22 + (s2 x2)2 x2* =1/3s2 f2(s2) = 1/3(s2)2当k=1时 f1(s1) = min x12 + f2(s2) 0x1s1=12 f1(s1) = min x12 + 1/3s22 s2 = s1 x1= min x12 + 1/3( s1 x1 ) 2 x1* =3 f1(s1) =36 x1* =3 f1(s1) =36 s1=12 s2 = s1 x1=9 x2* =1/3s2=3 f2(s2) = 1/3(s2)2=27 s3 = s2 x2=6 x3* =1/2s3=3 f3(s3) = 1/2s32=18 s
10、4 = s3 x3=3 x4* =s4 =3 f4(s4) = s42=9z*= f1(s1) = 36动态规划的应用举例不确定价格采购问题 例：某厂必须在5周内采购一批原料，其浮动价格和概 率已测得，试求在哪一周以什么价格购入，使采购 价格的数学期望值最小，并求出期望值。周浮动价 格及概率如下表：周浮动价格500600700 概率0.30.30.4解：阶段数n=5，每个星期为一个阶段决策变量：状态变量sk:第k周的价格 可选状态集合为Sk=500，600，700状态转移方程：无。每周的价格与上周的价格、决策 无关 ykE=Efk+1(yk+1) ：当第k阶段选择不采购时以后阶段 均选用最优子
11、策略购入价格的期望值。 指标函数fk(yk)：第k周实际价格为yk 时，则第k周至 第5周末采用最优子策略购入价格的期望值。 递推方程： fk(yk) = min yk ,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，700 f5(500)=500，x5(500)=1 f5(600)=600，x5(600)=1 f5(700)=600，x5(700)=1当k=4时，S4=500
12、，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。甲 乙 丙0000 1132 2 444 3865 4776 5785 6694专家数盈利商店资源分配问题 某公司拟聘请4-6名商业专家，分配给其甲、乙、丙 三个商店任用。各商店分的不同数量的专家后， 预测可创造的利润如
13、表所示，问该公司聘请几名 专家并如何分配，可使得所创造的总利润最大？解：阶段数n=3，3个阶段分别决定甲、乙、丙三个商 店的专家数； 状态变量sk：第k阶段初还剩余的专家数；k=1,2,3 决策变量xk：分配给第k个商店的专家数； 允许决策集合：Xk=xk|0 xk sk 状态转移方程：sk+1=sk-xk 阶段效益函数vk(sk,xk)：给第k个商店xk个专家能够 获得的盈利； 最优过程效益函数fk(sk):第k阶段初还剩余sk个专家 能够获得的总利润。 递推方程：当k=3时当k=2时7+3=107+0=7 7+5=12当k=1时当k=2时所以最优策略为甲、乙、丙三家商店分别聘用3、1、2位
14、 专家，总利润为15。当k=3时复合系统的可靠性问题 为保证某设备正常运转，需对串联工作的三种零部件 A1、A2、A3分别确定备件数量。若增加备用零件的 数量，可提高设备正常运转的可靠性，但费用增加 ，而总投资额为8万。已知备用零件数与他的可靠 性和费用关系如表所示，求A1、A2、A3的备用零件 数各为多少时，设备运转的可靠性最高。备件数可 靠 性备用零件费用 A1A2A3A1A2A3000000010.30.20.113220.40.50.225330.50.90.7364解：阶段数n=3状态变量sk:第k阶段初的剩余资金额决策变量xk:购买第k中备件的数量效益函数：系统可靠性87654320备件 数可 靠 性备用零件费用A1A2A3A1A2A3000000010.30.20.113220.40.50.225330.50.90.73640.30.40.50.20.50.20.20.70.20.110.70.20.10.140.040.020.042
