数学建模动态规划ppt课件

西安电子科技大学,.,1,动态规划TrendsProgram/ProgrammingDynamic,唐厚俭hjTang,西安电子科技大学,.,2,目录,引例最短路问题动态规划基本概念、模型与方法例题1：载货问题/背包问题例题2：生产问题例题3：采购与库存例题4：加工顺序问题总结参考书目课后习题,西安电子科技大学,.,3,引例：求AG的最短线路,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,西安电子科技大学,.,4,用同一符号改写,P0,P11,P12,P21,P22,P23,P24,P31,P32,P33,P41,P42,P43,P51,P52,P6,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,a243=4,a322=1,西安电子科技大学,.,5,P0,P11,P12,P21,P22,P23,P24,P31,P32,P33,P41,P42,P43,P51,P52,P6,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,f52=3,f51=4,f41=min(3+f51,5+f52)=7,f42=min(5+f51,2+f52)=5,f43=min(6+f51,6+f52)=9,Pkj到终点的最小代价,西安电子科技大学,.,6,问题的解,P018,P1113,P1216,P2113,P2210,P239,P2412,P317,P326,P338,P417,P425,P439,P514,P523,P60,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,西安电子科技大学,.,7,动态规划的基本概念,阶段与阶段变量一个问题需要作出决策的步骤描述阶段的变量称为阶段变量，常用k表示状态与状态变量(Status)每个阶段都有一些特征，即状态第k阶段的状态变量用sk来表示决策与决策变量过程处于某一阶段时可以做出不同的决定用xk(sk)表示k阶段sk所做的决策在k阶段sk状态所有允许决策集合用Dk(sk)表示,西安电子科技大学,.,8,(Strategy,Policy),策略按顺序排列的决策组成的集合k子过程由第k阶段开始到终止状态的过程pk,n(sk)=xk(sk),xn(sn)k子过程策略k=1时为全过程策略,西安电子科技大学,.,9,状态转移函数(Transform),如果给定第k阶段状态变量sk和该阶段的决策变量xk(sk)，则k+1阶段的状态变量sk+1的值也随之确定，即sk+1随sk和xk(sk)的变化而变化，记：sk+1=Tk(sk,xk(sk)称为状态转移方程vk(sk,xk)=f(Tk(sk,xk(sk)为转移费用value,西安电子科技大学,.,10,指标函数(回收函数),用来衡量所实现过程优劣的一种数量指标它定义在全过程或所有后部子过程上的数量函数:,西安电子科技大学,.,11,最优值函数,optimalvaluefunction从第k阶段的状态sk开始到第n阶段的终止状态sn+1的过程,采用最优策略(optimalpolicy)所得到的指标函数称为最优值函数，记为fk(sk)(k=1,2,n),西安电子科技大学,.,12,P018,P1113,P1216,P2113,P2210,P239,P2412,P317,P326,P338,P417,P425,P439,P514,P523,P60,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,k=1,k=5,西安电子科技大学,.,13,动态规划基本条件,1)将问题转化为n个阶段2)正确选择状态变量sk,使它既能表达过程，又无后效性和可知性后效性：以后过程的发展不受以前各阶段的影响可知性：规定的各阶段状态变量的值是可知的3)确定决策变量xk及每一个阶段的允许决策集合4)写出状态转移方程：sk+1=Tk(sk,xk)5)正确写出指标函数Vk,n的关系Vk,n具有可分离性和递归关系函数是关于Vk+1,n的严格单调的,西安电子科技大学,.,14,动态规划的基本模型,逆序解法模型顺序解法模型,西安电子科技大学,.,15,逆序解法模型,指标函数形式,西安电子科技大学,.,16,西安电子科技大学,.,17,动态规划的求解方法,阶段1,阶段1,阶段1,西安电子科技大学,.,18,示例：用逆推法求解,西安电子科技大学,.,19,分析,将其看着三阶段的决策问题：有三个决策，且决策是连续函数，因此求最大值一般用到微分令,西安电子科技大学,.,20,西安电子科技大学,.,21,练习(正推),西安电子科技大学,.,22,动态规划应用案例分析,例1载货问题设有一辆载重为15t的卡车，要装运4种货物，已知4种货物的单位重量和价值如表所示，在载重许可的条件下每辆车载某种货物的条件不限，试问应如何搭配才能使装载的价值最大？,西安电子科技大学,.,23,设决策变量x1,x2,x3,x4分别为4种货物的转载件数，问题用线性整数规划：,西安电子科技大学,.,24,用动态规划方法,将其转化为四个阶段，各阶段标记的指标函数为状态变量:第k种至第4种货物允许载重重量允许的状态集合为最优值函数状态转移方程为允许决策集合为,西安电子科技大学,.,25,逆顺序法求解过程,1)k=42)k=33)k=24)k=1,西安电子科技大学,.,26,西安电子科技大学,.,27,程序源码,西安电子科技大学,.,28,讨论最大值,最大值点：sk=15时，值为22,012345678910111213141500000666661212121212180000566610111212151617180004568910121314161718200034679101213151618192122,西安电子科技大学,.,29,西安电子科技大学,.,30,背包问题,有人带背包上山，其可携带的物品容量限度为aml.设有n种物品可供他选择，设其编号为1,2,n,已知第i重物品单个容积为ciml，在他上山后的利润是携带数量xi的函数mi(xi)。试问此人应该如何选取携带物品所得的利润最大,西安电子科技大学,.,31,例题,西安电子科技大学,.,32,例2:生产问题,某工厂购进1000台机器，准备生产P1,P2两种产品。生产P1每台机器可收入50万，损坏率达65%；生产P2每台机器可收入40万，损坏率只有40%；估计3年后将有新的机器出现，旧的全部淘汰。试问：应如何安排生产，使3年内收入最多？计划以1年为周期。,生产,收入,损耗,P1,50,65%,P2,40,40%,剩余,35%,60%,西安电子科技大学,.,33,整数规划：设x1,x2,x3分别表示第1，2，3年生产P1的机器数量，y1,y2,y3表示生产P2的机器数量,西安电子科技大学,.,34,设fk(n)为n台机器在k年内的最大收益，若只安排一年的生产，x3为生产P1的机器数目k=1即1年后的最大收益k=2即2年后的最大收益,西安电子科技大学,.,35,最后考虑k=3即考虑3年的生产，第一年生产P1的机器数目设为x1，则,三年生产计划安排：第一年1000台机器一律生产P2第二年把余下的机器一律生产P2第三年把所有的机器改为生产P1总收入为82000万元，即8.2亿元,西安电子科技大学,.,36,例3：采购与库存安排,某公司需要制定一种产品今后四个时期的采购计划，根据市场预测在今后的四个时期内，该产品的需求量分别为2,3,2,4。如果每批产品的固定采购成本费为3万元，若不采购成本为0元；每单位产品的成本价为1万元；每个时期所允许的最大采购批量不超过6个单位；对于每个时期末没能售出的库存需要存储费0.5万元/单位。已知第一阶段和最后阶段末库存量均为0，试问公司应如何安排各个时期的采购和库存，才能在满足市场需要的前提下总的成本费最小。,西安电子科技大学,.,37,符号定义,k阶段xk采购量ck(xk)采购成本skk阶段末库存量hk(sk)库存成本fk(sk)第k阶段内的最小总成本,西安电子科技大学,.,38,西安电子科技大学,.,39,西安电子科技大学,.,40,西安电子科技大学,.,41,西安电子科技大学,.,42,例题4：加工排序问题,设有n个工件需要在机床A、B上加工，每个工件必须先经过A而后经过B的两道加工工序，以ai,bi分别表示工件i在A、B上的加工时间，问：应该如何在两机床上安排加工顺序使在机床A上加工第一个工件开始到机床B上将最后一个工件加工完为止所用的加工时间最少？,A,B,3,6,7,2,4,7,5,3,7,4,工件号,1,2,3,4,5,西安电子科技大学,.,43,变量定义,X：在机床A上等待加工一个排列x:不属于X的在A上最后加工完的工件t:A上加工完x的时刻算起到B上加工完x所需的时间f(X,t):由状态(X,t)出发，对未加工的工件采用“最优”加工顺序后，将X中所有工件加工完所需要的时间f(X,t,i):由状态(X,t)出发，在A上加工工件i，然后再对以后的加工工件采用“最优”顺序f(X,t,i,j):由状态(X,t)出发，在A上加工工件i，再加工j，然后再对以后的加工工件采用“最优”顺序,西安电子科技大学,.,44,西安电子科技大学,.,45,求解方法,西安电子科技大学,.,46,动态规划回顾,阶段与阶段变量(k)状态与状态变量(Sk)决策xk(sk)策略按顺序排列的决策组成的集合pk,n(sk)=xk(sk),xn(sn)k子过程策略状态转移函数sk+1=Tk(sk,xk(sk),西安电子科技大学,.,47,指标函数(回收函数),用来衡量所实现过程优劣的一种数量指标它定义在全过程或所有后部子过程上的数量函数:,西安电子科技大学,.,48,最优值函数,optimalvaluefunction从第k阶段的状态sk开始到第n阶段的终止状态sn+1的过程,采用最优策略(optimalpolicy)所得到的指标函数称为最优值函数，记为fk(sk)(k=1,2,n),西安电子科技大学,.,49,总结,使用动态规划的基本条件将问题转化为恰当的n个阶段正确选择状态变量sk,使之既能表达过程，又具有无后效性和可知性基本模型逆序解法（最短路问题、生产问题、载货问题）顺序解法（采购与库存计划）求解方法逐步写出各阶段的最优值递归函数,西安电子科技大学,.,50,动态规划与静态规划的关系,动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。,西安电子科技大学,.,51,动态规划的优点,能够得到全局最优解由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。可以得到一族最优解。动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解能够利用经验提高求解效率。,西安电子科技大学,.,52,动态规划的缺点,没有统一的标准模型也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则存在维数灾(curseofdimensionality)问题若一维状态变量有m个取值，那么对于n维问题，状态xk就有个mn值，对于每个状态值都要计算、存储函数fk(xk)，对于n稍大（即使n=3）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。,西安电子科技大学,.,53,作业1：复合系统工作可靠性问题,设某电子设备由三种组件D1,D2,D3组成，三种部件任一部件失灵，整个设备就不能正常工作，因此需要在需要的地方安装有随时可替换的备用件。已知三种组件的价格和可靠性指标如表所示，现要求在设计中所使用的费用不超过105万元，试问应如何设计备用件是该电子设备的可靠性最大？,组件,单价(万元),可靠性,D1,D2,D3,30,15,20,0.9,0.8,0.5,西安电子科技大学,.,54,作业2：项目资金分配问题,某建筑公司现有在建的A,B,C,D四个项目，按目前所赔给的人力、设备和材料，预计完成这四个项目分别需要15周、20周、18周和25周的时间，管理部门希望能够提前完成这些项目，为此决定追加35万元分配给这四个项目。这样为这四个项目分配追加的金额和能够完成任务的时间(周数)如表所示。试问：该公司应该如何将这35万资金分配给A,B,C,D四个项目，使得提前完成任务的总时间为最多。这里假设追加资金只能以5万元为一组分配。,西安电子科技大学,.,55,附表：追加资金与完成时间表,西安电子科技大学,.,56,最长公共子序列,LongestCommonSubsequence(LCS)给定两个序列x1.m和y1.n，找出它们的最长公共子序列,西安电子科技大学,.,57,最长上升子序列,LongestIncreaseSubsequence(LIS)给定一个序列，求它的一个递增子序列，使它的元素个数