【大学课件】动态规划应用举例.ppt

2024/8/311Ø资源分配问题Ø生产与存贮问题Ø设备更新问题动态规划应用举例动态规划应用举例2024/8/31 资源分配问题资源分配问题 6.3.16.3.1一维离散资源一维离散资源分配问题分配问题 设设有有某某种种原原料料，，总总数数量量为为a，，用用于于生生产产n种种产产品品若若分分配配数数量量xi用用于于生生产产第第i 种种产产品品，，其其收收益益为为g gi i(x(xi i) )问应如何分配，才能使生产问应如何分配，才能使生产n种产品的总收入最大？种产品的总收入最大？ 将将数数量量一一定定的的一一种种或或若若干干种种资资源源，，恰恰当当地地分分配配给给若干个使用者，使目标函数为最优若干个使用者，使目标函数为最优MAX =g1(x1)+ g2(x2)+‥ ‥+ gn(xn)x1+x2+…+ xn=axi≥0 i=1,2, …,ns.t.2024/8/31 Dk( (sk)={)={uk|0|0 uk= =xk sk} }•uk: :分配给生产第分配给生产第k种产品的原料数量，即种产品的原料数量，即uk= =xk；；•sk: :分配给用于生产分配给用于生产第第k种至第种至第n种种产品的原料数量；产品的原料数量；•状态转移方程状态转移方程：： sk+1+1= =sk- -uk= =sk- -xk•最最优优值值函函数数fk( (sk) ): :数数量量为为sk的的原原料料分分配配给给第第k种种产产品品至至第第n种种产产品品所所得得到到的的最最大大总总收收益益，，动动态态规规划划的的递递推推关系为：关系为：2024/8/31 5台某种设备分配给所属的甲、乙、丙台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。

提供的盈利如表 问：这五台设备如何分配给各工厂，才能使问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大公司得到的盈利最大例例1 1解解：：将将问问题题按按工工厂厂分分为为三三个个阶阶段段，，甲甲、、乙乙、、丙丙分分别别编号为编号为1 1，，2 2，，3 3逆推法逆推法﹗﹗2024/8/31 s3 5，， 0 x3 s3可分配的机器数量可分配的机器数量分配的机器数量分配的机器数量 sk+1+1= =sk- -uk= =sk- -xkf3(s3)=max﹝ ﹝g3﹙ ﹙x3﹚﹞ ﹚﹞ 0≤x3≤s3f4(s4)=0S3=?g3(0)g3(1) =4x3 *(1) =1= g3﹙﹙0﹚﹚=0S3=0, f3(0)=max｛｛ g3﹙ ﹙x3﹚ ﹚+ f4(s4) ｝｝ 0≤x3≤s3x3 *(0) =0=max x3=0,1S3=1, f3(1)=max｛｛ g3﹙ ﹙x3﹚ ﹚+ f4(s4) ｝｝0≤x3≤s32024/8/312024/8/312024/8/31 s3=s2-x2，， 0 s2 5，， 0 x2 s2，，有有2024/8/312024/8/312024/8/312024/8/31 =4 f3(5-3)=f3(2)2024/8/31 s2=s1-x1，， s1=5，， 0 x1 s1，，有有S1=5, f1(S1 )=max｛｛ g1﹙ ﹙x1﹚ ﹚+ f2(s2) ｝｝0≤x1≤s1=max｛｛ g1﹙ ﹙x1﹚ ﹚+ f2(s1- x1) ｝｝x1=0,1,2,3,4,5=maxg1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0) x1*(5)=0, 20+213+167+149+1012+513+0= max2024/8/312024/8/312024/8/31 以上两个分配方案所得到的总盈利均为以上两个分配方案所得到的总盈利均为21万元万元问题：如果原设备台数是问题：如果原设备台数是4台，求最优分配方案？台，求最优分配方案？ 如果原设备台数是如果原设备台数是3台，求最优分配方案？台，求最优分配方案？2024/8/31 一维连续资源分配问题一维连续资源分配问题: 一般问题的提法是一般问题的提法是 A种生产种生产数量数量u1投入投入 收益收益g(u1) 年终资源回收率年终资源回收率a如此进行如此进行n年，如何确定投入年，如何确定投入A的资源量的资源量u1、、…、、un，使总收入最大？，使总收入最大？ B种生产种生产数量数量s1-u1 收益收益h(s1-u1) 年终资源回收率年终资源回收率b资源数量资源数量s1第一年第一年资源数量资源数量s2=au1+b(s1-u1)第二年第二年 A种生产种生产数量数量u2投入投入;收益收益g(u2);年终回收率年终回收率a B种生产种生产数量数量s2-u2;收益收益h(s2-u2);年终回收率年终回收率b到到n年年2024/8/312024/8/31 高负荷高负荷: 产量函数产量函数 g=8u1, u1是投入生产的机器是投入生产的机器 数量，年完好率为数量，年完好率为 a=0.7，， 低负荷低负荷: 产量函数产量函数 h=5y，， y是投入生产的机器是投入生产的机器数量，数量， 年完好率为年完好率为b=0.9。

