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

《运筹学4.5动态规划应用举例》由会员分享，可在线阅读，更多相关《运筹学4.5动态规划应用举例（27页珍藏版）》请在装配图网上搜索。

1、 动态规划 应用举例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个阶段个阶段,希望选择希望选择 ,使使n个阶段的总收入最大个阶段的总收入最大,则问题变

3、成求则问题变成求 ,使使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()xayb xy基本方程的导出基本方程的导出:k阶段的效益阶段的效益:kkk()()g

4、yh xy策略策略:1n-1,y yy目标目标:选取选取 ,使每一阶段的效益合起来达到最大使每一阶段的效益合起来达到最大 12n-1,y y yy 令令 表示开始有资源表示开始有资源x,再进行再进行k个阶段生产并采用最优个阶段生产并采用最优分配策略后得到的最大总收入分配策略后得到的最大总收入.k()fx决策决策:对每个状态对每个状态 ,都有一允许决策集合都有一允许决策集合 ,kykxk0,xkk0,yxORXJTU第四章 动态规划 当当k=2时时,由于前一阶段分别以由于前一阶段分别以y,x-y投投A、B,生产后回收得生产后回收得 作为下一个阶段开始时可以投入生产的资源量作为下一个阶段开始时可以

5、投入生产的资源量,若采用最优方式投入生产若采用最优方式投入生产,由最优性原理由最优性原理,后一个阶段总收入是后一个阶段总收入是 ,所以所以: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第四章 动态规划由此得逆推关系由此得逆推关系:g、h一般非线性函数、复杂、无法用解析法求解一般非线性函数、复杂、无法用解析法求解 求数值解求数值解,离散化离散化

6、!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)0ghORXJTU第四章 动态规划因为因为:(对于固定的对于固定的x)a)由由 ,凸凸()()g y h y()()()F yg yh xy凸凸1

7、21212,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 xORXJTU第四章 动态规划为为y的凸函数的凸函数,其最大值一定在其最大值一定在y=0或或y=x处达到处达到由归纳法即可得证由归纳

8、法即可得证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的凸函数的凸函数 ORXJTU第四章 动态规划Exp.:在有限资源分配问题中在有限资源分配问题中22()2,()0,0,1,01g xcxxh xcxxxca bbab 且且,故上述故上述Th知知:()()(0)(0)0g yh ygh、均均凸凸,2221()

9、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进行分割进行分割,令令 精度要求精度要求计算机容量计算机容量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()()f

10、mfx确定出最优决策确定出最优决策所求的所求的最大总收入最大总收入离散取值离散取值,变化变化,逐步逐步,逐个计算函数值逐个计算函数值或用表格法求出数值解或用表格法求出数值解 计算机实现计算机实现ORXJTU第四章 动态规划用用DP求解某些求解某些NLP:按问题变量的个数划分阶段按问题变量的个数划分阶段2123123imaxs.t.(0)0,1,2,3zxxxxxxc cxi222123123imax42120s.t.3290,1,2,3zxxxxxxxi乘积可分乘积可分可加可分可加可分前提前提:可直接用微分法可直接用微分法(求稳定点求稳定点 )可得到解析解可得到解析解!()0fORXJTU第四

11、章 动态规划二维资源分配问题二维资源分配问题:设有两种原料设有两种原料,数量各为数量各为a和和b单位单位,需要分配用于产生需要分配用于产生n种种产品产品,如果第一种原料以数量如果第一种原料以数量 为单位为单位,第二种原料以数量第二种原料以数量 为单位为单位,用于生产第用于生产第i种产品种产品,其收入为其收入为 .问应如何分配这两种原料于问应如何分配这两种原料于n种产品的生产种产品的生产,使总收入最大使总收入最大?ixiyiii(,)g x y静态规划问题静态规划问题:111222nnn12n12niimax(,)(,)(,)s.t.,0,0(1)g x ygxygxyxxxayyybxyin

