管理运筹学第10章动态规划.ppt

1,第十章 动态规划,1多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理3动态规划的应用(1)4动态规划的应用(2),2,1多阶段决策过程最优化问题举例,例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,3,1多阶段决策过程最优化问题举例,用穷举法的计算量:从A到E的路径有432=24条，计算每条路径的总长度需要做4次加法，则计算各路径长度总共要进行244=96次加法，做23次比较，才能得出结果。,4,1多阶段决策过程最优化问题举例,讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；,分析得知：从D1和D2到E的最短路径唯一。,5,第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题：,1多阶段决策过程最优化问题举例,分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。,6,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：,1多阶段决策过程最优化问题举例,分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。,7,第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：,1多阶段决策过程最优化问题举例,最后，可以得到：从A到E的最短路径为A B4 C3 D1 E,8,以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。,1多阶段决策过程最优化问题举例,以上过程，仅用了22次加法，计算效率远高于穷举法。,9,一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,2基本概念、基本方程与最优化原理,10,6、阶段指标函数rk(sk,xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,xn)：从状态sk出发，选择决策xk,xk+1,xn所产生的过程指标。动态规划要求过程指标具有可分离性，即 Vk,n(sk,xk,xk+1,xn)=rk(sk,xk)+Vk+1,n(sk+1,xk+1,xn)称指标具有可加性，或 Vk,n(sk,xk,xk+1,xn)=rk(sk,xk)Vk+1,n(sk+1,xk+1,xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即,2基本概念、基本方程与最优化原理,11,对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。,2基本概念、基本方程与最优化原理,12,三、最优化原理 作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。,2基本概念、基本方程与最优化原理,13,一、资源分配问题 例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如下表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？,3 动态规划的应用(1),14,解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个设备台数。已知s1=5,并有 从sk与xk的定义，可知以下我们从第三阶段开始计算。,3 动态规划的应用(1),15,第三阶段：s3=x3,3 动态规划的应用(1),16,3 动态规划的应用(1),第二阶段：S3=S2-X2,17,第一阶段：s1=5,s2=s1-x1=5-x1,3 动态规划的应用(1),（1）x1=0 s2=s1-x1=5-0=5 x2=2 s3=s2-x2=5-2=3 x3=3。即分配给甲厂0台，乙厂2台，丙厂3台利润最大，最大利润为21万元。（2）x1=2 s2=s1-x1=5-2=3 x2=2 s3=s2-x2=3-2=1 x3=1。即分配给甲厂2台，乙厂2台，丙厂1台利润最大，最大利润为21万元。,18,二、背包问题 设有n种物品，第i种物品数量为ni，第i种物品每件重量为wi公斤，第i种物品每件价值为ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,n），背包中物品的总价值为z，则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW xi ni(i=1,2,n)x1,x2,xn0 且为整数。,3 动态规划的应用(1),19,下面用动态规划逆序解法求解它。设 阶段变量k：装载第k种物品（k=1,2,n）状态变量sk：装载第k种物品到第n种物品的重量；决策变量 xk：装载第k种物品的件数；决策允许集合：Dk(sk)=xk|0 xksk/wk，xk为整数；状态转移方程：sk+1=sk wkxk；阶段指标：rk=ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程：fk(sk)=max ckxk+fk+1(sk+1)=max ckxk+fk+1(sk wkxk)；xDk(sk)终端条件：fn+1(sn+1)=0。,3 动态规划的应用(1),20,例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如下表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？,3 动态规划的应用(1),21,3动态规划的应用(1),解：用整数规划来解有：设xi为处理第i种咨询项目的客户数，则其整数规划模型为：Max z=2x1+8x2+11x3+20 x4S.t.x1+3x2+4x3+7x4 10 x14 x2 3 x3 2 x4 2x1,x2,x3,x40且为整数。,22,解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设sk：分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。xk：在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知s110并有s2=T1(s1,x1)=s1-x1,s3=T2(s2,x2)=s2-3x2 s4=T3(s3,x3)=s3-4x2,3 动态规划的应用(1),23,第四阶段：x4=s4/7=0,1,3 动态规划的应用(1),24,第三阶段：x3=s3/4=0,1,2,s4=s3-4x3,3 动态规划的应用(1),25,3动态规划的应用(1),第二阶段：x2=s2/3=0,1,2,3；s3=s2-3x2,26,第一阶段：s2=s1-x1=10-x1,3动态规划的应用(1),x1=0s2=s1-x1=10-0=10 x2=1 s3=s2-3x2=10-31=7 x3=0 s4=s3-4x3=7-40=7 x4=1。即第一个咨询项目处理的客户数为0户，第二个咨询项目处理的客户数为1户，第三个咨询项目处理的客户数为0户，第四个咨询项目处理的客户数为1户，获得的利润最大，最大利润为28。,27,三、生产与存贮问题 例4.某公司为主要电力公司生产大型变压器，由于电力公司采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如下表所示。,3动态规划的应用(1),28,3动态规划的应用(1),每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？,生产成本的调试费为4，生产成本除了调试费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如下表所示。,29,解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4).设sk为第k阶段期初库存量；k=1,2,3,4 xk为第k阶段生产量；k=1,2,3,4dk为第k阶段需求量；k=1,2,3,4，因为下个月初的库存量等于上个月初的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：,3动态规划的应用(1),各月的生产成本和储存费用分别用ck(xk)和hk(sk,xk)表示，即阶段指标函数为：rk(sk,xk)=ck(xk)+hk(sk,xk),30,第四阶段：r4(s4,x4)=c4(x4)+h4(s4,x4)=c4(3-s4),3动态规划的应用(1),31,第三阶段：r3(s3,x3)=c(x3)+h(s3,x3),s4=s3+x3-1,3动态规划的应用(1),32,第二阶段：r2(s2,x2)=c(x2)+h(s2,x2),s3=s2+x2-4,3动态规划的应用(1),33,第一阶段：r1(s1,x1)=c(x1)+h(s1,x1),s2=s1+x1-2=x1-1,3动态规划的应用(1),利用递推关系可以从得到两组最优解：x1=1s2=x1-1=1-1=0 x2=4 s3=s2+x2-4=0+4-4=0 x3=4 s4=s3+x3-1=0+4-1=3 x4=0，即1、2、3、4月份分别生产1、4、4、0台变压器，能使四个月的生产成本和存储总费用最省，最小费用为29。x1=2s2=x1-1=2-1=1 x2=4 s3=s2+x2-4=1+4-4=1 x3=0 s4=s3+x3-1=1+0-1=0 x4=3，即1、2、3、4月份分别生产2、4、0、3台变压器，能使四个月的生产成本和存储总费用最省，最小费用为29。,34,3动态规划的应用(1),四、系统可靠性问题 例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：,问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？,35,3动态规划的应用(1),解：用逆序算法。设 阶段：每个研究小组为一个阶段，共分为3个阶段进行，且,决策变量xk：分配给第k小组的高级科学家人数，相应的失败概率为rk(sk,xk)（k=1,2,3），即为阶段指标函数；状态变量sk：分配给第k小组至第3小组的高级科学家人数（k=1,2,3)。则状态转移方程为：s1=1 s2=s1-x1 s3=s2-x2递推方程为：fk(sk)=minrk(sk,xk)fk+1(sk+1),36,3动态规划的应用(1),第一阶段：s3=x3,第二阶段：s3=s2-x2,37,3动态规划的应用(1),第一阶段：,最优解为 x1=1s2=s1-x1=2-1=1 x2=0 s3=s2-x2=1-0=1 x3=1；即当分配给第1、2、3小组的高级科学家人数分别为1、0、1人时，科研项目最终失败的概率最小，最小概率为0.060。,38,4动态规划的应用(2)*,一、连续确定性动态规划 对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。,39,4动态规划的应用(2)*,机器负荷分配问题 例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。,40,4动态规划的应用(2)*,解 建立动态规划模型：分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。状态转移方程为 sk+1=0.7xk+0.9(sk-xk)阶段指标 rk(sk,xk)=8xk+5(sk-xk)最优指标函数,(k=1,2,3,4,5),f6(s6)=0,41,4动态规划的应用(2)*,第5阶段：因为f5(s5)=max8x5+5(s5-x5)=max5s5+3x5,而0 x5s5,故有x5*=s5，于是有f5(s5)=8s5。第4阶段：,42,4动态规划的应用(2)*,故有x4*=s4，f4(s4)=13.6s4。对前几个阶段依次类推，可得 f3(s3)=max17.24s3+0.28x3,而0 x3s3，故当x3*=s3时，有f3(s3)=17.5s3，f2(s2)=max20.768s2-0.704x2,而0 x2s2，故当x2*=0时，有f2(s2)=20.768s2，f1(s1)=max23.6912s1-1.1236x1,而0 x1s1，故当x1*=0时，有f1(s1)=23.6912s1。综上所述，得最优解为x1*=0，x2*=0，x3*=s3，x4*=s4,x5*=s5。因为期初共有完好机器1000台，故s1=1000,有f1(s1)=23.6912s123691.2，即5年最大的产量为23691.2。而 s2=0.7x1*+0.9(s1-x1*)=0.9s1=0.91000=900,s3=0.7x2*+0.9(s2-x2*)=0.9s2=0.9900=810,s4=0.7x3*+0.9(s3-x3*)=0.7s3=0.7810=567 s5=0.7x4*+0.9(s4-x4*)=0.7s4=0.7567=397 s6=0.7x5*+0.9(s5-x5*)=0.7s5=0.7397=278 这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。,43,4动态规划的应用(2)*,下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:,44,4动态规划的应用(2)*,上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？下面来分析：根据终点条件有 可得,45,4动态规划的应用(2)*,显然，由于固定了终点的状态，x5的取值受到了约束。因此有 类似的，容易解得，f4(s4)=21.7s4-7500。,46,4动态规划的应用(2)*,依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000，,47,4动态规划的应用(2)*,可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。相应的最优指标为 f1(s1)=29.4s1-750021900。可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。,48,二、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：,4动态规划的应用(2)*,sk,状态,xk,决策,概率,k阶段的收益,p1,p2,pN,.,k+1阶段的状态sk+1,c1,c2,cN,1,2,N,49,4动态规划的应用(2)*,图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。,50,离散随机性动态规划,例2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？,51,离散随机性动态规划,解：把三次试制当作三个阶段（k=1,2,3）,决策变量xk表示第k次生产的产品的件数；状态变量sk表示第k次试制前是否已经生产出合格品，如果有合格品，则sk=0；如果没有合格品，记sk=1。最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)0。生产出一件合格品的概率为0.4，所以生产xk件产品都不合格的概率为，至少有一件合格品的概率为1-，故有状态转移方程为,52,离散随机性动态规划,用C(xk)表示第k阶段的费用，第k阶段的费用包括制造成本和装配费用，故有 根据状态转移方程以及C(xk)，可得到,53,离散随机性动态规划,如果3个月后没有试制出一件合格品，则要承担2000元的罚金，因此有f4(1)=20。当k=3时，计算如下表：,54,离散随机性动态规划,当k=2时，计算如下表：,55,离散随机性动态规划,当k=1时，有,56,离散随机性动态规划,上面三个表中并没有列出xk取更大数值的情况，因为可以证明以后的C(xk)+fk+1(1)的值是对xk单调增加的。因此得到的最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望费用6.46。,57,离散随机性动态规划,随机采购问题例3 某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？,58,离散随机性动态规划,解：建立动态规划。按照采购周期分为5个阶段，将每周的价格看作该阶段的状态。假设状态变量sk表示第k周的实际价格，决策变量xk表示第k周是否采购的0-1变量。如决定采购，则xk=1；如选择等待，则xk=0。用skE表示第k周等待，而在以后采取最优决策时采购价格的期望值。根据定义，动态规划基本方程如下：,59,离散随机性动态规划,第五阶段：因为如果前4周都没有买，那第5周必须购买，因此有f5(s5)=s5，即f5(450)=450；f5(470)=470；f5(500)=500。第四阶段：下面考虑第4周的情况。如第4周购买，则需花费s4；如果不买，则必须在第5周购买。在第5周采购的费用的期望值为,60,离散随机性动态规划,于是，有 故第4周的最优决策为 同理，考虑第3周的最优决策。,61,离散随机性动态规划,第三阶段：如果第3周采购，则需花费s3；也要和第3周后再采购的费用的期望值作比较。于是，有故第3周的最优决策为,62,离散随机性动态规划,第二阶段：同理可得 故第2周的最优决策为,63,离散随机性动态规划,第一阶段：同理可得第1周的最优决策为,64,离散随机性动态规划,由上可知，最优的采购策略为：在第1、2、3周的市场价格为450时，应该立即采购，否则等待；在第4周时，若市场价格为450或470时，应该采购，否则等待。若等到第五周，只能采购。,