运筹学74动态规划应用举例ppt课件.ppt

1、第七章 动态规划,多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 动态规划在经济管理中的应用,第四节 动态规划在经济管理中的应用,连续变量的离散化解法 先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：,模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量 状态转移方程、基本方程、指标函数、最优指标函数,建立它的动态规划模型，其基本方程为：,其状态转移方程为:,由于 与 都是连续变量，当各阶段指标 没有特殊性而较为复杂时， 要求出 会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如

2、下：,（1） 令 ，把区间 0，a进行分割， 的大小可依据问题所要求的精度以及计算机的容量来定。,(2) 规定状态变量 及决策变量 只在离散点 上取值，相应的指标函数 就被定义在这些离散值上，于是递推方程就变为：,其中,作为离散化例子，在例5中规定状态变量和决策变量只在给出的离散点上取值，见例6。,（3）按逆序方法，逐步递推求出 ，最后求出最优资金分配方案。,问如何分配投资数额才能使总效益最大?,例5 某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其效益分别为：,例6 连续变量的离散化解法,解 令 ，将区间0，10分割成0，2，4，6，8，10六个点，即状态变量 集合

3、为,允许决策集合为 ， 与 均在分割点上取值。,动态规划基本方程为：,当k=3时，,式中 与 的集合均为：,计算结果见表7-1。,当k=3时，,表7-1,当k=2时，,计算结果见表7-2。,表7-2,当k=1时，,计算结果见表7-3。,表7-3,最大收益为 ，与例5结论完全相同。,计算结果表明，最优决策为：,应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。,一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a kg，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai kg，其价值是携带数量xi的函数ci(xi)(i=1,2,n)，问旅行者应如何选择携带

4、各种物品的件数，以使总价值最大？,例1 有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？,逆序解法： 阶段k： k=1,2,3 状态变量sk:第k阶段可以装载第k种到第3种货物的重量。 决策变量xk:决定装载第k种货物的数量。 状态转移方程:sk+1=sk-akxk 最优指标函数fk(sk):当可装载重量为sk,装载第k种到第3种货物所获得的最大价值。 基本方程：,当阶段k=3时，有,当阶段k=2时，有,当阶段k=1时，有,二、生产经营问题,在生产和经营管理中，经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计

5、划，使总效益最高的问题。下面通过例子来说明对不同特点问题的不同处理技巧。,例2 生产与存贮问题,某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产j单位产品费用为：,每月库存j单位产品的费用为 ，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。,用动态规划方法求解时，对有关概念作如下分析：,(1) 阶段：每个月为一个阶段，k1，2，3，4。,(2)状态变量： 为第k个月初的库存

6、量。,(3)决策变量： 为第k个月的生产量。,(4)状态转移方程：,(5)最优指标函数： 表示第k月状态为 时，采取最佳策略生产，从本月到计划结束(第4月末)的生产与存贮最低费用。 （6）基本方程：,k4，s5=s4+u4-g4=0，所以u4=g4-s4=4-s4，s4可取0，1，2，3。,k3，s4=s3+u3-g3，所以u3=s4+ g3-s3，s3可取0，1，2，3。,k2，s3=s2+u2-g2，所以u2=s3+ g2-s2， s2可取0，1，2，3。,k1，s2=s1+u1-g1，所以u1=s2+ g1-s1， s1可取0。,反推回去， u1*=2， u2*=5， u3*=0， u4

7、*=4。,例3 采购与销售问题,某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商品l000单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表7_12所示，假定商店在1月开始经销时，仓库贮有该商品500单位。试问若不计库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大。,解 按月份划分为4个阶段，k=l，2，3，4 状态变量 ：第k月初时仓库中的存货量(含上月订货)。 决策变量 ：第k月卖出的货物数量。 ：第k月订购的货物数量。,状态转移方程：,最优指标函数 ：第k月初存货量为