12、且且为为整整数数ORXJTU第四章 动态规划用动态规划用动态规划 状态变量、决策变量均为二维的状态变量、决策变量均为二维的状态变量状态变量:x表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品种产品的第一种原料的数量的第一种原料的数量y表示分配用于生产第表示分配用于生产第k种产品至第种产品至第n种产品种产品的第二种原料的数量的第二种原料的数量决策变量决策变量:k(,)Sx ykkk(,)uxy 表示分配给第表示分配给第k种产品用的第一种原料的种产品用的第一种原料的单位数量单位数量kx 表示分配给第表示分配给第k种产品用的第二种原料的种产品用的第二种原料的单位数量单位数量kyOR

13、XJTU第四章 动态规划允许决策集合允许决策集合:状态转移方程状态转移方程效益函数效益函数:kkkk0(,)0 xxDx yuyyk+1(,)Sx y kxxxkyyy:用来生产第用来生产第k+1种产品至第种产品至第n种产品的第一种产品的第一(二二)种原料的种原料的 数量数量()x y:表示以第一种原料数量为表示以第一种原料数量为x,第一种原料数量为第一种原料数量为y,分配分配 用于生产第用于生产第k种产品至第种产品至第n种产品时所得的最大收入种产品时所得的最大收入k(,)fx y第第k阶段的阶段的kSORXJTU第四章 动态规划则则nn(,)(,)fx ygx ykkkkkkk+1kk0 x

14、x0 yy(,)max(,)(,),1,1fx ygxyfxxyykn 问题的最大收入问题的最大收入1(,)f a bg(x,y)的复杂性的复杂性,难于直接计算求解难于直接计算求解数值计算数值计算降维降维,简化处理简化处理1 逐次逼近法逐次逼近法:先保持一个变量不变先保持一个变量不变,对另一个变量求最优对另一个变量求最优(一维问题一维问题),然后交替地固定然后交替地固定,以迭代的形式反复进行以迭代的形式反复进行,直到获得满足某种直到获得满足某种要求的解为止要求的解为止.ORXJTU第四章 动态规划设设n(0)(0)(0)(0)(0)12nii=1,:xxxxxa固定固定 为为(0)xx用一维方

15、法求解用一维方法求解,得得(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第四章 动态规划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 粗格子点法粗格子点法(疏密法疏密法):一般只收敛到局部最优解一般只收敛到局部最

16、优解.为找到全局最优解为找到全局最优解,可同时选各个可同时选各个 ,(0)x采用离散化方法计算采用离散化方法计算.将矩形定义域划分成网格将矩形定义域划分成网格,然后在格点上计算然后在格点上计算1200 xamybm等分等分个格点个格点12(1)(1)mmORXJTU第四章 动态规划对每个对每个k值值,需计算需计算 的的 个值个值.k12(,)(1)(1)fx ymm计算量很大计算量很大,且随着且随着 的增加迅速膨胀的增加迅速膨胀.分点分点维数维数维数灾难维数灾难!粗格子点法粗格子点法:1)先用少数的格子点进行粗糙的计算先用少数的格子点进行粗糙的计算,求出对应的最优解求出对应的最优解.2)在在“

17、最大最大”解附近的小范围内进一步细分解附近的小范围内进一步细分,并求在细分格并求在细分格子子 点上的最优解点上的最优解.转转 1).可能导致漏掉全局最优解可能导致漏掉全局最优解!应结合对指标函数的特性进行分析应结合对指标函数的特性进行分析!ORXJTU第四章 动态规划3 Lagrange乘数法乘数法:引入引入Lagrange乘子乘子 ,将二维问题转化为将二维问题转化为nniiiii=1i=1niii0i=1max(,)()s.t.,g xyyxaxyZ因因 为固定的参数为固定的参数,问题关于问题关于 可分可分.iyiiiiiiiiiy0()(,)max(,)h xh xg x yy为有意义为有

