运筹学动态规划.pptx

《运筹学动态规划.pptx》由会员分享，可在线阅读，更多相关《运筹学动态规划.pptx（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、最短路线问题最短路线问题：是指给定始点和终点，并且已知由始点到终点的各种可能的途径，需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离，也可以是运输的时间或运输费用等等。第1页/共79页例由A到D地要铺设一条煤气管道。其中须经过两级中间站，第一级中间站分别为B1和B2，第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道，没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度，试确定一条由A点到D点的铺设管道的最短路线。AB2B1C3C2C1D21233134341第2页/共79页符号和概念AB2B1C3C2C1D21233134341n：表

2、示由当前的状态到终点之间的阶段数。如由A点到D点n=3；由B2到D点n=2等等。n=3n=2n=1第3页/共79页符号和概念AB2B1C3C2C1D21233134341s：表示当前所处的位置，称为状态变量。如s可以是A、B1、B2、C1、C2等等。第4页/共79页符号和概念AB2B1C3C2C1D21233134341Xn(s)：称为决策变量，它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态，决策者做出的一种选择。如，X2(B1)表示已处于B1状态，还有2个阶段就到达D点了，此时决策者可选择的地点；X2(B1)可取C1,C2或C3。第5页/共79页符号和概念AB2B1C3C2C1D2

3、1233134341fn(s)：表示由阶段数为n的某个状态s至终点的最短距离。例如，f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离，即B1到D点的最短距离。显然本例就是要求f3(A)及f3(A)所确定的最短路线。第6页/共79页符号和概念AB2B1C3C2C1D21233134341d(s，Xn(s)：表示当前处于状态s时，选取决策变量Xn(s)后，由点s到点Xn(s)的距离。例如，d(B1，C3)=1，d(C2，D)=3 第7页/共79页分析要求出f3(A)的值及相应的策略从起点A开始分析 AB2B1C3C2C1D21233134341第8页/共79页当处于状态A时，有几种可

4、供选择的路线 AB2B1C3C2C1D21233134341第9页/共79页当处于状态A时，有两种可供选择的路线AB1：表明由A点所选择的下一点是B1由B1状态到终点D的最短距离为f2(B1)若选此条路线，则由A出发到达终点的最短距离可表示为 d(A,B1)+f2(B1)AB2：表明由A点所选择的下一点是B2由B2状态到终点D的最短距离为f2(B2)若选此条路线，则由A出发到达终点的最短距离可表示为 d(A,B2)+f2(B2)第10页/共79页综合考虑两种情况可知，由状态A出发，到终点D的最优路线应是上述两种最短距离中的最小值，即 可见，要计算f3(A)就得先计算f2(B1)和f2(B2)。

5、第11页/共79页由B1、B2点出发分别有几种可供选择的路线？AB2B1C3C2C1D21233134341第12页/共79页由B1点出发有三种可供选择的路线 B1C1最短距离为 d(B1,C1)+f1(C1)B1C2最短距离为 d(B1,C2)+f1(C2)B1C3最短距离为 d(B1,C3)+f1(C3)第13页/共79页综合考虑三种情况可知，由状态B1出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B1)就得先计算和f1(C1)、f1(C2)、f1(C3)。第14页/共79页由B2点出发有三种可供选择的路线 B2C1最短距离为 d(B2,C1)+f1(C1)B

6、2C2最短距离为 d(B2,C2)+f1(C2)B2C3最短距离为 d(B2,C3)+f1(C3)第15页/共79页综合考虑三种情况可知，由状态B2出发，到终点D的最优路线应是上述三种最短距离中的最小值，即可见，要计算f2(B2)就得先计算和f1(C1)、f1(C2)、f1(C3)。第16页/共79页由于由状态C1、C2、C3出发到达终点D只需经过一个阶段，所以 第17页/共79页由以上分析可以看出，计算f3(A)的过程实际是一个倒推的过程，即由最后的阶段向前逐级进行计算。AB2B1C3C2C1D21233134341第18页/共79页当n=1时 第19页/共79页图示AB2B1C3C2C1D

7、21233134341第20页/共79页当n=2时 第21页/共79页图示AB2B1C3C2C1D21233134341第22页/共79页当n=3时 第23页/共79页图示AB2B1C3C2C1D21233134341所以，铺设管道的最短路线应是AB1C1D。第24页/共79页总结对于最短路线问题，一般地有如下的递推关系式：这个递推公式是根据最优化原理得到的 第25页/共79页最优化原理一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，其今后诸决策对第一个决策所形成的状态作为初始状态和过程而言，必须构成最优策略。第26页/共79页二、动态规划的应用第27页/共79页1、“背包”

