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

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