18、意义suppose that:iiiiyi(,)lim0g x yyORXJTU第四章 动态规划1122nnmax()()()h xh xhx12ni0s.t.,xxxaxZ()一维问题一维问题一维方程一维方程 求解求解iiii()()xxyynii=1()ifyb为最优解为最优解ii,x y用插值法、优化中乘子法用插值法、优化中乘子法 调整调整 的取值的取值Otherwisenii=1()untilybORXJTU第四章 动态规划()的解可能不唯一的解可能不唯一.不妨设有不妨设有m个最优解个最优解:可能出现下面几种情况可能出现下面几种情况:(k)(k)(k)(k)1n1n(),(),(),(

19、),1,2,xxyykm令令:nn(k)(k)iikki=1i=1()min(),()max(),1FyGykm1 存在某一个存在某一个k,使使n(k)ii=1()yb为最优解为最优解ii,x y2 ,则增大则增大 的值的值,重新求重新求()()Fb3 ,则减少则减少 的值的值,重新求重新求()()Gb4 ,且对所有的且对所有的k,均有均有 ,则算法则算法 不适用不适用!停止迭代停止迭代.()()FbGn(k)ii=1()yb可考虑将可考虑将Lagrange乘子法用于约束条件乘子法用于约束条件nii=1xaORXJTU第四章 动态规划 状态转移不能完全确定状态转移不能完全确定,它也许按它也许按

20、某种已知的概率分布取值某种已知的概率分布取值不确定性的多阶段问题不确定性的多阶段问题由于随机因素由于随机因素称为称为随机性的决策过程随机性的决策过程采购问题采购问题：某厂生产上需要在近五周内必须采购一批原料某厂生产上需要在近五周内必须采购一批原料,而估计而估计在未来五周内价格会波动在未来五周内价格会波动,其浮动价格和概率已测得如下表其浮动价格和概率已测得如下表所示所示:试求在哪一周内以什么价格购入试求在哪一周内以什么价格购入,使其采购价格的数学期望使其采购价格的数学期望最小最小,并求出期望值并求出期望值.Scenario 1 500PriceProbScenario 3 700Scenario

21、 2 600ORXJTU第四章 动态规划解解:这里价格是一个随机变量这里价格是一个随机变量,是按已知的概率分布取值的是按已知的概率分布取值的.按采购期限按采购期限5周分为周分为5个阶段个阶段,将每周的价格看作该阶段的将每周的价格看作该阶段的状态状态.:状态变量状态变量,表示第表示第k周的实际价格周的实际价格.:决策变量决策变量 =1 表示第表示第k周决定采购周决定采购0 表示第表示第k周决定等待周决定等待:表示第表示第k周决定等待周决定等待,而在以后采取最优决策时采购价格而在以后采取最优决策时采购价格 的期望值的期望值.kxkEykk()fyky:表示第表示第k周实际价格为周实际价格为 时时,

22、从第从第k周至第周至第5周采取最优周采取最优 决策所得的最小期望值决策所得的最小期望值.kyORXJTU第四章 动态规划可写出逆序递推关系式为可写出逆序递推关系式为: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第四章 动态规划从最后一周开始从最后一周开始,逐步向前递推

23、计算逐步向前递推计算,具体计算过程如下具体计算过程如下:即在第五周时即在第五周时,若所需的原料尚未买入若所需的原料尚未买入,则无论市场价格则无论市场价格如何如何,都必须采购都必须采购,不能再等不能再等.5k5()fyyk=5 时时,555(500)500,(600)600,(700)700fffk=4 时时,4E5550.3(500)0.3(600)0.4(700)610yfff44444444E4ySyS()min,min,610fyyyy5006006104if y 5006007004x41500600if yor40700y ORXJTU第四章 动态规划33333333E3ySyS()

24、min,min,574fyyyy5005743x=5003y=600 or 7003y30600700yor31500y 22222222E2ySyS()min,min,551.8fyyyy5002x=5002y=600 or 7002y20600700yor21500y 11111111E1ySyS()min,min,536.26fyy yy5001x=5001y=600 or 7001y10600700yor11500y ORXJTU第四章 动态规划最优策略为最优策略为:在第一、二、三周时在第一、二、三周时,若价格为若价格为500就采购就采购,否则应该等待否则应该等待.在第四周在第四周,价格为价格为500或或600时应采购时应采购,否则就等待否则就等待.在第五周在第五周,无论什么价格都要采购无论什么价格都要采购.依照上述最优策略进行采购时依照上述最优策略进行采购时,价格的数学期望值为价格的数学期望值为:234500 0.3 1+0.7+0.70.70.70.433600 0.3 0.70.4 0.723700 0.40.70.80106 +=1=525.382