8、问题/最优装载问题假设有一个徒步旅行者，它所能承受的旅行背包的总重量式A公斤，今有n种旅行物品供它选择装入背包中，已知，aj：第j种物品的单位重量（公斤）cj：第j种物品的单位使用价值（表明给该旅行者所带来的好处的一种数量指标）我们的问题是：如何确定这n种物品的数量x1、x2、xn，使得该旅行者的背包重量不超过A公斤，而且对旅行者来说总的使用价值最大？第28页/共79页例假设有以下“背包”问题（总重量不超过5）物品编号 123单位重量aj325每件使用价值量cj8512物品件数xjx1x2x3第29页/共79页数学模型第30页/共79页思路分析给待装物品编号：1、2、n分n步装载物品。为与阶段

9、数同一，假设从编号为n的物品开始倒序装载。即先装第n号物品，再装n-1号物品，最后装1号物品。如本例，先装3号物品，再装2号物品，最后装1号物品。第31页/共79页思路分析当装n号物品时，若决定装xn件，xn 应满足以下条件（xn为决策变量、A为总重量限制）第32页/共79页递推公式n种物品的最大价值量=第n种物品的价值量+剩余n-1种物品的最大价值量即：第33页/共79页状态变量的确定“背包”只有一个约束条件：重量限制。装载阶段不同，“背包”剩余的重量限制会发生变化。因此可确定“重量限制”为状态变量。公式可写成 （n2时）第34页/共79页当n=1时第35页/共79页求解例题用递推关系式计算

10、：我们的问题是求f3(5)第36页/共79页可见要计算f3(5),要先计算f2(5)、f2(0)第37页/共79页可见，要计算f2(5)、f2(0)，要先计算f1(5)、f1(3)、f1(1)、f1(0)第38页/共79页将f1值代入f2中，得到 第39页/共79页将f2值代入f3中，得到“背包”问题的最优解为 X1=1,X2=1,X3=0,最优值为13。第40页/共79页2、投资分配问题/资源分配问题资源分配问题：设有某种资源（如电力、煤炭等），可用于n种生产，假设资源的总数量为A，用于第j种生产的资源数量为xj时，可以得到收益gj(xj),j=1,2,n，问：对资源A应如何进行分配，使得总

11、的收益最大？投资分配问题：设有总数为A的资金，要分配给n个项目（或工厂、部门等），用于扩大再生产（或其他建设），假设xj：表示分配给第j个项目的资金数；gj(xj):表示第j个项目得到数量为xj的资金后，所提供的利润值；问：如何确定各项目的资金数，使得总的投资利润最大？第41页/共79页分析不妨假设，分n个阶段考虑分配给n个项目的资金，因为每个阶段的决策不仅影响到该项目得到的资金多少，同时也会影响到今后其他项目所可能得到的资金数（资金总数A已确定），所以可以用动态规划方法来求解，令：fk(x):数量为x的资金分配给前k个项目所得到的最大利润值；xk：分配给第k个项目的资金数，满足条件：0 xk

12、x显然，我们的目标是求fn(A)第42页/共79页分析当n=1时，f1(x)表示将数量为x的资金分配给一个项目的最大利润，因为只有一个项目，所以f1(x)=g1(x)当n=k2时，gk(xk)表示分配给第k个项目资金数为xk时的利润值；(x-xk)表示分配给前k个项目资金数为x，则分配给前k-1个项目的资金数为x-xk；fk-1(x-xk)表示以数量为x-xk的资金分配给k-1个项目所得到的最大利润值。第43页/共79页例：股东投资30万元给三个工厂进行工厂扩建，每个工厂扩建后的利润与投资额的大小有关，投资后的利润值如下表：问：应如何分配这30万元使得这四个工厂扩建后总利润最大？投资x利润01

13、02030g1(x)0205065g2(x)0204050g3(x)0256075第44页/共79页解要计算f3(30)，要先计算f2(30)，f2(20)，f2(10)，f2(0)第45页/共79页第46页/共79页要计算f2(30)，f2(20)，f2(10)，f2(0)，要先计算f1(30)，f1(20)，f1(10)，f1(0)第47页/共79页将以上结果代入前面各式 第48页/共79页第49页/共79页第50页/共79页第51页/共79页得最优解为 最优值为80 第52页/共79页3、多阶段生产安排问题 /多阶段配置问题设有某种原料，其数量为A吨，用于生产两种不同类型的产品，记为类型

