随机型动态规划问题课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,采购与销售问题,两个决策变量情形,采购与销售问题两个决策变量情形,1,运筹学课件,主 讲：唐晓斌,课件制作：何茂佳,小组成员：,何茂佳 2002044034,唐晓斌 2002044051,李 良 2002044057,陈庆宇 2002044013,运筹学课件主 讲：唐晓斌,2,采购与销售,某商店在未来的4个月里,准备用它的一个仓库来专门经销某种商品,仓库最大容量能贮存这种商品1000单位.假定该商店每月只能出卖仓库现有的货,当商店在某月购货时,下月初才能到货.预测该商品未来四个月的买卖价格如表7-12所示,假定商店在1月开始经销时,仓库贮有该商品500单位.试问若不计库存费用,该商店应如何制定1月至4月的订购与销售计划,使预期获利最大。,12,8,13,17,10,9,11,15,1,2,3,4,销售单位,购买单位,月份,k,采购与销售 某商店在未来的4个月里,准备用它的,3,建立动态规划模型,阶段k:按月份划分为4个阶段，,K1，2，3，4,：第K月定购的货物数量,状态转移方程：,状态变量 :,第K月初时仓库中的存货量（含上月订货）,决策变量 ：,第K月卖出的货物数量,最优指标函数 ：第K月初存货量为 时，从第K月到4月末所获得最大利润。,建立动态规划模型阶段k:按月份划分为4个阶段，K1，2,4,则有逆序递推关系式(基本方程)为：,建立动态规划模型,则有逆序递推关系式(基本方程)为：建立动态规划模型,5,当 K4 时,显然，决策应取 ，,最大值：,动态规划模型求解,当 K4 时显然，决策应取 ，最,6,当 K3 时,动态规划模型求解,当 K3 时动态规划模型求解,7,这个阶段需求解一个线性规划问题：,因为只有两个变量 ，,可以用图解法，也可以用单纯形法，求解得到：,时有最大值,动态规划模型求解,这个阶段需求解一个线性规划问题：因为只有两个变量,8,当 K2 时,动态规划模型求解,当 K2 时动态规划模型求解,9,求解线性规划问题：,得：,动态规划模型求解,求解线性规划问题：得：动态规划模型求解,10,当 K1 时,因为,所以,动态规划模型求解,当 K1 时因为所以动态规划模型求解,11,解线性规划问题：,得决策:,动态规划模型求解,解线性规划问题：得决策:动态规划模型求解,12,最优策略见下表，最大利润为16000,月份,期前存货,售出量,购进量,1,500,500,0,2,0,0,1000,3,1000,1000,1000,4,1000,1000,0,动态规划模型求解结果,最优策略见下表，最大利润为16000 月份期前存货售出,13,随机型动态规划问题,限期采购问题（随机型）,随机型动态规划问题限期采购问题（随机型）,14,运筹学第三小组,主 讲：,江齐行（2002044052）,课件制作：,潘日华（2002044039）,小组成员:,运筹学第三小组,15,别急嘛，让俺先算一算再说。,老总，此周买呼？,别急嘛，让俺先算一算再说。老总，此周买呼？,16,例10,某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同价格的概率如下表所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的期望值最小。,一次性采购。,确定在五周内的哪一周购进？,例10 某部门欲采购一批原料，原料价格在五周内可能有所变,17,原料单价（元）,概率,500,0.3,600,0.3,700,0.4,原料单价（元）概率5000.36000.37000.4,18,这里，有可能要对数学期望做一下说明。,这里，有可能要对数学期望做一下说明。,19,解：,阶段k：,可按采购期限（周）分为5段，k=1,2,3,4,5.,状态变量S,K,：,第k周的原料实际价格。,决策变量x,k,：,第k周如采购则x,k,=1，若不采购则x,k,=0。,另外用S,kE,表示：,当第k周决定等待，而在以后采购时的采购价格期望值。,最优指标函数f,k,(S,K,)：,第k周实际价格为,S,K,时，从第k周至第5周采取最优策略所花费的最低期望价格。,解：,20,随机型动态规划问题课件,21,当k=5时，因为前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以,当k=5时，因为前四周尚未购买，则无论本周价格,22,随机型动态规划问题课件,23,随机型动态规划问题课件,24,随机型动态规划问题课件,25,所以，容易得最优策略为：若前面三周原料价格为500，则立即采购，否则在以后的几周内再采购。若第四周的价格为500或600，则立即采购，否则等待第五周再采购。而第五周无论当时的价格为多少都必须采购。,所以，容易得最优策略为：若前面三周原料价格为5,26,所以，按以上策略进行采购，期望价格为：,所以，按以上策略进行采购，期望价格为：,27,？,？,OK!,OK!,