运筹学动态规划应用举例.pptx

第四节动态规划在经济管理中的应用连续变量的离散化解法连续变量的离散化解法 先先介介绍绍连连续续变变量量离离散散化化的的概概念念。如如投投资资分分配配问问题题的一般静态模型为：的一般静态模型为：模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量态变量 状态转移方程、基本方程、指标函数、最优指标函数状态转移方程、基本方程、指标函数、最优指标函数第1页/共59页建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：其状态转移方程为其状态转移方程为:由于由于 与与 都是连续变量，当各阶段指标都是连续变量，当各阶段指标 没没有特殊性而较为复杂时，有特殊性而较为复杂时，要求出要求出 会比较困难，因而求会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下：离散化的办法求其数值解。具体做法如下：第2页/共59页（1 1）令令 ，把区间把区间 0 0，aa进行分割，进行分割，的大小可的大小可依据问题所要求的精度以及计算机的容依据问题所要求的精度以及计算机的容量来定。量来定。第3页/共59页(2)(2)规定状态变量规定状态变量 及决策变量及决策变量 只在离散点只在离散点 上取值，相应的指标上取值，相应的指标函数函数 就被定义在这些离散值上，于是递推方就被定义在这些离散值上，于是递推方程就变为：程就变为：其中 第4页/共59页 作为离散化例子，在例作为离散化例子，在例5 5中规定状态变量和决中规定状态变量和决策变量只在给出的离散点上取值，见例策变量只在给出的离散点上取值，见例6 6。（3 3）按按逆逆序序方方法法，逐逐步步递递推推求求出出 ，最后求出最优资金分配方案。，最后求出最优资金分配方案。第5页/共59页问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大?例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为：时，其效益分别为：第6页/共59页例例6 6 连续变量的离散化解法连续变量的离散化解法第7页/共59页解解 令令 ，将区间，将区间00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六个点，即状态变量六个点，即状态变量 集合为集合为 允许允许决策集合为决策集合为 ，与与 均在分割点上取值。均在分割点上取值。动态规划基本方程为：动态规划基本方程为：当当k=3k=3时，时，第8页/共59页式中式中 与与 的集合均为：的集合均为：计算结果见表计算结果见表7-17-1。02468100832721282000246810当k=3时，表7-1 第9页/共59页当k=2时，计算结果见表计算结果见表7-27-2。024681000 20 2 40 2 4 60 2 4 6 80 2 4 6 8 1008 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 900 18 36 72 128 2000 24 0 0 0表表7-2 7-2 第10页/共59页当k=1时，计算结果见表计算结果见表7-37-3。表7-3 1010101010100246810200136886050402000第11页/共59页最大收益为最大收益为 ，与例，与例5 5结论完全相同。结论完全相同。计算结果表明，最优决策为：计算结果表明，最优决策为：应指出的是：这种方法有可能丢失最优解，应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。一般得到原问题的近似解。第12页/共59页一、背包问题一、背包问题一一位位旅旅行行者者携携带带背背包包去去登登山山，已已知知他他所所能能承承受受的的背背包包重重量量限限度度为为a kg，现现有有n种种物物品品可可供供他他选选择择装装入入背背包包，第第i种种物物品品的的单单件件重重量量为为ai kg，其其价价值值是是携携带带数数量量xi的的函函数数ci(xi)(i=1,2,n)，问问旅旅行行者者应应如如何何选选择择携携带带各各种种物物品品的的件件数，以使总价值最大？数，以使总价值最大？第13页/共59页例例1有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载的卡车，用以装载3种货物，每种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可使种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？总价值最大？货物编号i123单位重量(t)345单位价值ci456逆序解法：逆序解法：阶段阶段k：k=1,2,3状态变量状态变量sk:第第k阶段可以装载第阶段可以装载第k种到第种到第3种货物的重量。种货物的重量。决策变量决策变量xk:决定装载第决定装载第k种货物的数量。种货物的数量。状态转移方程状态转移方程:sk+1=sk-akxk最优指标函数最优指标函数fk(sk):当可装载重量为当可装载重量为sk,装载第装载第k种到第种到第3种货物所获得的种货物所获得的最大价值。最大价值。基本方程：基本方程：第14页/共59页当阶段k=3时，有s3012345678910 x3000000101010101012c3+f40000006060606060612f3000006666612x3*00000111112当阶段k=2时，有s2012345678910 x2000001010101012012012c2+f3000005+0656565651065+610125+610f200005666101112x2*00001000210第15页/共59页当阶段k=1时，有s110 x10123c1+f3124+68+512f213x1*2第16页/共59页二、生产经营问题 在在生生产产和和经经营营管管理理中中，经经常常遇遇到到如如何何合合理理地地安安排排生生产产计计划划、采采购购计计划划以以及及仓仓库库的的存存货货计计划划和和销销售售计计划划，使使总总效效益益最最高高的的问问题题。下下面面通通过过例例子子来来说说明明对对不不同同特特点点问问题题的的不不同同处理技巧处理技巧。第17页/共59页例2生产与存贮问题某某工工厂厂生生产产并并销销售售某某种种产产品品，已已知知今今后后四四个个月月市市场场需需求求预预测测如如表表，又又每每月月生产生产j单位产品费用为：单位产品费用为：每每月月库库存存j j单单位位产产品品的的费费用用为为 ，该该厂厂最最大大库库存存容容量量为为3 3单单位位，每每月月最最大大生生产产能能力力为为6 6单单位位，计计划划开开始始和和计计划划期期末末库库存存量量都都是是零零。试试制制定定四四个个月月的的生生产产计计划划，在在满满足足用用户户需需求求条条件件下下总总费费用用最最小小。假假设设第第i+1i+1个个月月的的库库存存量量是是第第i i个个月月可可销销售售量量与与该该月月用用户户需需求求量量之之差差；而而第第i i个个月月的的可可销销售售量量是是本本月初库存量与产量之和。月初库存量与产量之和。12342324第18页/共59页用动态规划方法求解时，对有关概念作如下分析：用动态规划方法求解时，对有关概念作如下分析：(1)(1)阶段：每个月为一个阶段，阶段：每个月为一个阶段，k k1 1，2 2，3 3，4 4。(2)(2)状态变量：状态变量：为第为第k k个月初的库存量。个月初的库存量。(3)(3)决策变量：决策变量：为第为第k k个月的生产量。个月的生产量。(4)(4)状态转移方程：状态转移方程：(5)(5)最最优优指指标标函函数数：表表示示第第k k月月状状态态为为 时时，采采取取最最佳佳策策略略生生产产，从从本本月月到到计计划划结结束束(第第4 4月月末末)的的生生产产与与存存贮贮最最低费用。低费用。（6 6）基本方程：）基本方程：第19页/共59页k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。s40123u44321C+E+f576+0.55+14+1.5f476.565.5u4*4321k3，s4=s3+u3-g3，所以，所以u3=s4+g3-s3，s3可取可取0，1，2，3。s30123u3234512340123012C+E+f45+76+6.57+68+5.54.5+75.5+6.56.5+67.5+5.51+75+6.56+67+5.51.5+6.55.5+66.5+5.5f31211.588u3*2100第20页/共59页k2，s3=s2+u2-g2，所以，所以u2=s3+g2-s2，s2可取可取0，1，2，3。s20123u23456234512340123C+E+f36+127+11.58+89+85.5+126.5+11.57.5+88.5+85+126+11.57+88+81.5+125.5+11.56.5+87.5+8f21615.51513.5u2*5430k1，s2=s1+u1-g1，所以，所以u1=s2+g1-s1，s1可取可取0。s10u12345C+E+f25+166+15.57+158+13.5f121u1*2反推回去，反推回去，u1*=2，u2*=5，u3*=0，u4*=4。第21页/共59页例3 3 采购与销售问题 某商店在未来的某商店在未来的4 4个月里，准备利用它的一个仓库来专门经销某种商品，个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商品仓库最大容量能贮存这种商品l000l000单位。假定该商店每月只能出卖仓库现单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表的买卖价格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月开始经销时，仓库贮有该商品月开始经销时，仓库贮有该商品500500单位。试问若不计库存费用，该商店应如何制定单位。试问若不计库存费用，该商店应如何制定1 1月至月至4 4月的订购与销售月的订购与销售计划，使预期获利最大。计划，使预期获利最大。月份（k）购买单价（ck）销售单价（pk）110122983111341517第22页/共59页解按月份划分为4个阶段，k=l，2，3，4状态变量：第k月初时仓库中的存货量(含上月订货)。决策变量：第k月卖出的货物数量。：第k月订购的货物数量。状态转移方程：最优指标函数：第k k月初存货量为时，从第k k月到4 4月末所获最大利润。则有逆序递推关系式为：第23页/共59页当k=4时显然，决策应取时才有最大值第24页/共59页当k=3时这个阶段需解一个线性规划问题：因 为 只 有 两 个 变 量 x3,y3，可 以 用 图 解 法，也 可 以 用 单 纯 形 法，求 解 得 到：时有最大值第25页/共59页当k=2时求解线性规划问题：得第26页/共59页当k=1时求解一个线性规划问题：得 第27页/共59页最优策略见下表。最大利润为1600016000。月份期前存货售出量购进量15005000200100031000100010004100010000第28页/共59页例例4 4 限期采购问题限期采购问题(随机型随机型)某部门欲采购一批原料，原料价格在五周内可能有某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概所变动，已预测得该种原料今后五周内取不同单价的概率如表率如表7-147-14所示。试确定该部门在五周内购进这批原料所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的的最优策略，使采购价格的期望值期望值最小。最小。原材料单价（元）概率5006007000.30.30.4表7-14第29页/共59页 阶段阶段k k：可按采购期限可按采购期限(周周)分为分为5 5段，段，k k1 1，2 2，3 3，4 4，5 5。状态变量状态变量 ：第：第k k周的原料实际价格。周的原料实际价格。决策变量 ：第k周如采购 则 1，若不采购 则 =0 =0。另外用 表示：当第k周决定等待，而在以后采购时的采购价格期望值。最优指标函数：第k周实际价格为时，从第k周至第5周采取最优策略所花费的最低期望价格。则有逆序递推关系式为：解解 本本例例与与前前面面所所讨讨论论的的确确定定型型问问题题不不同同，状状态态的的转转移移不不能能完完全全确确定定，而而按某种已知的按某种已知的概率分布概率分布取值，即属于取值，即属于随机型随机型动态规划问题。动态规划问题。为状态集合500，600，700。第30页/共59页当k=5时 因为若前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以第31页/共59页当k=4时由于 所以第32页/共59页当k=3时由于 所以第33页/共59页当k=2时 同理第34页/共59页当k=1时第35页/共59页 所所以以，最最优优采采购购策策略略为为：若若第第一一、二二、三三周周原原料料价价格格为为500500，则则立立即即采采购购，否否则则在在以以后后的的几几周周内内再再采采购购。若若第第四四周周价价格格为为500500或或600600，则则立立即即采采购购，否否则则等等第第五五周周再再采采购购。而第五周时无论当时价格为多少都必须采购。而第五周时无论当时价格为多少都必须采购。按照以上策略进行采购，期望价格为：按照以上策略进行采购，期望价格为：第36页/共59页三、设备更新问题 从经济上分析，一台设备应该从经济上分析，一台设备应该 使用多少年更新最使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多少，故障变多,维修费用增加。如果更新可提高年净收维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费，为了比较入，但是当年要支出一笔数额较大的购买费，为了比较不同决策的优劣，常常要在一个较长的时间内考虑更新不同决策的优劣，常常要在一个较长的时间内考虑更新决策问题。决策问题。第37页/共59页设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。uk(t)：在第k年设备役龄为t年，再使用一年的维修费用。ck(t)：在第k年卖掉台役龄为t年的设备，买进一台新设备的更新净费用。为折扣因子(01)，表示一年以后的单位收入价值相当于现年的 单位。第38页/共59页动态规划模型阶段变量k：k=1,2,n，表示计划使用该设备的年限数。状态变量sk:第k年初，设备已使用过的年数，即役龄。决策变量xk:是第k年初更新（Replacement），还是保留使用（keep）旧设备，分别用R与K表示。状态转移方程为：阶段指标为：指标函数为：第39页/共59页最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程：实际上，第40页/共59页例例5 5 设设某某台台新新设设备备的的年年效效益益及及年年均均维维修修费费、更更新新净净费费用用如如表表7-7-1515所所示示。试试确确定定今今后后5 5年年内内的的更更新新策策略略，使使总总收收益益最最大大。（设设 ）役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5第41页/共59页解如前述建立动态规划模型，n=5当k=5时，状态变量s5可取1，2，3，4。=2.5 =2 =1.5 役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5第42页/共59页当k=4时，状态变量s4可取1，2，3。=6.5 役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5=5.8=5.5 第43页/共59页当k=3时，状态变量s3可取1，2。=9.5 役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5=8.8 第44页/共59页当k=2时，状态变量s2只能取1役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5=12.5 第45页/共59页当k=1时，状态变量s1只能取0役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5=17 第46页/共59页 上述计算递推回去，当 时，由状态转移方程，则则查 得：状态 ，查：推出 ，查最优策略为：，即第一年初购买的设备到第二、三、四年初各更新一次，用到第5年末，其总效益为17万元。第47页/共59页k5，s5可取可取1,2,3,4。s51234u5KRKRKRKRv5+f64.5-15-0.5-1.54-1.55-0.5-2.23.75-25-0.5-2.53-2.55-0.5-3f53.52.521.5u5*KKRRk4,s4可取可取1,2,3。s4123u4KRKRKRv4+f54.5-1+2.55-0.5-1.5+3.5 4-1.5+25-0.5-2.2+3.53.75-2+1.55-0.5-2.5+3.5f46.55.85.5u4*RRR第48页/共59页k3，s3可取可取1,2。s312u3KRKRv3+f44.5-1+5.85-0.5-1.5+6.54-1.5+5.55-0.5-2.2+6.5f49.58.8u4*RRk2,s2可取可取1。s21u2KRv3+f24.5-1+8.85-0.5-1.5+9.5f212.5u2*Rk1,s2可取可取0。s10u1KRv1+f25-0.5+12.55-0.5-0.5+12.5f117u1*K第49页/共59页 货郎担问题一般提法为：一个货郎从某货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅一次，城镇出发，经过若干个城镇一次，且仅一次，最后仍回到原出发的城镇，问应如何选择行最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这著名问题，实际中有很多问题可以归结为这类问题。类问题。四、货郎担问题第50页/共59页 设设 是已知的是已知的n n个城镇，城镇个城镇，城镇 到城到城镇镇 的距离为的距离为 ，现求从，现求从 出发，经各城镇一出发，经各城镇一次且仅一次返回次且仅一次返回 的最短路程。若对的最短路程。若对n n个城镇进行排个城镇进行排列，有列，有 (n(n一一1)!1)!2 2种方案，所以穷举法是不现种方案，所以穷举法是不现实的，这里介绍一种动态规划方法。实的，这里介绍一种动态规划方法。货郎担问题也是求最短路径问题，但与例货郎担问题也是求最短路径问题，但与例4 4的最短的最短路问题有很大不同，建动态规划模型时，虽然也可按城路问题有很大不同，建动态规划模型时，虽然也可按城镇数目镇数目n n将问题分为将问题分为n n个阶段。但是状态变量不好选择，个阶段。但是状态变量不好选择，不容易满足无后效性。为保持状态间相互独立，可按以不容易满足无后效性。为保持状态间相互独立，可按以下方法建模：下方法建模：第51页/共59页 设设S S表示从表示从 到到 中间所有可能经过的城中间所有可能经过的城市集合，市集合，S S实际上是包含除实际上是包含除 与与 两个点之外其两个点之外其余点的集合，但余点的集合，但S S中的点的个数要随阶段数改变。中的点的个数要随阶段数改变。状态变量状态变量 表示：从表示：从 点出发经过点出发经过S S集合中所有点一次最后到达集合中所有点一次最后到达 。最优指标函数最优指标函数 为从为从 出发经由出发经由k k个个城镇的城镇的S S集合到集合到V Vi i的最短距离。的最短距离。第52页/共59页 决策变量决策变量 表示：从表示：从 经经k k个中间城个中间城镇的镇的S S集合到集合到 城镇的最短路线上邻接城镇的最短路线上邻接 的前的前一个城镇，则动态规划的顺序递推关系为一个城镇，则动态规划的顺序递推关系为：第53页/共59页例例6 6 已知已知4 4个城市间距离如表个城市间距离如表7 71616，求从，求从v1v1出发，经其出发，经其余城市一次且仅一次最后返回余城市一次且仅一次最后返回v1v1的最短路径与距离。的最短路径与距离。第54页/共59页解解 由边界条件（由边界条件（7.21b7.21b）知：）知：当当k=1k=1时，从城市时，从城市v v1 1出发，经过出发，经过1 1个城镇到达个城镇到达v vi i的最短距离为：的最短距离为：第55页/共59页 当当k=2k=2时，从城市时，从城市v v1 1出发，经过出发，经过2 2个城镇到个城镇到达达v vi i的最短距离为：的最短距离为：所以所以所以所以所以所以第56页/共59页 当当k=3k=3时，从城市时，从城市v v1 1出发，经过出发，经过3 3个城镇到个城镇到达达v vi i的最短距离为：的最短距离为：所以所以第57页/共59页 逆推回去，货郎的最短路线是逆推回去，货郎的最短路线是l2431l2431最短距离为最短距离为2323。货郎担问题当城市数目增加时，用动态规货郎担问题当城市数目增加时，用动态规划方法求解，无论是计算量还是存贮量都会大大划方法求解，无论是计算量还是存贮量都会大大增加，所以本方法只适合于增加，所以本方法只适合于n n较小情况。较小情况。第58页/共59页感谢您的观看！第59页/共59页