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

§4.5

动态规划应用举例1ppt课件多阶段有限资源分配问题—资源连续分配问题设有数量为x的某种资源,将它投入两种生产方式A和B中,以数量y投入生产方式A,剩下的量投入生产方式B,则可得到收入,其中和是已知函数,并且=0.再设以y与x-y分别投入两种生产方式A、B后可以回收再生产,回收率分别为

与,因此在第一阶段生产后回收的总资源为,再将投入生产方式A与B,和第一阶段一样,若以与分别投入生产方式A和B,则又可得到收入,回收资源.因此,两个阶段的总收入为若上面的过程进行n个阶段,希望选择,使n个阶段的总收入最大,则问题变成求,使状态:拥有资源的数量对上述n个阶段的决策问题,选在第k个阶段状态转移方程:～下一阶段的资源量基本方程的导出:k阶段的效益:策略:目标:选取,使每一阶段的效益合起来达到最大令表示开始有资源x,再进行k个阶段生产并采用最优分配策略后得到的最大总收入.决策::对每个状态,都有一允许决策集合,当k=2时,由于前一阶段分别以y,x-y投A、B,生产后回收得作为下一个阶段开始时可以投入生产的资源量,若采用最优方式投入生产,由最优性原理,后一个阶段总收入是,所以:对,同样的分析得当k=1时,由此得逆推关系:g、h一般非线性函数、复杂、无法用解析法求解求数值解,离散化!对上述的资源分配问题,当,很复杂时,基本方程的解就不容易找到.但当,均为凸函数,且时,则可以证明在每个阶段上y的最优决策总是取其端点的值.因为:(对于固定的x)a)由,凸b),Th.

:

设,为凸函数,且,则n阶段资源分配问题的最优策略y在每个阶段总取的端点的值,并且:为y的凸函数,其最大值一定在y=0或y=x处达到由归纳法即可得证Proof:

为x的凸函数.也是y的凸函数.a)b)y的凸函数

﹟Exp.:在有限资源分配问题中,故上述Th知:归纳法把区间[0,x]进行分割,令

精度要求计算机容量对,依次计算出确定出最优决策所求的最大总收入离散取值,变化,逐步,逐个计算函数值或用表格法求出数值解计算机实现用DP求解某些NLP:按问题变量的个数划分阶段乘积可分可加可分前提:可直接用微分法(求稳定点)可得到解析解!二维资源分配问题:设有两种原料,数量各为a和b单位,需要分配用于产生n种产品,如果第一种原料以数量为单位,第二种原料以数量为单位,用于生产第i种产品,其收入为.问应如何分配这两种原料于n种产品的生产,使总收入最大?静态规划问题:用动态规划状态变量、决策变量均为二维的状态变量:x表示分配用于生产第k种产品至第n种产品的第一种原料的数量y表示分配用于生产第k种产品至第n种产品的第二种原料的数量决策变量:表示分配给第k种产品用的第一种原料的单位数量表示分配给第k种产品用的第二种原料的单位数量允许决策集合:状态转移方程效益函数::用来生产第k+1种产品至第n种产品的第一(二)种原料的数量:表示以第一种原料数量为x,第一种原料数量为y,分配用于生产第k种产品至第n种产品时所得的最大收入第k阶段的则～问题的最大收入g(x,y)的复杂性,难于直接计算求解数值计算降维,简化处理1>逐次逼近法:先保持一个变量不变,对另一个变量求最优(一维问题),然后交替地固定,以迭代的形式反复进行,直到获得满足某种要求的解为止.设固定为用一维方法求解,得固定为2>粗格子点法(疏密法):一般只收敛到局部最优解.为找到全局最优解,可同时选各个,…采用离散化方法计算.将矩形定义域划分成网格,然后在格点上计算等分个格点对每个k值,需计算的个值.计算量很大,且随着的增加迅速膨胀.分点维数维数灾难!粗格子点法:1)先用少数的格子点进行粗糙的计算,求出对应的最优解.2)在“最大”解附近的小范围内进一步细分,并求在细分格子点上的最优解.转1).可能导致漏掉全局最优解!应结合对指标函数的特性进行分析!3>Lagrange乘数法:引入Lagrange乘子,将二维问题转化为因为固定的参数,问题关于可分.为有意义→supposethat:(△)一维问题一维方程求解为最优解用插值法、优化中乘子法调整的取值Otherwise(△)的解可能不唯一.不妨设有m个最优解:可能出现下面几种情况:令:1>存在某一个k,使为最优解2>,则增大的值,重新求(△)3>,则减少的值,重新求(△)4>,且对所有的k,均有,则算法不适用!停止迭代.可考虑将Lagrange乘子法用于约束条件状态转移不能完全确定,它也许按某种已知的概率分布取值不确定性的多阶段问题由于随机因素称为随机性的决策过程采购问题：某厂生产上需要在近五周内必须采购一批原料,而估计在未来五周内价格会波动,其浮动价格和概率已测得如下表所示:试求在哪一周内以什么价格购入,使其采购价格的数学期望最小,并求出期望值.Scenario1

5000.3PriceProbScenario3

7000.4Scenario2

6000.3解:这里价格是一个随机变量,是按已知的概率分布取值的.按采购期限5周分为5个阶段,将每周的价格看作该阶段的状态.:状态变量,表示第k周的实际价格.:决策变量=1表示第k周决定采购0表示第k周决定等待:表示第k周决定等待,而在以后采取最优决策时采购价格的期望值.:表示第k周实际价格为时,从第k周至第5周采取最优决策所得的最小期望值.可写出逆序递推关系式为:其中由和的定义知:最优决策为:从最后一周开始,逐步向前递推计算,具体计算过程如下:即在第五周时,若所需的原料尚未买入,则无论市场价格如何,都必须采购,不能再等.k=5时,k=4时,500600610500600700500574=500=600or700500551.8=500=600or700500536.26