运筹学动态规划.ppt

(79页)

'运筹学动态规划.ppt'

《运筹学动态规划.ppt》由会员分享,提供在线免费全文阅读可下载,此文档格式为ppt,更多相关《运筹学动态规划.ppt》文档请在天天文库搜索。

1、第八章 动态规划多阶段决策过程:是指这样一类决策过程,它可以按时间分为若干阶段(称为时段),每一个阶段都需要做出决策,以便在过程的最终阶段得到最优结局。动态规划的一个重要特点是利用所谓的“最优化原理”,将问题用函数方程来表示(即递推方程),然后利用方程递推地进行计算、求解。一、最短路线问题最短路线问题:是指给定始点和终点,并且已知由始点到终点的各种可能的途径,需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离,也可以是运输的时间或运输费用等等。例由A到D地要铺设一条煤气管道。其中须经过两级中间站,第一级中间站分别为B1和B2,第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道,没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度,试确定一条由A点到D点的铺设管道的最短路线。AB2B1C3C2C1D21233134341符号和概念AB2B1。

2、C3C2C1D21233134341n:表示由当前的状态到终点之间的阶段数。如由A点到D点n=3;由B2到D点n=2等等。n=3n=2n=1符号和概念AB2B1C3C2C1D21233134341s:表示当前所处的位置,称为状态变量。如s可以是A、B1、B2、C1、C2等等。符号和概念AB2B1C3C2C1D21233134341Xn(s):称为决策变量,它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态,决策者做出的一种选择。如,X2(B1)表示已处于B1状态,还有2个阶段就到达D点了,此时决策者可选择的地点;X2(B1)可取C1,C2或C3。符号和概念AB2B1C3C2C1D21233134341fn(s):表示由阶段数为n的某个状态s至终点的最短距离。例如,f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离,即B1到D点的最短距离。显然本例就是要求f3(A)及f3(。

3、A)所确定的最短路线。符号和概念AB2B1C3C2C1D21233134341d(s,Xn(s)):表示当前处于状态s时,选取决策变量Xn(s)后,由点s到点Xn(s)的距离。例如,d(B1,C3)=1,d(C2,D)=3 分析要求出f3(A)的值及相应的策略从起点A开始分析 AB2B1C3C2C1D21233134341当处于状态A时, 有几种可供选择的路线 AB2B1C3C2C1D21233134341当处于状态A时, 有两种可供选择的路线①A→B1:表明由A点所选择的下一点是B1由B1状态到终点D的最短距离为f2(B1)∴若选此条路线,则由A出发到达终点的最短距离可表示为 d(A,B1)+ f2(B1)②A→B2:表明由A点所选择的下一点是B2由B2状态到终点D的最短距离为f2(B2)∴若选此条路线,则由A出发到达终点的最短距离可表示为 d(A,B2)+ f2(B2)综合考虑两种情况。

4、可知,由状态A出发,到终点D的最优路线应是上述两种最短距离中的最小值,即 可见,要计算f3(A)就得先计算f2(B1)和f2(B2)。 由B1、B2点出发 分别有几种可供选择的路线? AB2B1C3C2C1D21233134341由B1点出发 有三种可供选择的路线 ①B1→C1最短距离为 d(B1,C1)+ f1(C1)②B1→C2最短距离为 d(B1,C2)+ f1(C2)③B1→C3最短距离为 d(B1,C3)+ f1(C3)综合考虑三种情况可知,由状态B1出发,到终点D的最优路线应是上述三种最短距离中的最小值,即可见,要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。 由B2点出发 有三种可供选择的路线 ①B2→C1最短距离为 d(B2,C1)+ f1(C1)②B2→C2最短距离为 d(B2,C2)+ f1(C2)③B2→C3最短距离为 d(B2,C3)+ f1。

5、(C3)综合考虑三种情况可知,由状态B2出发,到终点D的最优路线应是上述三种最短距离中的最小值,即可见,要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。 由于由状态C1、C2、C3出发到达终点D只需经过一个阶段,所以 由以上分析可以看出,计算f3(A)的过程实际是一个倒推的过程,即由最后的阶段向前逐级进行计算。AB2B1C3C2C1D21233134341当n=1时 图示AB2B1C3C2C1D21233134341当n=2时 图示AB2B1C3C2C1D21233134341当n=3时 图示AB2B1C3C2C1D21233134341所以,铺设管道的最短路线应是A→B1→C1→D。 总结对于最短路线问题,一般地有如下的递推关系式: 这个递推公式是根据最优化原理得到的 最优化原理一个过程的最优策略具有这样的性质,即无论其初始状态和初始决策如何,其今后诸决策对第一个。

