一般数学模型的动态规划解法.pptx

安徽科技学院安徽科技学院 运筹与优化运筹与优化例例1 某公司有资金某公司有资金10万元，若投资于项目万元，若投资于项目i(i=1,2,3)的投的投资额为资额为xi时，其收益分别为时，其收益分别为g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资数额才能使总收益最大？问应如何分配投资数额才能使总收益最大？一、非线性规划问题的动态规划解法一、非线性规划问题的动态规划解法 解解 静态规划模型：静态规划模型：第四节第四节 一般数学模型的动态规划解法一般数学模型的动态规划解法1.连续变量的一般解法连续变量的一般解法 安徽科技学院安徽科技学院 运筹与优化运筹与优化为了应用动态规划方法求解，人为地赋予它为了应用动态规划方法求解，人为地赋予它“时段时段”的概念，将投资项目排序，首先考虑对项目的概念，将投资项目排序，首先考虑对项目1投资，投资，然后考虑对项目然后考虑对项目2投资投资，即把问题划分为，即把问题划分为3个阶个阶段，每个阶段只决定对一个项目应投资的金额。段，每个阶段只决定对一个项目应投资的金额。通常把决策变量通常把决策变量uk定为原静态规划的变量定为原静态规划的变量xk即设即设状态变量和决策变量有密切关系，状态变量一般状态变量和决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。为累计量或随递推过程变化的量。可把每阶段可供使用的资金定为状态变量可把每阶段可供使用的资金定为状态变量sk，初始，初始状态为状态为s1=10 安徽科技学院安徽科技学院 运筹与优化运筹与优化u1为可分配用于第一种项目的最大资金，则第一阶为可分配用于第一种项目的最大资金，则第一阶段时有：段时有：第二阶段第二阶段(k=2)时，状态变量时，状态变量s2为余下可投资于其为余下可投资于其余两个项目的资金，即：余两个项目的资金，即：一般地，当第一般地，当第k段时段时 安徽科技学院安徽科技学院 运筹与优化运筹与优化于是有于是有状态变量状态变量sk：第第k阶段可以投资于第阶段可以投资于第k项到第项到第3个项目个项目的资金的资金决策变量决策变量xk：决定给第决定给第k项目的资金项目的资金状态转移方程：状态转移方程：sk+1=sk-uk指标函数：指标函数：最优指标函数最优指标函数fk(sk)：当可投资金为当可投资金为sk时，投资第时，投资第k-3项所得最大收益。基本方程为：项所得最大收益。基本方程为：安徽科技学院安徽科技学院 运筹与优化运筹与优化0ss2x2当当k=2时，时，这是一个函数求极值问这是一个函数求极值问题题,利用微分方法可求得利用微分方法可求得该函数有极小值该函数有极小值.当当k=3时，时，显然当显然当，函数取极大值为，函数取极大值为 安徽科技学院安徽科技学院 运筹与优化运筹与优化要讨论要讨论s2的具体情况的具体情况:当当 时，时，当当 时，时，此时此时此时此时到此，第二阶段的决策已经作出到此，第二阶段的决策已经作出 安徽科技学院安徽科技学院 运筹与优化运筹与优化减函数减函数此结论与前矛盾，故舍去此结论与前矛盾，故舍去当当k=1时，时，时时注：此时注：此时由前面分析可知由前面分析可知而而 安徽科技学院安徽科技学院 运筹与优化运筹与优化另取另取此时此时又是一个求极值问题，微分求解又是一个求极值问题，微分求解比较比较0,10的端点的端点当当 时，时，当当 时，时，再由递推方程递推：再由递推方程递推：最优方案为全部资金投到第三个项目最优方案为全部资金投到第三个项目 安徽科技学院安徽科技学院 运筹与优化运筹与优化2.连续变量的离散化解法连续变量的离散化解法:例如投资分配问题例如投资分配问题的一般静态模型为：的一般静态模型为：建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：其状态转移方程为：其状态转移方程为：sk+1=sk-xk 安徽科技学院安徽科技学院 运筹与优化运筹与优化 由于由于sk与与xk都是连续变量，当各阶段指标都是连续变量，当各阶段指标gk(xk)，没有特没有特殊性质而较为复杂时，要求出殊性质而较为复杂时，要求出fk(sk)比较困难，因而求全过程比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量离的最优策略也就相当不容易，这时常常采用把连续变量离散化的方法求其数值解，具体做法如下：散化的方法求其数值解，具体做法如下：（1）令）令sk=0,2,m=a，把区间把区间0,a进行分割，进行分割，的的大小可依据问题所要求的精度及计算机的容量来定。大小可依据问题所要求的精度及计算机的容量来定。（2）规定状态变量）规定状态变量sk及决策变量及决策变量xk只在离散的点只在离散的点0,2,m上取值，相应的指标函数上取值，相应的指标函数fk(sk)就被定义在这些离散值上，就被定义在这些离散值上，于是递推方程变为：于是递推方程变为：其中其中 安徽科技学院安徽科技学院 运筹与优化运筹与优化（3）按逆序方法，逐步递推求出）按逆序方法，逐步递推求出fn(sn),f1(s1)，最后求出，最后求出最优资金分配方案。最优资金分配方案。例例2 用连续变量的离散化求解用连续变量的离散化求解解解 令令 ，将区间，将区间0,10分割成分割成0,2,6,8,10六个点，即状六个点，即状态变量态变量sk集合为集合为0,2,4,6,8,10允许决策集合为允许决策集合为 均在分割点上取值。均在分割点上取值。安徽科技学院安徽科技学院 运筹与优化运筹与优化动态规划基本方程为：动态规划基本方程为：当当k=3时，时，其中其中s3和和x3的集合均为的集合均为0,2,4,6,8,10,计算结果如下表计算结果如下表s30246810f3(s3)083272128200 x3*0246810 安徽科技学院安徽科技学院 运筹与优化运筹与优化计算结果如下表计算结果如下表s20246810 x200 20 2 40 2 4 60 2 4 6 80 2 4 6 8 10g2+f30 8 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 90f20183672128200 x2*024000当当k=2时，时，计算结果如下表计算结果如下表s110 x10246810g1+f220013688605040f1200 x1*0当当k=1时，时，安徽科技学院安徽科技学院 运筹与优化运筹与优化计算结果表明，最优决策为：计算结果表明，最优决策为：最大收益为：最大收益为：与例与例5结论完全相同。结论完全相同。注意：这种方法有可能丢失最优解，一般得到原问题注意：这种方法有可能丢失最优解，一般得到原问题的近似解的近似解 安徽科技学院安徽科技学院 运筹与优化运筹与优化练练 习习用连续变量的离散化方法求解下面的非线性规划用连续变量的离散化方法求解下面的非线性规划令令sk=0,1,2,3,4，列表求解列表求解逆序解法逆序解法:基本方程基本方程:注意到注意到目标函目标函数是乘数是乘积的形积的形式：式：安徽科技学院安徽科技学院 运筹与优化运筹与优化 背包问题的一般提法是：一位旅行者携带背包去登山、已背包问题的一般提法是：一位旅行者携带背包去登山、已知他所能承受的背包重量限度为知他所能承受的背包重量限度为a千克，现有千克，现有n种物品可供他选种物品可供他选择装入背包。第择装入背包。第i种物品的单件重量为种物品的单件重量为ai干克、其价值干克、其价值(可以是表可以是表明本物品对登山的重要性的数量指标明本物品对登山的重要性的数量指标)是携带数量是携带数量xi的函数的函数ci(xi)(i1,2,n),问旅行者应如何选择携带各种物品的件数，以使总问旅行者应如何选择携带各种物品的件数，以使总价值最大？价值最大？其他如车、船、飞机、潜艇、人造卫星等工具的最优装载其他如车、船、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。均等同于背包问题。三、背包问题的动态规划解法三、背包问题的动态规划解法 安徽科技学院安徽科技学院 运筹与优化运筹与优化背包问题的动态规划模型背包问题的动态规划模型1、阶段、阶段k：将可装入物品按：将可装入物品按1,2,.,n排序，共划分为排序，共划分为n个阶段，即个阶段，即 k1,2,.,n。2、状态变量、状态变量sk+1：在第：在第k段开始时，背包中允许装入前段开始时，背包中允许装入前k种物品的种物品的 总重量。总重量。3、决策变量、决策变量xk：装入第：装入第k种物品的件数。种物品的件数。4、状态转移方程：、状态转移方程：sk=sk+1-akxk5、允许决策集合为：、允许决策集合为：Dk(sk+1)xk|0 xk sk+1/ak，xk为整数整数6、最优指标函数、最优指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不表示在背包中允许装入物品的总重量不 超过超过sk+1千克，采用最优策略只装前千克，采用最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值7、顺序递、顺序递 推方程：推方程：安徽科技学院安徽科技学院 运筹与优化运筹与优化例例3:3:有一辆最大货运量为有一辆最大货运量为1010吨的卡车，用以装载吨的卡车，用以装载3 3种货物种货物每种货物的单位重量及相应单位价值如表所示。应如何装每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大载可使总价值最大?货物编号货物编号i123单位重量单位重量（t）345单位价值单位价值ci456设第设第i种货物装载的件数为种货物装载的件数为xi(i1,2,3)，则问题可表为，则问题可表为 安徽科技学院安徽科技学院 运筹与优化运筹与优化建立动态规划模型，由于决策变量取离散值，故可建立动态规划模型，由于决策变量取离散值，故可利用列表法求解利用列表法求解基本方程：基本方程：当当k=1时，时，或或s2012345678910f1(s2)0004448881212x1*00011122233 安徽科技学院安徽科技学院 运筹与优化运筹与优化当当k=2时，时，s30 1 2 345678910 x20 0 0 00 10 10 1 0 10 1 20 1 20 1 2c2+f10 0 0 44 54 58 5 8 9 8 9 1012 9 1012 13 10f2(s3)0 0 05589101213x2*0 0 0 01101201当当k=3时，时，此时此时x3*=0，逆推可得全部策略为，逆推可得全部策略为x1*=2,x2*=1,x3*=0最大价值为最大价值为13 安徽科技学院安徽科技学院 运筹与优化运筹与优化三、生产经营问题的动态规划解法三、生产经营问题的动态规划解法 在生产和经营管理中经常遇到如何合理地安排生产在生产和经营管理中经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。益最高的问题。例例4 4：某工厂生产并销售某种产品，已知今后四个月市场需某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位产品费用为：求预测如表，又每月生产单位产品费用为：每月库存每月库存j单位产品的费用为单位产品的费用为E(j)0.5j(干元干元)，该厂最大库，该厂最大库存容量为存容量为3单位，每月最大生产能力为单位，每月最大生产能力为6单位，计划开始和单位，计划开始和计划期末库存量都是零。计划期末库存量都是零。安徽科技学院安徽科技学院 运筹与优化运筹与优化试制定四个月的生产计划，在满足用户需求条件下总费用最小。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第假设第j+1个月的库存量是第个月的库存量是第j个月可销售量与该月用户需求量个月可销售量与该月用户需求量之差；而第之差；而第i个月的可销售量是本月初库存量与产量之和。个月的可销售量是本月初库存量与产量之和。i（月）1234gi（需求）2324解：建立动态规划模型解：建立动态规划模型(1)阶段：阶段：每个月为一个阶段，每个月为一个阶段，k1,2,3,4。(2)状态变量状态变量:sk为第为第k个月初的库存量。个月初的库存量。(3)决策变量决策变量:uk为第为第k个月的生产量。个月的生产量。(4)状态转移方程：状态转移方程：sk+1=sk+uk-gk 安徽科技学院安徽科技学院 运筹与优化运筹与优化(5)最优指标函数最优指标函数：fk(sk)表示第表示第k月状态为月状态为sk时，采用最佳时，采用最佳策略生产，从本月到计划结束（第策略生产，从本月到计划结束（第4个月末）的生产与存个月末）的生产与存贮最低费用。贮最低费用。(6)基本方程基本方程：当当k=4时，时，s40123f4(s4)76.565.5u4(s4)4321 安徽科技学院安徽科技学院 运筹与优化运筹与优化当当k=3时，时，s30123u3(s3)234512340123012C+E+f41212.51313.511.51212.5138 11.51212.5811.512f3(s3)1211.588u3*(s3)2100且为整数且为整数 安徽科技学院安徽科技学院 运筹与优化运筹与优化当当k=2时，时，s20123u2(s2)3456234512340123C+E+f31818.5161717.51815.516.51717.5151613.51714.515.5f2(s2)1615.51513.5u2*(s2)5430且为整数且为整数 安徽科技学院安徽科技学院 运筹与优化运筹与优化当当k=1时，时，s10u1(s1)2345C+E+f22121.52221.5f1(s1)21u1*(s1)2且为整数且为整数可得最佳生产计划为：可得最佳生产计划为：第一个月生产第一个月生产2 2单位，第二个月生产单位，第二个月生产5 5单位，单位，第三个月不生产，第三个月不生产，第四个月生产第四个月生产4 4单位。单位。安徽科技学院安徽科技学院 运筹与优化运筹与优化本本 章章 小小 结结动态规划问题的特点、类型动态规划问题的特点、类型动态规划问题的基本概念动态规划问题的基本概念 阶段、状态、决策和策略、状态转移、指标函数阶段、状态、决策和策略、状态转移、指标函数动态规划的求解方法（逆序法和顺序法）动态规划的求解方法（逆序法和顺序法）离散确定性动态规划的求解方法离散确定性动态规划的求解方法动态规划模型的建立动态规划模型的建立