假定开始生产时完好机器的数量为假定开始生产时完好机器的数量为1000台 机机器器 例例2 2 机器负荷分配问题机器负荷分配问题解：设阶段数解：设阶段数k表示年度表示年度 试问每年如何安排机器在高低两种负荷下的生产，试问每年如何安排机器在高低两种负荷下的生产，可使可使5年内生产的产品总产量最高年内生产的产品总产量最高状态变量状态变量sk为第为第k年度初拥有的完好机器台数；年度初拥有的完好机器台数； 决策变量决策变量uk为第为第k年度中分配高负荷下生产的机年度中分配高负荷下生产的机 器器台数 低负荷下生产的机器台数是低负荷下生产的机器台数是sk-uk2024/8/31 状态转移方程状态转移方程第第k年度产量为年度产量为 递推方程递推方程为为指标函数指标函数为为允许决策集合允许决策集合 0 uk sk2024/8/31 , f5(s5)= max ﹛ ﹛8u5+5﹙ ﹙ s5 - u5 ﹚ ﹚ + f6(s6) ﹜﹜0≤u5 ≤ s5=max ﹛ ﹛3u5+5 s5 ﹜ ﹜0≤u5 ≤ s5u5*= s5 , f5(s5)=8 s5当当k=4时时 , f4(s4)= max ﹛ ﹛8u4+5( s4 – u4 ) + f5(0.7 u4+0.9(s4 – u4 )) ﹜﹜0≤u4 ≤ s4= max ﹛ ﹛13.6u4+12.2( s4- u4)﹜ ﹜0≤u4 ≤ s4= max ﹛ ﹛1.4u4+12.2 s4﹜ ﹜0≤u4 ≤ s4u4*= s4 , f4(s4)=13.6s42024/8/31 u3*=s3 f3(s3)=17.5 s3 u2*=0 f2(s2)=20.8 s2 u1*=0 f1(s1)=23.7 s1 最高产量为最高产量为23700。

因此因此最优策略最优策略为为: u1*=0, u1*=0, u3*=s3, u4*= s4 u5*= s5, u5*= s5 , f5(s5)=8 s5u4*= s4 , f4(s4)=13.6s42024/8/31 该如何安排生产？该如何安排生产？S6=5002024/8/31 在生产和经营管理中，经常遇到要合理安排生产（或在生产和经营管理中，经常遇到要合理安排生产（或购买）与库存的问题，达到既要满足社会的需要，又要尽购买）与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用因此，正确指定生产（或采购）策略，量降低成本费用因此，正确指定生产（或采购）策略，确定不同时期的生产量（或购买量）和库存量，以使总的确定不同时期的生产量（或购买量）和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标题的最优化目标 设某公司对某种产品要制定一项设某公司对某种产品要制定一项n个阶段的生产计划个阶段的生产计划已知它的初始库存量为零，每阶段生产该产品的数量有上已知它的初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在保证供应；在n阶段末的终结库存量为零。

