随机型动态规划问题课件.ppt

1、采购与销售问题两个决策变量情形两个决策变量情形运筹学课件v主主 讲：唐晓斌讲：唐晓斌v课件制作：何茂佳课件制作：何茂佳v小组成员：小组成员：v何茂佳何茂佳 20020440342002044034v唐晓斌唐晓斌 20020440512002044051v李李 良良 20020440572002044057v陈庆宇陈庆宇 20020440132002044013采采购购与与销销售售 某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来四个月的买卖价格如表7-12

2、所示,假定商店在1月开始经销时,仓库贮有该商品500单位.试问若不计库存费用,该商店应如何制定1月至4月的订购与销售计划,使预期获利最大。1281317 10911151234销售单位购买单位月份 kkckpv建立动态规划模型建立动态规划模型阶段k:按月份划分为4个阶段，K1，2，3，4 ：第K月定购的货物数量ky状态转移方程：kkkkxyss1ks状态变量 :第K月初时仓库中的存货量（含上月订货）决策变量 ：kx第K月卖出的货物数量)(kksf最优指标函数 ：第K月初存货量为 时，从第K月到4月末所获得最大利润。ks则有逆序递推关系式(基本方程)为：1,2,3,4k )()()(100000

3、max)(55110sfsfycxpxsysxsfkkkkkkkkkkkkkv建立动态规划模型建立动态规划模型当 K4 时1517max)(444434444)(100000yxsfxsysx显然，决策应取 ，4*4sx0*4y44417)(ssf最大值：v动态规划模型求解动态规划模型求解当 K3 时)(1113max)(4433)(1000003333333sfyxsfxsysx)(171113max 33333)(10000033333xysyxxsysx1764max 333)(10000033333syxxsysxv动态规划模型求解动态规划模型求解这个阶段需求解一个线性规划问题：010

4、00 x 1764max 3,333333333yxsxyssysz因为只有两个变量 ，可以用图解法，也可以用单纯形法，求解得到：3x3y1000,*33*3ysx时有最大值333136000)(ssfv动态规划模型求解动态规划模型求解当 K2 时)(98max)(222322)(1000002222222xysfyxsfxsysx)(13600098max 22222)(10000022222xysyxxsysx45136000max 222)(10000022222yxsxsysxv动态规划模型求解动态规划模型求解求解线性规划问题：0,1000 45136000max 2222222222

5、yxsxysxyxsz得：222229100044000136000)(ssssf2*3*31000,0syxv动态规划模型求解动态规划模型求解当 K1 时)1(1012max)(11211)(1000001111111xxsysxysfyxsf因为5001s)1(9100001012max)500(1111500050001111xxyxysyxf145003max 1150005000111yxxyx所以v动态规划模型求解动态规划模型求解0,500500314500max1111111yxxyxyxz解线性规划问题：得决策:16000500314500)500(,0,5001*1*1fyx

6、v动态规划模型求解动态规划模型求解最优策略见下表，最大利润为16000 月份期前存货售出量购进量 1 500 500 0 2 0 0 1000 3 1000 1000 1000 4 1000 1000 0kskxkyv动态规划模型求解结果动态规划模型求解结果随机型动态规划问题限期采购问题（随机型）限期采购问题（随机型）v运筹学第三小组运筹学第三小组v主 讲：江齐行（2002044052）v课件制作：潘日华（2002044039）v小组成员:）钟建生（学号：）江齐行（学号：）黄华德（学号：）潘日华（学号：2002044054200204405220020440322002044039别急嘛，让俺

7、先算一算再说。老总，此周买呼？例10 某部门欲采购一批原料，原料价某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该格在五周内可能有所变动，已预测得该种原料今后五周内取不同价格的概率如种原料今后五周内取不同价格的概率如下表所示。试确定该部门在五周内购进下表所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期这批原料的最优策略，使采购价格的期望值最小。望值最小。一次性采购。一次性采购。确定在五周内的确定在五周内的哪一周购进？哪一周购进？原料单价（元）概率5000.36000.37000.4称为均值。数学期望简称期望，又的数学期望值。的和为随机变量绝对收敛，则称若级数的分布

8、律为量定义：设离散型随机变XpxpxkpxXPXkkkkkkk113,2,1,解：解：阶段阶段k：可按采购期限（周）分为可按采购期限（周）分为5段，段，k=1,2,3,4,5.状态变量状态变量S K：第第k周的原料实际价格。周的原料实际价格。决策变量决策变量xk：第第k周如采购则周如采购则xk=1，若不，若不采购则采购则xk=0。另外用另外用S kE表示：表示：当第当第k周决定等待，而在周决定等待，而在以后采购时的采购价格期望值。以后采购时的采购价格期望值。最优指标函数最优指标函数f k(S K)：第第k周实际价格周实际价格为为S K时，从第时，从第k周至第周至第5周采取最优策略所周采取最优策

9、略所花费的最低期望价格。花费的最低期望价格。，为状态集合，逆序递推公式为：700600500)(1,2,3,4,min)(55555kkkkEkkkDDsssfkDsSssf)(1700 ,700)(1600 ,600)(1500 0,50)(*55*55*5555采购，当采购，当采购，当xsxsxssf 当当k=5时，因为前四周尚未购买，则无论本周时，因为前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以价格如何，该部门都必须购买，所以6107004.06003.05003.0)700(4.0)600(3.0)500(3.045554fffSkk时，由于当)(0700 610)(16

10、00 600)(1500 ,500610,min,min)(*44*44*444444444等待，当，采购，当，采购，当所以xsxsxssSssfEDs5746104.06003.05003.0)700(4.0)600(3.0)500(3.034443fffSkk时，当)(0700600 574)(1500 ,500574,min,min)(*33*333333333等待，或当，采购，当xsxssSssfEDs)(07006008.551)(1500 ,5008.551,min,min)(2*22*222222222等待，或，当采购，当时，同理可得当xsxssSssfkEDs)(0700600

11、26.536)(1500 ,50026.536,min,min)(1*11*111111111等待，或，当采购，当时，则当xsxssSssfkEDs 所以，容易得最优策略为：若前面所以，容易得最优策略为：若前面三周原料价格为三周原料价格为500500，则立即采购，否则，则立即采购，否则在以后的几周内再采购。若第四周的价在以后的几周内再采购。若第四周的价格为格为500500或或600600，则立即采购，否则等待，则立即采购，否则等待第五周再采购。而第五周无论当时的价第五周再采购。而第五周无论当时的价格为多少都必须采购。格为多少都必须采购。所以，按以上策略进行所以，按以上策略进行采购，期望价格为：采购，期望价格为：525382.52526.5364.026.5363.05003.0)700(4.0)600(3.0)500(3.0)(11111fffsf题的相关习题请看课本13.7217P？OK!