6、决策所形成的状态作为初始状态和过程而言,必须构成最优策略。 二、动态规划的应用1、“背包”问题/最优装载问题假设有一个徒步旅行者,它所能承受的旅行背包的总重量式A公斤,今有n种旅行物品供它选择装入背包中,已知,aj:第j种物品的单位重量(公斤)cj:第j种物品的单位使用价值(表明给该旅行者所带来的好处的一种数量指标)我们的问题是:如何确定这n种物品的数量x1、x2、…、xn,使得该旅行者的背包重量不超过A公斤,而且对旅行者来说总的使用价值最大? 例假设有以下“背包”问题 (总重量不超过5)物品编号 123单位重量aj325每件使用价值量cj8512物品件数xjx1x2x3数学模型思路分析给待装物品编号:1、2、……、n分n步装载物品。为与阶段数同一,假设从编号为n的物品开始倒序装载。即先装第n号物品,再装n-1号物品,……,最后装1号物品。如本例,先装3号物品,再装2号物品,最后装1号物品。

7、。思路分析当装n号物品时,若决定装xn件, xn 应满足以下条件( xn为决策变量、A为总重量限制)递推公式n种物品的最大价值量= 第n种物品的价值量 + 剩余n-1种物品的最大价值量即:状态变量的确定“背包”只有一个约束条件:重量限制。装载阶段不同,“背包”剩余的重量限制会发生变化。因此可确定“重量限制”为状态变量。公式可写成 (n≥2时)当n=1时求解例题用递推关系式计算:我们的问题是求f3(5) 可见要计算f3(5),要先计算f2(5)、f2(0)可见,要计算f2(5)、f2(0) ,要先计算f1(5)、f1(3)、 f1(1)、f1(0)将f1值代入f2中,得到 将f2值代入f3中,得到∴“背包”问题的最优解为 X1=1, X2=1, X3=0, 最优值为13。 2、投资分配问题/资源分配问题资源分配问题:设有某种资源(如电力、煤炭等),可用于n种生产,假设资源的总数量为A,用于第。

8、j种生产的资源数量为xj时,可以得到收益gj(xj),j=1,2,…,n,问:对资源A应如何进行分配,使得总的收益最大?投资分配问题:设有总数为A的资金,要分配给n个项目(或工厂、部门等),用于扩大再生产(或其他建设),假设xj:表示分配给第j个项目的资金数;gj(xj):表示第j个项目得到数量为xj的资金后,所提供的利润值;问:如何确定各项目的资金数,使得总的投资利润最大? 分析不妨假设,分n个阶段考虑分配给n个项目的资金,因为每个阶段的决策不仅影响到该项目得到的资金多少,同时也会影响到今后其他项目所可能得到的资金数(资金总数A已确定),所以可以用动态规划方法来求解,令:fk(x):数量为x的资金分配给前k个项目所得到的最大利润值;xk:分配给第k个项目的资金数,满足条件:0≤xk≤x显然,我们的目标是求fn(A) 分析当n=1时,f1(x)表示将数量为x的资金分配给一个项目的最大利润,。

9、因为只有一个项目,所以f1(x)=g1(x)当n=k≥2时,gk(xk)表示分配给第k个项目资金数为xk时的利润值;(x-xk)表示分配给前k个项目资金数为x,则分配给前k-1个项目的资金数为x-xk;fk-1(x-xk)表示以数量为x-xk的资金分配给k-1个项目所得到的最大利润值。例:股东投资30万元给三个工厂进行工厂扩建,每个工厂扩建后的利润与投资额的大小有关,投资后的利润值如下表:问:应如何分配这30万元使得这四个工厂扩建后总利润最大? 投资x利润0102030g1(x)0205065g2(x)0204050g3(x)0256075解∴要计算f3(30), 要先计算f2(30),f2(20),f2(10),f2(0)∴要计算f2(30),f2(20),f2(10),f2(0), 要先计算f1(30),f1(20),f1(10),f1(0) 将以上结果代入前面各式 得最优解为 最优值。

10、为80 3、多阶段生产安排问题 /多阶段配置问题设有某种原料,其数量为A吨,用于生产两种不同类型的产品,记为类型Ⅰ、类型Ⅱ,已知投入该原料进行生产后,还可以回收部分原料用于下一阶段的再生产,假设g1(a):投入数量为a的原料,生产Ⅰ型产品的收益值;g2(a) :投入数量为a的原料,生产Ⅱ型产品的收益值; r1(a):生产Ⅰ型产品的回收率(0≤r1≤1);r2(a):生产Ⅱ型产品的回收率(0≤r2≤1)我们的目标是,对于总数为A的原料进行n个阶段生产,每个阶段应如何分配原料用于生产Ⅰ型产品及Ⅱ型产品,使得经过n个阶段生产之后总收益最大? 分析由于问题本身就是多阶段的,所以可以用动态规划方法求解,令:fk(a):初始原料数量为a,进行k个阶段的生产,采取最优分配策略所获得的最大收益;x:进行k个阶段的生产时,在生产的第一个阶段用于生产Ⅰ型产品的原料数量(0≤x≤a)。在进行某阶段生产时,当前阶。

