动态规划教学PPT.ppt

4 动态规划,4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题,例2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u),这时机器的年完好率为a（0a1)在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v),这时机器的年完好率为b（ab1）假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。,4.1 多阶段决策问题与动态规划,多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。,(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。,(2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。,(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。,4.2 动态规划的基本概念（一）,(4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n u1,u2,un 称为全过程策略，简称策略；而在k子过程上的决策序列pk,n uk,uk+1,un 称为k子过程策略，也简称子策略。,(5)状态转移方程 若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。,4.2 动态规划的基本概念（二）,(6)指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量，用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为 Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un)动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：各阶段指标函数的和 Vk,nvj(sj,uj)；各阶段指标函数的积 Vk,nvj(sj,uj)。把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数，记为fk(sk)。即 fk(sk)opt Vk,n(sk,uk,sn,un)uk,un式中的“opt”（optimization）可根据具体问题而取min或max。,fk(sk)-表示第k阶开始状态为sk的情况下到末状态为sn作最优策略对应的指标值,(7)基本方程 通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,nvj(sj,uj)，则有 fk(sk)opt vk(sk,uk)+fk+1(sk+1)ukDk(sk)(kn,n-1,1)递推方程 fn+1(sn+1)0 边界条件递推方程和边界条件一起称为动态规划的基本方程。可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解(称为逆序解法)。,此问题的基本方程为fk(sk)Mindk(uk)+fk+1(sk+1)ukDk(sk)k6,5,4,3,2,1f7(s7)0,4.3 动态规划的步骤（一）,当k=6时,按基本方程由后向前继续递推有:,当k=5时,当k=4时,当k=3时,当k=2时,当k=1时,由此可以看出，A到G的最短路长为18，路径为：AB1C2D1E2F2G,现在把动态规划法的步骤归纳如下：(1)将所研究问题的过程划分为n个恰当的阶段，k 1,2,n；(2)正确地选择状态变量Sk，并确定初始状态S1的值；(3)确定决策变量uk以及各阶段的允许决策集Dk(Sk)；(4)给出状态转移方程；(5)给出满足要求的过程指标函数Vk,n及相应的最优 值函数；(6)写出递推方程和边界条件，建立基本方程；(7)按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。,4.3 动态规划的步骤（二）,顺序解法-即解题顺序与决策顺序一致,4.3 动态规划的顺序解法（三）,即是在第k阶段末状态sk+1已知的情况下,确定前面的决策uk,使从初始状态s1到第k阶段末状态sk+1的策略最优,此时的状态转移方程应为,从sk+1出发通达uk解出sk,即从sk+1Tk(sk,uk)中反解出sk,skTrk(sk+1,uk),fk(sk+1)-表示第k阶末状态为sk的情况下到第1阶初始状态为s1作最优策略对应的指标值,顺序解法基本方程为,fk(sk+1)opt vk(sk+1,uk)+fk-1(sk)ukDrk(sk+1)(k1,n)递推方程 f0(s1)0 边界条件,4.3 动态规划的顺序解法（三）,fk(sk)-表示第k阶末状态为sk的情况下到第1阶初始状态为s1作最优策略对应的指标值,则顺序解法基本方程为,fk(sk)opt vk(sk,uk)+fk-1(sk-1)ukDrk(sk)(k1,n)递推方程 f0(s0)0 边界条件,如果sk表示第k阶段末状态,s0表示第1阶段初始状态,注,贝尔曼(Ballman)最优化原理 作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优的。,例：机器负荷问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 g8u,这时机器的年完好率为a=0.7在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为h5v,这时机器的年完好率为b=0.9假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。,(1)按年数划分为5个阶段，k=1,2,3,4,5,(2)取第k年初完好的机器数sk为状态变量,s1=1000,(3)取第k年投入高负荷的机器数xk为决策变量,0 xksk,(4)状态转移方程为 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk,(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj),(6)基本方程为 fk(sk)max 5sj+3xj+fk+1(sk+1)k=5,4,3,2,1 0 xksk f6(s6)0,解:,当k=5时,f5(s5)max5s5+3x5+f6(s6)=max5s5+3x5=8s5(x5*=s5)0 x5s5 0 x5s5,当k=4时,f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4)0 x4s4 0 x4s4=max12.2s4+1.4x4=13.6s4(x4*=s4)0 x4s4,当k=3时,f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3)0 x3s3 0 x3s3=max17.24s3+0.28x3=17.5s3(x3*=s3)0 x3s3,当k=2时,f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2)0 x2s2 0 x2s2=max20.77s2-0.504x2=20.7s4(x2*=0)0 x2s2,当k=1时,f1(s1)=23.7s1(x1*=0),f1(1000)=23700,s1=1000,x1*=0,s2=900,x2*=0,s3=810,x3*=810,s4=576,x4*=576,s5=397,x5*=397,某些静态规划问题可用动态规划法来求解。,例 用动态规划法求解 max z=x1.x22.x3 x1+x2+x3=c xi0 i=1,2,3,4.4 动态规划的应用(一),1 求解静态规划问题,4.5 动态规划模型举例,4.5.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。,例1 产品生产计划安排,设xk为第k阶段生产量，则有直接成本 dk(sk,xk)=ck xk+2sk状态转移公式为 sk+1=sk+xk-yk总成本递推公式,第四阶段：(即第4月份)由边界条件和状态转移方程 s5=s4+x4-y4=s4+x46=0 得 s4+x4=6 或 x4=6 s4估计第四阶段，即第4月份初库存的可能状态：s4 0,5,第四阶段最优决策表,第三阶段：最大可能库存量 7 件由状态转移方程：s4=s3+x3-120 及 x310，可知 s32,7，min x3=5由阶段效果递推公式有：f3(2)=d3(2,10)+f4*(0)=22+8010+456=1260得第三阶段最优决策表，如下,第三阶段最优决策表,第二阶段：最大可能库存量 4 件由状态转移方程：s3=s2+x2-72 及 x210，可知 s20,4，min x2=5由阶段效果递推公式有：f2(1)=d3(1,10)+f3*(4)=21+7210+1104=1826,得第二阶段最优决策表，如下,第三阶段最优决策表,第四阶段：初始库存量 s4=0由状态转移方程：s3=s4+x4-60 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下,回溯得此表,例2 生产库存管理问题(连续变量),设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。,解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设 sk 为第k季初的库存量，则边界条件为 s1=s5=0 设 xk 为第k季的生产量，设 yk 为第k季的订货量；sk，xk，yk 都取实数，状态转移方程为 sk+1=sk+xk-yk 仍采用反向递推，但注意阶段编号是正向的 目标函数为,例2 生产库存管理问题(连续变量),第一步：(第四季度)总效果 f4(s4,x4)=0.005 x42+s4 由边界条件有：s5=s4+x4 y4=0，解得：x4*=1200 s4 将x4*代入 f4(s4,x4)得：f4*(s4)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42第二步：(第三、四季度)总效果 f3(s3,x3)=0.005 x32+s3+f4*(s4)将 s4=s3+x3 500 代入 f3(s3,x3)得：,例2 生产库存管理问题(连续变量),第三步：(第二、三、四季度)总效果 f2(s2,x2)=0.005 x22+s2+f3*(s3)将 s3=s2+x2-700 代入 f2(s2,x2)得：,注意：最优阶段总效果仅是当前状态的函数，与其后的决策无关,例2 生产库存管理问题(连续变量),第四步：(第一、二、三、四季度)总效果 f1(s1,x1)=0.005 x12+s1+f2*(s2)将 s2=s1+x1 600=x1 600 代入 f1(s1,x1)得：,由此回溯：得最优生产库存方案 x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。,4.5.2 资源分配问题,例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。,解：设分配人员的顺序为市场1,2,3，采用顺向阶段编号。设 sk 为第k阶段尚未分配的人员数，边界条件为 s1=9 设 xk 为第k阶段分配的推销人员数；采用反向递推，状态转移方程为 sk+1=sk xk 靜态规划为,例3 第三阶段：给第三市场分配,s3 有09种可能，第三阶段最优决策表如下：,允许推销人员没用完时,允许推销人员没用完时,例3 第二阶段：给第二市场分配,s2 有09种可能，第二阶段最优决策表如下：,第一阶段：给第一市场分配,由边界条件 s1=9，第一阶段最优决策表如下：,得决策过程：x1*=2,x2*=0,x3*=7,f1*=218 即 市场1 分配 2人，市场2 不分配，市场3 分配 7人最优解与分配的顺序有关吗？,4.5.2 资源分配问题,例4 项目选择问题 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：,这是一类0-1规划问题该问题是经典的旅行背包问题(Knapsack)该问题是 NP-complete,例4 项目选择问题,解：设项目选择的顺序为A,B,C,D;1、阶段 k=1,2,3,4 分别对应 D,C,B,A项目的选择过程2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额4、状态转移方程为 sk1=sk wk xk5、直接效益 dk(sk,xk)=vk 或 06、总效益递推公式,该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。,例4 第一阶段(项目D)的选择过程,s18 时，x1只能取0；w1=8,v1=5,例4 第二阶段(项目C)的选择过程,例4 第三阶段(项目B)的选择过程,第四阶段(项目A)的选择过程,4.5.3 串联系统可靠性问题,例5 有 A,B,C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A,B,C 产生次品的概率分别为 pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案1:不拨款，机器保持原状；方案2:加装监视设备，每部机器需款 1 万元；方案3:加装设备，每部机器需款 2 万元；方案4:同时加装监视及控制设备，每部机器需款 3 万元；采用各方案后，各部机器的次品率如下表。,例5 串联机器可靠性问题,解：为三台机器分配改造拨款，设拨款顺序为A,B,C，阶段序号反向编号为 k，即第一阶段计算给机器 C 拨款的效果。设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；设 xk 为第 k 阶段的拨款额；状态转移方程为 sk-1=sk-xk；目标函数为 max R=(1-PA)(1-PB)(1-PC)仍采用反向递推第一阶段：对机器 C 拨款的效果 R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1),第二阶段最优决策表,第二阶段：对机器 B,C 拨款的效果 由于机器 A 最多只需 3 万元，故 s2 2 递推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)例：R2(3,2)=d2(3,2)R1(1,1)=(1-0.2)0.9=0.72 得第二阶段最优决策表,第二阶段最优决策表,第三阶段：对机器 A,B,C 拨款的效果 边界条件：s3=5 递推公式：R3(s3,x3)=d3(s3,x3)R2(s2,x2*)例：R3(5,3)=d3(5,3)R2(2,2)=(1-0.05)0.64=0.608 得第三阶段最优决策表,第二阶段最优决策表,回溯：有多组最优解。I：x3=1,x2=3,x1=1,R3=0.8 0.9 0.9=0.648 II：x3=2,x2=2,x1=1,R3=0.90.80.9=0.648III:x3=2,x2=3,x1=0,R3=0.90.90.8=0.648,资源分配问题可描述如下：设有某种原料，总数量为a，分配给n个使用者。已知第i个使用者得到数量xi的资源，可创造的收益为gi（xi）。问应如何分配该资源，才能使总收益最大。,4.4 动态规划的应用(二),用动态规划法处理这种问题时，通常把给一个使用者分配资源的过程看成一个阶段，按n个使用者分成先后n个决策阶段。即先给第1个使用者分配资源，为第一阶段；再给第2个使用者分配，为第2阶段；依此类推，最后给第n个使用者分配，为第n阶段。,2 资源分配问题,例 某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。,某单位准备在以后的n个时期内采购一批物资。各时期的价格不是确定的，而是按照某种已知的概率分布取值。试制定采购策略，确定在哪一时期以什么价格采购，能使采购价的数学期望值最低。这类问题也适合用动态规划法进行处理。下面通过实例加以说明。,例7 某厂生产上需要在近五周内采购一批原料，而估计在未来五周的价格有波动，其浮动价格和概率策得如下表。试确定该厂应在哪一周以什么价格购入，能使其采购价的数学期望值最小，并求出期望值。,4.4 动态规划的应用(三),3 不确定性采购问题,解:按釆购期限5周分为5个阶段,将每周的价格看作该阶段的状态,yk-为状态变量,表示笫k周的实际价格,ykE-表示笫k周等待,而在以后采取最优决策时采购价格的期望值,fk(yk)-表示笫k周实际价格为yk时,从第k周至第5周釆取最优决策所得的最小期望值,基本方程为,设有n个工件需要在机床A、B上加工，每个工件都必须先经过A而后B两道加工工序。以ai、bi分别表示工件i(1in)在A、B上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床A上加工第一个工件开始到在机床B上加工完最后一个工件为止，所用的加工总时间最少？,加工工件在机床A上有加工顺序问题，在机床B上也有加工顺序问题。可以证明：最优加工顺序在两台机床上可同时实现。因此，最优排序方案可以只在机床A、B上加工顺序相同的排序中寻找。即使如此，所有可能的方案仍有n!个，这是一个不小的数，用穷举法是不现实的。,4.4 动态规划的应用(四),4 排序问题,用动态规划法可以推出，工件i应该排在工件j之前的条件为 min(ai,bj)min(aj,bi)。根据这个条件，构造下列排序方法：a1 a2 an 1)建立工时矩阵 M=b1 b2 bn 2)在工时矩阵M中找出最小元素（若不止一个可任选其一），若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置。3)将排定位置的工件所对应的列从M中划去，然后对余下的工件再按2)进行排序。如此进行下去，直到把所有工件都排完为止。,当加工顺序排定之后，工件在A上没有等待时间，而在B上则常常需要等待。因此，寻求最优排序方案只有尽量减少在B上等待加工的时间，才能使总加工时间最短。,例 设有5个工件需在机床A、B上加工，加工的次序为先A后B，每个工件需要的加工时间如下表。试安排加工顺序，使总加工时间最少，并求出总加工时间。,