8、 时，从第k月到4月末所获最大利润。 则有逆序递推关系式为：,当k=4时,显然，决策应取 时才有最大值,当k=3时,这个阶段需解一个线性规划问题：,因为只有两个变量x3, y3 ，可以用图解法，也可以用单纯形法，求解得到： 时有最大值,当k=2时,求解线性规划问题：,得,当k=1时,求解一个线性规划问题：,得, ,最优策略见下表。最大利润为16000。,期前存货,例4 限期采购问题(随机型),某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如表7-14所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。,表7-14,阶段k：可

9、按采购期限(周)分为5段，k1，2，3，4，5。 状态变量 ：第k周的原料实际价格。,决策变量 ：第k周如采购 则 1，若不采购 则 =0。 另外用 表示：当第k周决定等待，而在以后采购时的采购价格期望值。 最优指标函数 ：第k周实际价格为 时，从第k周至第5周采取最优策略所花费的最低期望价格。 则有逆序递推关系式为：,解 本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的概率分布取值，即属于随机型动态规划问题。,为状态集合500，600，700。,当k=5时,因为若前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以,当k=4时,由于,所以,当k=3时,由于,所以

10、,当k=2时 同理,当k=1时,所以，最优采购策略为：若第一、二、三周原料价格为500，则立即采购，否则在以后的几周内再采购。若第四周价格为500或600，则立即采购，否则等第五周再采购。而第五周时无论当时价格为多少都必须采购。 按照以上策略进行采购，期望价格为：,三、设备更新问题,从经济上分析，一台设备应该 使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多,维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费，为了比较不同决策的优劣，常常要在一个较长

11、的时间内考虑更新决策问题。,设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。,rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。 uk(t) ：在第k年设备役龄为t年，再使用一年的维修费用。 ck(t) ：在第k年卖掉台役龄为t年的设备，买进一台新设备的更新净费用。 为折扣因子(01) ，表示一年以后的单位收入价值相当于现年的单位。,动态规划模型 阶段变量k：k=1,2,n，表示计划使用该设备的年限数。,状态变量sk: 第k年初

12、，设备已使用过的年数，即役龄。 决策变量xk: 是第k年初更新（Replacement），还是保留使用（keep）旧设备，分别用R与K表示。 状态转移方程为：,阶段指标为：,指标函数为：,最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程：,实际上，,例5 设某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。（设 ）,解 如前述建立动态规划模型，n=5 当k=5时，,状态变量s5可取1，2，3，4。,=2.5,=2,=1.5,当k=4时，,状态变量s4可取1，2，3。,=,=

13、6.5,=,= 5.8,=,= 5.5,当k=3时，,状态变量s3可取1，2。,=,= 9.5,=,= 8.8,当k=2时，,状态变量s2只能取1,=,= 12.5,当k=1时，,状态变量s1只能取0,= 17,上述计算递推回去，当 时，由状态转移方程，,则,则查 得：,状态 ，查：,推出 ，查,最优策略为： ，即第一年初购买的设备到第二、三、四年初各更新一次，用到第5年末，其总效益为17万元。,k5，s5可取1,2,3,4。,k4, s4可取1,2,3。,k3，s3可取1,2。,k2, s2可取1。,k1, s2可取0。,货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅一

14、次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这类问题。,四、货郎担问题,设 是已知的n个城镇，城镇 到城镇 的距离为 ，现求从 出发，经各城镇一次且仅一次返回 的最短路程。若对n个城镇进行排列，有 (n一1)!2种方案，所以穷举法是不现实的，这里介绍一种动态规划方法。 货郎担问题也是求最短路径问题，但与例4的最短路问题有很大不同，建动态规划模型时，虽然也可按城镇数目n将问题分为n个阶段。但是状态变量不好选择，不容易满足无后效性。为保持状态间相互独立，可按以下方法建模：,设S表示从 到 中间所有可能经过的城市集合，S实际上是包含除 与 两个点之外其余点的集合，但S中的点的个数要随阶段数改变。 状态变量 表示：从 点出发经过S集合中所有点一次最后到达 。 最优指标函数 为从 出发经由k个城镇的S集合到Vi的最短距离。,决策变量 表示：从 经k个中间城镇的S集合到 城镇的最短路线上邻接 的前一个城镇，则动态规划的顺序递推关系为：,例6 已知4个城市间距离如表716，求从v1出发，经其余城市一次