11、段的收益为 分析该阶段生产之后,总的回收原料的数量为 它是在以后将要进行的k-1个阶段生产的状态变量的值,这些原料用于k-1个阶段生产,采取最优分配策略所获得的最大收益为分析根据动态规划的最优化原理,当2≤k≤n时,有 当k=1时(即只进行一个阶段生产),有 显然,我们的目标是计算fn(A)例在多阶段生产安排问题中,设收益函数分别为回收率分别为生产阶段数为n=3,现有原料为A=100吨。解:先整理一些算式 当k=1时 ∴对于一个阶段生产问题,最大收益为0.6a,最佳生产安排是:全部原料用于生产Ⅰ型产品; 当k=2时 ∴可知,当进行两个阶段生产时,最大收益为0.74a最佳生产安排是:全部原料用于生产Ⅱ型产品;当k=3时 ∴可知,当进行三个阶段生产时,最大收益为0.796a最佳生产安排是:全部原料用于生产Ⅱ型产品; 将已知数据代入上式得 即投入100吨原料进行三阶段生产时,可获得的最大收益为7。

12、9.6万元。此时,最佳生产安排是:第一阶段(k=3)全部原料用于生产Ⅱ型产品;第二阶段(k=2)全部原料用于生产Ⅱ型产品;第三阶段(k=1)全部原料用于生产Ⅰ型产品; 第一阶段:把全部原料100吨投入Ⅱ型产品生产 收益=0.5*100=50万元,回收=0.4*100=40吨第二阶段:把全部原料40吨投入Ⅱ型产品生产 收益=0.5*40=20万元,回收=0.4*40=16吨第三阶段:把全部原料16吨投入Ⅰ型产品生产 收益=0.6*16=9.6万元,回收=0.1*16=1.6吨 ∴三个阶段总收益为:50+20+9.6=79.6万元 每个阶段生产安排4、多阶段存储问题 把一年(或一段时间)分为n个周期(也称阶段),已知仓库的最大容量为w,第i个周期的需求量为ri,单位产品的购进费为ai,单位产品的周期保管费为bi。问:各个周期应订多少货,才能够既满足需求,又使n个周期总存储费最小。假设:1、各个。

13、周期的订货在该周期末才能存储,而各周期的需求应在该周期初给予满足,而且不允许缺货。2、第一个周期的初始存储量z1为已知,第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。 例某个居民区每年四个季度对煤的需求量、该区煤场各个季度购进煤的单价和存储煤的保管费用都列于下表。已知煤场的最大容量为9百吨,每年年底都要求有8百吨煤的存储,现在问,煤场应如何安排各个季度的进煤量,才最合理。假设:1、各个周期的订货在该周期末才能存储,而各周期的需求应在该周期初给予满足,而且不允许缺货。2、第一个周期的初始存储量z1为已知,第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。单位第一季度第二季度第三季度第四季度需求量 ri每百吨购买价 ai每百吨保管费 bi百吨千元千元840.5520.7530.763.50.6分析存储问题的周期数n为一定数,故定购费在一年内也是一个常数;又因为不允许短缺,所以可以不考虑定购费与短缺费。这样,总存储费就等于购进费与保管费之和。设第i个周期的初始存储量为zi,订货量为qi(i=1,2,…,n),由假设知,有如下关系式成立: 分析令fk(z)=初始存储量为z,还有k个周期,采取最优策略时的最低总存储费。显然,我们的目标是求fn(z1)。如果设第i个周期的初始存储量为z,进货量为q,由公式(1)(2)可知 分析再结合公式(3)知令得当i=n时,有 即 分析由“最优化原理”可得递推公式: 解这是一个四阶段的存储问题,且z1=z5=8,w=9,由递推公式,得其中由表可知 从而知 这样,得到煤场每年各季度的购煤量和季初存储量的最优安排如下表,全年总存储费为80400元。 第一季度第二季度第三季度第四季度购煤量季初存储量58952986思考题与练习题。

关 键 词:
运筹学 动态规划
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:运筹学动态规划.ppt
链接地址: https://www.wenku365.com/s-58383709.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开