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

第七章 动态规划 ;第四节 动态规划在经济管理中的应用 ;建立它的动态规划模型，其基本方程为：;（1） 令 ，把区间 [0，a]进行分割， 的大小可依据问题所要求的精度以及计算机的容量来定。 ; (2) 规定状态变量 及决策变量 只在离散点 上取值，相应的指标函数 就被定义在这些离散值上，于是递推方程就变为： ; 作为离散化例子，在例5中规定状态变量和决策变量只在给出的离散点上取值，见例6。 ;问如何分配投资数额才能使总效益最大?;例6 连续变量的离散化解法;解 令 ，将区间[0，10]分割成0，2，4，6，8，10六个点，即状态变量 集合为 ;式中 与 的集合均为： ;当k=2时， ;当k=1时， ;最大收益为 ，与例5结论完全相同。 ;一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重量限度为a kg，现有n种物品可供他选择装入背包，第i种物品的单件重量为ai kg，其价值是携带数量xi的函数ci(xi)(i=1,2,…,n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？ ;例1 有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？ ;当阶段k=3时，有;当阶段k=1时，有;二、生产经营问题;例2 生产与存贮问题 ;用动态规划方法求解时，对有关概念作如下分析：; k＝4，s5=s4+u4-g4=0，所以u4=g4-s4=4-s4，s4可取0，1，2，3。 ; k＝2，s3=s2+u2-g2，所以u2=s3+ g2-s2， s2可取0，1，2，3。 ;例3 采购与销售问题 ;解 按月份划分为4个阶段，k=l，2，3，4 状态变量 ：第k月初时仓库中的存货量(含上月订货)。 决策变量 ：第k月卖出的货物数量。 ：第k月订购的货物数量。 ;当k=4时 ;当k=3时 ;当k=2时 ;当k=1时 ;最优策略见下表。最大利润为16000。 ;例4 限期采购问题(随机型) ; 阶段k：可按采购期限(周)分为5段，k＝1，2，3，4，5。 状态变量 ：第k周的原料实际价格。 ;当k=5时 ;当k=4时 ;当k=3时 ;当k=2时 同理 ;当k=1时 ; 所以，最优采购策略为：若第一、二、三周原料价格为500，则立即采购，否则在以后的几周内再采购。若第四周价格为500或600，则立即采购，否则等第五周再采购。而第五周时无论当时价格为多少都必须采购。 按照以上策略进行采购，期望价格为： ;三、设备更新问题; 设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。 ;动态规划模型 阶段变量k：k=1,2,…,n，表示计划使用该设备的年限数。 ; 最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程： ;例5 设某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。（设 ） ;解 如前述建立动态规划模型，n=5 当k=5时， ;当k=4时， ;当k=3时， ;当k=2时， ;当k=1时， ; 上述计算递推回去，当 时，由状态转移方程， ; k＝5，s5可取1,2,3,4。 ; k＝3，s3可取1,2。 ; 货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这类问题。; 设 是已知的n个城镇，城镇 到城镇 的距离为 ，现求从 出发，经各城镇一次且仅一次返回 的最短路程。若对n个城镇进行排列，有 (n一1)!／2种方案，所以穷举法是不现实的，这里介绍一种动态规划方法。 货郎担问题也是求最短路径问题，但与例4的最短路问题有很大不同，建动态规划模型时，虽然也可按城镇数目n将问题分为n个阶段。但是状态变量不好选择，不容易满足无后效性。为保持状态间相互独立，可按以下方法建模：;