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

1、 4.5 动态规划 运用举例ORXJTU第四章 动态规划多阶段有限资源分配问题多阶段有限资源分配问题资源延续分配问题资源延续分配问题 设有数量为设有数量为x的某种资源的某种资源, 将它投入两种消费方式将它投入两种消费方式A和和B中中,以数量以数量y投入消费方式投入消费方式A, 剩下的量投入消费方式剩下的量投入消费方式B, 那么可得那么可得到收到收入入 , 其中其中 和和 是知函数是知函数, 并且并且 =0. 再设以再设以y与与x-y分别投入两种消费方式分别投入两种消费方式A、B后可以回收再生后可以回收再生产产, 回收率分别为回收率分别为 与与 , 因此在第一阶段消费后回收因此在第一阶段消费后回

2、收的总资源为的总资源为 , 再将再将 投入消费方式投入消费方式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 xyORXJTU第四章 动态规划 假设上面的过程进展假设上面的过程进展n个阶段个阶段, 希望选择希

3、望选择 , 使使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个阶段个阶段ORXJTU第四章 动态规划形状转移方程形状转移方程 : 下一阶段的资源量下一阶段的资源量k+1kkk()

4、xayb xy根本方程的导出根本方程的导出 :k阶段的效益 :kkk()()g yh xy战略战略 :1n-1,y yy目的目的 : 选取选取 ,使每一阶段的效益合起来到达最大使每一阶段的效益合起来到达最大 12n-1,y y yy 令令 表示开场有资源表示开场有资源x, 再进展再进展k个阶段消费并采用最优个阶段消费并采用最优分配战略后得到的最大总收入分配战略后得到的最大总收入. k( )fx决策决策 : : 对每个形状对每个形状 , 都有一允许决策集合都有一允许决策集合 ,kykxk0,xkk0,yxORXJTU第四章 动态规划 当当k=2时时, 由于前一阶段分别以由于前一阶段分别以y, x

5、-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 ORXJTU第四章 动态规划由此得逆推

6、关系由此得逆推关系 : 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)0gh

7、ORXJTU第四章 动态规划由于由于 : (对于固定的对于固定的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( )(), ( )()

8、( )max( ), ( )fxh xfbx g xfaxf xh x g xORXJTU第四章 动态规划为为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的凸函数 ORX

9、JTU第四章 动态规划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 归纳法归纳法ORXJTU第四章 动态规划把区间把区间0, x进展分割进展分割, 令令

10、精度要求精度要求计算机容量计算机容量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确定出最优决策确定出最优决策所求的所求的最大总收入最大总收入离散取值离散取值, 变化变化, 逐渐逐渐, 逐个计算函数值逐个计算函数值或用表格法求出数值解或用表格法求出数值解 计算机实现计算机实现ORXJTU第四章 动态规划用用DP求解某些求解某些NLP :按问题变量的个数划分阶段按问题变量的个数划分阶段2123

11、123imaxs.t.(0)0,1,2,3zxxxxxxc cxi222123123imax42120s.t.3290,1,2,3zxxxxxxxi乘积可分乘积可分可加可分可加可分前提前提 : 可直接用微分法可直接用微分法(求稳定点求稳定点 ) 可得到解析解可得到解析解 !( )0fORXJTU第四章 动态规划二维资源分配问题二维资源分配问题 : 设有两种原料设有两种原料, 数量各为数量各为a和和b单位单位, 需求分配用于产生需求分配用于产生n种种产品产品, 假设第一种原料以数量假设第一种原料以数量 为单位为单位, 第二种原料以数量第二种原料以数量 为单位为单位, 用于消费第用于消费第i种产品

12、种产品, 其收入为其收入为 .问应如何分配这两种原料于问应如何分配这两种原料于n种产品的消费种产品的消费, 使总收入最大使总收入最大?ixiyiii( ,)g x y静态规划问题静态规划问题 :111222nnn12n12niimax( ,)(,)(,)s.t.,0,0 (1)g x ygxygxyxxxayyybxyin 且且为为整整数数ORXJTU第四章 动态规划用动态规划用动态规划 形状变量、决策变量均为二维的形状变量、决策变量均为二维的形状变量形状变量 :x表示分配用于消费第k种产品至第n种产品的第一种原料的数量y表示分配用于消费第k种产品至第n种产品的第二种原料的数量决策变量决策变量

13、 :k( , )Sx ykkk(,)uxy 表示分配给第表示分配给第k种产品用的第一种原料的种产品用的第一种原料的单位数量单位数量kx 表示分配给第表示分配给第k种产品用的第二种原料的种产品用的第二种原料的单位数量单位数量kyORXJTU第四章 动态规划允许决策集合允许决策集合 :形状转移方程形状转移方程效益函数效益函数 :kkkk0( , )0 xxDx yuyyk+1( , )Sx y kxxxkyyy: 用来消费第用来消费第k+1种产品至第种产品至第n种产品的第一种产品的第一(二二)种原料的种原料的 数量数量( )x y : 表示以第一种原料数量为表示以第一种原料数量为x,第一种原料数量

14、为第一种原料数量为y, 分配分配 用于消费第用于消费第k种产品至第种产品至第n种产品时所得的最大收入种产品时所得的最大收入k( , )fx y第第k阶段的阶段的kSORXJTU第四章 动态规划那那么么nn( , )( , )fx ygx ykkkkkkk+1kk0 xx0 yy( , )max(,)(,) ,1,1fx ygxyfxxyykn 问题的最大收入问题的最大收入1( , )f a bg(x,y)的复杂性, 难于直接计算求解数值计算数值计算降维降维, 简化处置简化处置1 逐次逼近法逐次逼近法 : 先坚持一个变量不变先坚持一个变量不变, 对另一个变量求最优对另一个变量求最优(一维问题一维

15、问题), 然后交替地固定然后交替地固定, 以迭代的方式反复进展以迭代的方式反复进展, 直到获得满足某种直到获得满足某种要求的解为止要求的解为止 .ORXJTU第四章 动态规划设设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.,0yyybyORXJTU第四章 动态

16、规划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)mmORXJTU第四章 动态规划对每个对每个k值值, 需计算需计算