问该公司如何阶段末的终结库存量为零问该公司如何制定每个阶段的生产计划，从而使总成本最小？制定每个阶段的生产计划，从而使总成本最小？第二节第二节 生产与存贮问题生产与存贮问题 2024/8/31 sk +1= sk + xk -dk 第k阶段的成本费用包括生产成本和存贮费用两项 ：：2024/8/31 (k= n,n-1，，…, 1) 2024/8/31 这是因为一方面每阶段生产的上限为m；另一方面保证第n阶段结束时库存量可以取0而 这是因为为了保证第k阶段能满足需求 2024/8/31 某工厂生产并销售某种产品，已知今后某工厂生产并销售某种产品，已知今后4个月市场需求个月市场需求预测如表所示预测如表所示 并且有如下假定：固定成本为并且有如下假定：固定成本为3千元，若千元，若不生产就为不生产就为0；每单位产品成本为；每单位产品成本为1千元；每个月生产能力千元；每个月生产能力所允许的最大生产批量为不超过所允许的最大生产批量为不超过6个单位；每个月末未售出个单位；每个月末未售出的产品，每单位需付存储费的产品，每单位需付存储费0.5千元。

还假定在第一个月的千元还假定在第一个月的初始库存量为初始库存量为0，第四个月末的库存量也为，第四个月末的库存量也为0 问：如何安排各月的生产与库存问：如何安排各月的生产与库存 ，使总成本最小使总成本最小 2024/8/312024/8/31 sk+1时的存储费用为 ，故第k时期内的总成本为 ，而动态规划的基本方程为： （（k＝＝4，，3，，2，，1）） 其中其中 2024/8/31 d4- s4，其计算如下表： 4321076540 7 6 5 4001234432102024/8/31 ， 其计算如下表 ： 2024/8/312024/8/31 ，其中， 其计算如下表：2024/8/312024/8/31 其相应的其相应的最小总成本为最小总成本为20.5千元。

千元2024/8/31 个人、单位等随时均有设备更新问题彩电、设备随着使用个人、单位等随时均有设备更新问题彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加处于各种阶段的设备总是面临保留还是更新问题保费用增加处于各种阶段的设备总是面临保留还是更新问题保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题局部的某个阶段的回收额来考虑，是一个多阶段的决策问题设备更新问题提法如下（以一台机器为例）：设备更新问题提法如下（以一台机器为例）： n为计划设备使用年数为计划设备使用年数 Ik(t) 为第为第k年（阶段）机器役龄为年（阶段）机器役龄为t年的一台机器运行（再使用年的一台机器运行（再使用一年）所得的收入一年）所得的收入 Ok(t) 为第为第k年机器役龄为年机器役龄为t年的一台机器运行（再使用一年）年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）时所需运行的费用（或维修费用） 。

Ck(t) 为第为第k年机器役龄为年机器役龄为t年的一台机器更新时所需更新的净年的一台机器更新时所需更新的净费用（处理一台役龄为费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费的旧设备，买进一台新设备的更新净费用）第三节设备更新问题第三节设备更新问题 2024/8/31 • 阶段效益为：阶段效益为： 为折扣因子，表示一年以后的收入是上一年的为折扣因子，表示一年以后的收入是上一年的 单位要求在要求在n年内的每年年初作出决策，是继续使用旧设备还是更年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使换一台新的，使n年内总效益最大？年内总效益最大？2024/8/31 最优指标函数gk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为实际上实际上2024/8/31 =1））2024/8/312024/8/312024/8/312024/8/312024/8/31 所以有所以有2024/8/312024/8/31。