14、、类型，已知投入该原料进行生产后，还可以回收部分原料用于下一阶段的再生产，假设g1(a)：投入数量为a的原料，生产型产品的收益值；g2(a)：投入数量为a的原料，生产型产品的收益值；r1(a)：生产型产品的回收率（0r11）；r2(a)：生产型产品的回收率（0r21）我们的目标是，对于总数为A的原料进行n个阶段生产，每个阶段应如何分配原料用于生产型产品及型产品，使得经过n个阶段生产之后总收益最大？第53页/共79页分析由于问题本身就是多阶段的，所以可以用动态规划方法求解，令：fk(a)：初始原料数量为a，进行k个阶段的生产，采取最优分配策略所获得的最大收益；x：进行k个阶段的生产时，在生产的第

15、一个阶段用于生产型产品的原料数量（0 xa）。在进行某阶段生产时，当前阶段的收益为 第54页/共79页分析该阶段生产之后，总的回收原料的数量为 它是在以后将要进行的k-1个阶段生产的状态变量的值，这些原料用于k-1个阶段生产，采取最优分配策略所获得的最大收益为第55页/共79页分析根据动态规划的最优化原理，当2kn时，有 当k=1时（即只进行一个阶段生产），有 显然，我们的目标是计算fn(A)第56页/共79页例在多阶段生产安排问题中，设收益函数分别为回收率分别为生产阶段数为n=3，现有原料为A=100吨。第57页/共79页解：先整理一些算式 第58页/共79页当k=1时 对于一个阶段生产问题

16、，最大收益为，最佳生产安排是：全部原料用于生产型产品；第59页/共79页当k=2时 可知，当进行两个阶段生产时，最大收益为最佳生产安排是：全部原料用于生产型产品；第60页/共79页当k=3时 可知，当进行三个阶段生产时，最大收益为最佳生产安排是：全部原料用于生产型产品；第61页/共79页将已知数据代入上式得 即投入100吨原料进行三阶段生产时，可获得的最大收益为万元。此时，最佳生产安排是：第一阶段（k=3）全部原料用于生产型产品；第二阶段（k=2）全部原料用于生产型产品；第三阶段（k=1）全部原料用于生产型产品；第62页/共79页第一阶段：把全部原料100吨投入型产品生产 收益=0.5*100

17、=50万元，回收=0.4*100=40吨第二阶段：把全部原料40吨投入型产品生产 收益=0.5*40=20万元，回收=0.4*40=16吨第三阶段：把全部原料16吨投入型产品生产 收益万元，回收吨 三个阶段总收益为：万元 每个阶段生产安排第63页/共79页4、多阶段存储问题 把一年（或一段时间）分为n个周期（也称阶段），已知仓库的最大容量为w，第i个周期的需求量为ri，单位产品的购进费为ai，单位产品的周期保管费为bi。问：各个周期应订多少货，才能够既满足需求，又使n个周期总存储费最小。假设：1、各个周期的订货在该周期末才能存储，而各周期的需求应在该周期初给予满足，而且不允许缺货。2、第一个周

18、期的初始存储量z1为已知，第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。第64页/共79页例某个居民区每年四个季度对煤的需求量、该区煤场各个季度购进煤的单价和存储煤的保管费用都列于下表。已知煤场的最大容量为9百吨，每年年底都要求有8百吨煤的存储，现在问，煤场应如何安排各个季度的进煤量，才最合理。假设：1、各个周期的订货在该周期末才能存储，而各周期的需求应在该周期初给予满足，而且不允许缺货。2、第一个周期的初始存储量z1为已知，第n个周期的期末存储量zn+1也为已知。3、期初存储量不低于本期需求量。单位第一季度第二季度第三季度第四季度需求量 ri每百吨购买价 ai每百吨

19、保管费 bi百吨千元千元840.5520.7530.763.50.6第65页/共79页分析存储问题的周期数n为一定数，故定购费在一年内也是一个常数；又因为不允许短缺，所以可以不考虑定购费与短缺费。这样，总存储费就等于购进费与保管费之和。设第i个周期的初始存储量为zi，订货量为qi（i1,2,n），由假设知，有如下关系式成立：第66页/共79页分析令fk(z)=初始存储量为z，还有k个周期，采取最优策略时的最低总存储费。显然，我们的目标是求fn(z1)。如果设第i个周期的初始存储量为z，进货量为q，由公式（1）（2）可知 第67页/共79页分析再结合公式（3）知令得当i=n时，有 即 第68页/共79页分析由“最优化原理”可得递推公式：第69页/共79页解这是一个四阶段的存储问题，且z1=z5=8，w=9，由递推公式，得其中第70页/共79页由表可知 从而知 第71页/共79页第72页/共79页第73页/共79页第74页/共79页第75页/共79页第76页/共79页这样，得到煤场每年各季度的购煤量和季初存储量的最优安排如下表，全年总存储费为80400元。第一季度第二季度第三季度第四季度购煤量季初存储量58952986第77页/共79页思考题与练习题第78页/共79页感谢您的观看！第79页/共79页