《管理运筹学第5章动态规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学第5章动态规划.ppt（30页珍藏版）》请在三一办公上搜索。
1、管理运筹学,主讲教师：马越峰,第五章 动态规划,5.1.动态规划的基本概念和最优化原理,5.2.动态规划模型的建立与求解,5.3.动态规划在经济管理中的应用,5.1.动态规划的基本概念和最优化原理,例1 最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；分析得知：从D1和D2到E的最短路径唯一。,第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2
2、，C3到D1，D2 的最短路径问题：分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：,第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：最后可以得到：从A到E的最短路径为A B4 C3 D1 E,一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。2、状
3、态sk：表示每个阶段开始所处的自然状况或客观条件。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。D3(C1)=D1,D2,基本概念、基本方程与最优化原理,s3=?,4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,6、阶段指标函数vk(sk,xk)：从状态sk出
4、发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1,xn)：从状态sk出发，选择决策xk,xk+1,xn所产生的过程指标。,二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标Vk,n的最优值，即,对于可加性指标函数，上式可以写为,终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。,三、最优化原理 作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任
5、意子策略都是最优的。,一、资源分配问题 例2:某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂,各工厂获得此设备后，预测可创造的利润如表所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？,5.2 动态规划模型的建立与求解,解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3)xk=分配给第k个设备台数。已知s1=5,并有 从与的定义，可知以下我们从第三阶段开始计算。,第三阶段:显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即 由于第3阶段是最后的阶段，故有
6、 其中可取值为0,1,2,3,4,5。其数值计算见表。,第二阶段：当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为,因为上式也可写成其数值计算如表所示。,第一阶段：把台设备分配给第1、第2、第3厂时，最大盈利为 其中 可取值0,1,2,3,4,5.数值计算见表 然后按计算表格的顺序推算，可知最优分配方案有两个：甲：0台 乙：2台 丙：3台甲：2台 乙：2台 丙：1台,背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的
7、价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,n），背包中物品的总价值为z，则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn0 且为整数。,5.3 动态规划的应用,例3:某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？,解：用动态规划来求解此题。我们把此问题分成四个阶段
8、，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知10并有,因为至多为10，其数值计算见表,第四阶段：,第三阶段：,第二阶段：,第一阶段：,最优解：,1.石油输送管道铺设最优方案的选择问题.下图中A为出 发点,E为目的地,B,C,D分别为三个必须建立油泵加压 站的地区,图中的线段表示管道可铺设的位置,线段旁 的数字为铺设管道线所需的费用.问如何铺设
9、管道才使 总费用最小.,练习.,B3,B1,B2,A,C1,C2,C3,D1,D2,E,3,5,4,6,3,5,3,2,4,4,1,5,2,5,7,4,5,4,3,4,2.某公司有资金400万元,向A,B,C三个项目追加投资,三个 项目可以有不同的投资额度,相应的效益值如下,问如何 分配资金,才使总效益最大.,3.某厂为扩大生产能力，拟订购某种成套设备46套,以 分配给所辖1,2,3三个分厂使用,预计各分厂分得不同套数的设备后每年创造的利润如下表.该厂应订购几套设备并如何分配,才能使每年预计创利润总额最大.,4.某厂生产三种产品,各种产品的重量与利润关系如下表所示.现将三种产品运往市场出售.运输能力总量不超过10吨.问如何安排运输使得总利润为最大.,
