运筹学4.5动态规划应用举例.ppt

4.5 动态规划 应用举例OR第四章 动态规划多阶段有限资源分配问题多阶段有限资源分配问题资源连续分配问题资源连续分配问题 设有数量为设有数量为x的某种资源的某种资源,将它投入两种生产方式将它投入两种生产方式A和和B中中,以数量以数量y投入生产方式投入生产方式A,剩下的量投入生产方式剩下的量投入生产方式B,则可得到收则可得到收入入 ,其中其中 和和 是已知函数是已知函数,并且并且 =0.再设以再设以y与与x-y分别投入两种生产方式分别投入两种生产方式A、B后可以回收再生后可以回收再生产产,回收率分别为回收率分别为 与与 ,因此在第一阶段生产后回收因此在第一阶段生产后回收的总资源为的总资源为 ,再将再将 投入生产方式投入生产方式A与与B,和第和第一阶段一样一阶段一样,若以若以 与与 分别投入生产方式分别投入生产方式A和和B,则又可得则又可得到收入到收入 ,回收资源回收资源 .因此因此,两两个阶段的总收入为个阶段的总收入为()()g yh xy()()g yh y(0)(0)gh(0,1)aba b1()xayb xy1x111yxy111()()g yh xy2111()xayb xy111()()()()g yh xyg yh xyOR第四章 动态规划 若上面的过程进行若上面的过程进行n个阶段个阶段,希望选择希望选择 ,使使n个阶段的总收入最大个阶段的总收入最大,则问题变成求则问题变成求 ,使使12n-1,y y yy12n-1,y y yy111n 1n 1n 112111n 1n 2n 2n 2iimax()()()()()()s.t.()()()0,0,11g yh xyg yh xyg yh xyxayb xyxayb xyxayb xyyxyxin 状态状态:拥有资源的数量拥有资源的数量 kx对上述对上述n个阶段的决策问题个阶段的决策问题,选在第选在第k个阶段个阶段OR第四章 动态规划状态转移方程状态转移方程:下一阶段的资源量下一阶段的资源量k+1kkk()xayb xy基本方程的导出基本方程的导出:k阶段的效益阶段的效益:kkk()()g yh xy策略策略:1n-1,y yy目标目标:选取选取 ,使每一阶段的效益合起来达到最大使每一阶段的效益合起来达到最大 12n-1,y y yy 令令 表示开始有资源表示开始有资源x,再进行再进行k个阶段生产并采用最优个阶段生产并采用最优分配策略后得到的最大总收入分配策略后得到的最大总收入.k()fx决策决策:对每个状态对每个状态 ,都有一允许决策集合都有一允许决策集合 ,kykxk0,xkk0,yxOR第四章 动态规划 当当k=2时时,由于前一阶段分别以由于前一阶段分别以y,x-y投投A、B,生产后回收得生产后回收得 作为下一个阶段开始时可以投入生产的资源量作为下一个阶段开始时可以投入生产的资源量,若采用最优方式投入生产若采用最优方式投入生产,由最优性原理由最优性原理,后一个阶段总收入是后一个阶段总收入是 ,所以所以:1()xayb xy11()f x210 y x()max()()()fxg yh xyfayb xy 对对 ,同样的分析得同样的分析得:2kknkk-10 y x()max()()()fxg yh xyfayb xy 当当k=1时时,10 y x()max()()f xg yh xy OR第四章 动态规划由此得逆推关系由此得逆推关系:g、h一般非线性函数、复杂、无法用解析法求解一般非线性函数、复杂、无法用解析法求解 求数值解求数值解,离散化离散化!10 y x()max()()f xg yh xy kk-10 y x()max()()(),2fxg yh xyfayb xyk 对上述的资源分配问题对上述的资源分配问题,当当 ,很复杂时很复杂时,基本方程基本方程的解就不容易找到的解就不容易找到.但当但当 ,均为凸函数均为凸函数,且且 时时,则可以证明在则可以证明在每个阶段上每个阶段上y的最优决策总是取其端点的值的最优决策总是取其端点的值.()()g y h y()()g y h y(0)(0)0ghOR第四章 动态规划因为因为:(对于固定的对于固定的x)a)由由 ,凸凸()()g y h y()()()F yg yh xy凸凸121212,0,1,y y 11221122()()()FyyF yF y b),12F F 凸凸12()max(),()F xF x F x凸凸Th.:设设 ,为凸函数为凸函数,且且 ,则则n阶段资源阶段资源分配问题的最优策略分配问题的最优策略y在每个阶段总取在每个阶段总取 的端点的值的端点的值,并且并且:()()g y h y(0)(0)0gh0yxkk-1k-11()max()(),()()()max(),()fxh xfbx g xfaxf xh x g xOR第四章 动态规划为为y的凸函数的凸函数,其最大值一定在其最大值一定在y=0或或y=x处达到处达到由归纳法即可得证由归纳法即可得证Proof:10 y x()max()()f xg yh xy 1()max(),()f xh x g x为为x的凸函数的凸函数.1()f x也是也是y的凸函数的凸函数.1()f ayb xy210 y x()max()()()fxg yh xyfayb xy 11max()(),()()h xf bx g xf axa)b)y的凸函数的凸函数 OR第四章 动态规划Exp.:在有限资源分配问题中在有限资源分配问题中22()2,()0,0,1,01g xcxxh xcxxxca bbab 且且,故上述故上述Th知知:()()(0)(0)0g yh ygh、均均凸凸,2221()max2,f xcxxcxxcxx 2222222()max2,fxcxxcaxa xcxxcbxb x2222max(1)(2),(1)(1)axc axbxcb x22(1)(1)cb xbx k2k2k2(1)1()11cbbfxxxbb 归纳法归纳法OR第四章 动态规划把区间把区间0,x进行分割进行分割,令令 精度要求精度要求计算机容量计算机容量0,2,mx10 j i()max()()f ig jh ij kk-10 j i()max()()()()fig jh ijfa jb ij 对对 ,依次计算出依次计算出0,1,im12n(),(),()f if ifinn()()fmfx确定出最优决策确定出最优决策所求的所求的最大总收入最大总收入离散取值离散取值,变化变化,逐步逐步,逐个计算函数值逐个计算函数值或用表格法求出数值解或用表格法求出数值解 计算机实现计算机实现OR第四章 动态规划用用DP求解某些求解某些NLP:按问题变量的个数划分阶段按问题变量的个数划分阶段2123123imaxs.t.(0)0,1,2,3zxxxxxxc cxi222123123imax42120s.t.3290,1,2,3zxxxxxxxi乘积可分乘积可分可加可分可加可分前提前提:可直接用微分法可直接用微分法(求稳定点求稳定点 )可得到解析解可得到解析解!()0fOR第四章 动态规划二维资源分配问题二维资源分配问题:设有两种原料设有两种原料,数量各为数量各为a和和b单位单位,需要分配用于产生需要分配用于产生n种种产品产品,如果第一种原料以数量如果第一种原料以数量 为单位为单位,第二种原料以数量第二种原料以数量 为单位为单位,用于生产第用于生产第i种产品种产品,其收入为其收入为 .问应如何分配这两种原料于问应如何分配这两种原料于n种产品的生产种产品的生产,使总收入最大使总收入最大?ixiyiii(,)g x y静态规划问题静态规划问题:111222nnn12n12niimax(,)(,)(,)s.t.,0,0(1)g x ygxygxyxxxayyybxyin 且且为为整整数数OR第四章 动态规划用动态规划用动态规划 状态变量、决策变量均为二维的状态变量、决策变量均为二维的状态变量状态变量:x表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品种产品的第一种原料的数量的第一种原料的数量y表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品种产品的第二种原料的数量的第二种原料的数量决策变量决策变量:k(,)Sx ykkk(,)uxy 表示分配给第表示分配给第k种产品用的第一种原料的种产品用的第一种原料的单位数量单位数量kx 表示分配给第表示分配给第k种产品用的第二种原料的种产品用的第二种原料的单位数量单位数量kyOR第四章 动态规划允许决策集合允许决策集合:状态转移方程状态转移方程效益函数效益函数:kkkk0(,)0 xxDx yuyyk+1(,)Sx y kxxxkyyy:用来生产第用来生产第k+1种产品至第种产品至第n种产品的第一种产品的第一(二二)种原料的种原料的 数量数量()x y:表示以第一种原料数量为表示以第一种原料数量为x,第一种原料数量为第一种原料数量为y,分配分配 用于生产第用于生产第k种产品至第种产品至第n种产品时所得的最大收入种产品时所得的最大收入k(,)fx y第第k阶段的阶段的kSOR第四章 动态规划则则nn(,)(,)fx ygx ykkkkkkk+1kk0 xx0 yy(,)max(,)(,),1,1fx ygxyfxxyykn 问题的最大收入问题的最大收入1(,)f a bg(x,y)的复杂性的复杂性,难于直接计算求解难于直接计算求解数值计算数值计算降维降维,简化处理简化处理1 逐次逼近法逐次逼近法:先保持一个变量不变先保持一个变量不变,对另一个变量求最优对另一个变量求最优(一维问题一维问题),然后交替地固定然后交替地固定,以迭代的形式反复进行以迭代的形式反复进行,直到获得满足某种直到获得满足某种要求的解为止要求的解为止.OR第四章 动态规划设设n(0)(0)(0)(0)(0)12nii=1,:xxxxxa固定固定 为为(0)xx用一维方法求解用一维方法求解,得得(0)(0)(0)(0)12n,yyyy固定固定 为为(0)yyn(0)iiii=1nii0i=1max(,)s.t.,g xyxaxZ(1)(1)(1)1n,xxx(0)(0)(0)111222nnnmax(,)(,)(,)g xygxygxy12nis.t.,0yyybyOR第四章 动态规划nnn(0)(0)(0)(1)(0)iiiiiiiiii=1i=1i=1(,)(,)(,)g xyg xyg xy(k)(k),0,1,2,xyk n(k)(k)iiii=1(,)g xy2 粗格子点法粗格子点法(疏密法疏密法):一般只收敛到局部最优解一般只收敛到局部最优解.为找到全局最优解为找到全局最优解,可同时选各个可同时选各个 ,(0)x采用离散化方法计算采用离散化方法计算.将矩形定义域划分成网格将矩形定义域划分成网格,然后在格点上计算然后在格点上计算1200 xamybm等分等分个格点个格点12(1)(1)mmOR第四章 动态规划对每个对每个k值值,需计算需计算 的的 个值个值.k12(,)(1)(1)fx ymm计算量很大计算量很大,且随着且随着 的增加迅速膨胀的增加迅速膨胀.分点分点维数维数维数灾难维数灾难!粗格子点法粗格子点法:1)先用少数的格子点进行粗糙的计算先用少数的格子点进行粗糙的计算,求出对应的最优解求出对应的最优解.2)在在“最大最大”解附近的小范围内进一步细分解附近的小范围内进一步细分,并求在细分格并求在细分格子子 点上的最优解点上的最优解.转转 1).可能导致漏掉全局最优解可能导致漏掉全局最优解!应结合对指标函数的特性进行分析应结合对指标函数的特性进行分析!OR第四章 动态规划3 Lagrange乘数法乘数法:引入引入Lagrange乘子乘子 ,将二维问题转化为将二维问题转化为nniiiii=1i=1niii0i=1max(,)()s.t.,g xyyxaxyZ因因 为固定的参数为固定的参数,问题关于问题关于 可分可分.iyiiiiiiii