17、 的的 个值个值 .k12( , )(1)(1)fx ymm计算量很大计算量很大, 且随着且随着 的添加迅速膨胀的添加迅速膨胀. 分点分点维数维数维数灾难维数灾难 !粗格子点法粗格子点法: :1 ) 先用少数的格子点进展粗糙的计算先用少数的格子点进展粗糙的计算, 求出对应的最优解求出对应的最优解 .2 ) 在在“最大解附近的小范围内进一步细分最大解附近的小范围内进一步细分, 并求在细分格子并求在细分格子 点上的最优解点上的最优解. 转转 1 ) .能够导致漏掉全局最优解能够导致漏掉全局最优解 !应结合对目的函数的特性进展分析应结合对目的函数的特性进展分析 !ORXJTU第四章 动态规划3 La

18、grange乘数法乘数法:引入引入Lagrange乘子乘子 , 将二维问题转化将二维问题转化为为nniiiii=1i=1niii0i=1max(,)()s.t.,g xyyxaxyZ因因 为固定的参数为固定的参数, 问题关于问题关于 可分可分 .iyiiiiiiiiiy0( )( , )max( ,)h xh xg x yy为有意义为有意义suppose that :iiiiyi( ,)lim0g x yyORXJTU第四章 动态规划1122nnmax()()()h xh xh x12ni0s.t.,xxxaxZ( )一维问题一维问题一维方程一维方程 求解求解iiii( )( )xxyynii

19、=1( )ifyb为最优解为最优解ii,x y用插值法、优化中乘子法用插值法、优化中乘子法 调整调整 的取值的取值Otherwisenii=1( )untilybORXJTU第四章 动态规划()的解能够不独一的解能够不独一 . 无妨设有无妨设有m个最优解个最优解 :能够出现下面几种情况能够出现下面几种情况 :(k)(k)(k)(k)1n1n( ),( ),( ),( ),1,2,xxyykm令令 :nn(k)(k)iikki=1i=1( )min( ),( )max( ),1FyGykm1 存在某一个存在某一个k, 使使n(k)ii=1( )yb为最优解为最优解ii,x y2 , 那么增大那么

20、增大 的值的值, 重新求重新求()( )Fb3 , 那么减少那么减少 的值的值, 重新求重新求()( )Gb4 , 且对一切的且对一切的k, 均有均有 , 那么算法那么算法 不适用不适用! 停顿迭代停顿迭代 .( )( )FbGn(k)ii=1( )yb可思索将可思索将Lagrange乘子法用于约束条件乘子法用于约束条件nii=1xaORXJTU第四章 动态规划 形状转移不能完全确定形状转移不能完全确定, 它也许按它也许按某种知的概率分布取值某种知的概率分布取值不确定性的多阶段问题不确定性的多阶段问题由于随机要素由于随机要素称为随机性的决策过程称为随机性的决策过程采购问题采购问题 ： 某厂消费

21、上需求在近五周内必需采购一批原料某厂消费上需求在近五周内必需采购一批原料, 而估计而估计在未来五周内价钱会动摇在未来五周内价钱会动摇, 其浮动价钱和概率已测得如下表其浮动价钱和概率已测得如下表所示所示 :试求在哪一周内以什么价钱购入试求在哪一周内以什么价钱购入, 使其采购价钱的数学期望使其采购价钱的数学期望最小最小 , 并求出期望值并求出期望值 .Scenario 1 500 0.3PriceProbScenario 3 700 0.4Scenario 2 600 0.3ORXJTU第四章 动态规划解解 :这里价钱是一个随机变量这里价钱是一个随机变量, 是按知的概率分布取值的是按知的概率分布取

22、值的. 按采购期限按采购期限5周分为周分为5个阶段个阶段, 将每周的价钱看作该阶段的将每周的价钱看作该阶段的形状形状 .: 形状变量形状变量, 表示第表示第k周的实践价钱周的实践价钱 .: 决策变量决策变量 =1 表示第k周决议采购0 表示第k周决议等待: 表示第表示第k周决议等待周决议等待, 而在以后采取最优决策时采购价钱而在以后采取最优决策时采购价钱 的期望值的期望值 .kxkEykk()fyky: 表示第表示第k周实践价钱为周实践价钱为 时时, 从第从第k周至第周至第5周采取最周采取最优优 决策所得的最小期望值决策所得的最小期望值 . kyORXJTU第四章 动态规划可写出逆序递推关系式

23、为可写出逆序递推关系式为 :55555kkkkEkk(),()min,fyyySfyyyyS其中其中k500,600,700 ,1,2,3,4,5Sk由由 和和 的定义知的定义知 :kEkk()yfykEk+1k+1k+1k+1k+1()0.3(500)0.3(600)0.4(700)yEfyfff最优决策为最优决策为 :kxkkk1()fyy（采采购购） 当当kkkE0()fyy（等等待待） 当当ORXJTU第四章 动态规划从最后一周开场从最后一周开场, 逐渐向前递推计算逐渐向前递推计算, 详细计算过程如下详细计算过程如下 : 即在第五周时即在第五周时, 假设所需的原料尚未买入假设所需的原料尚未买入, 那么无论市场那么无论市场价钱价