运筹学生产与存储问题

动态规划应用,生产与存储问题,汇报人：郭营指导老师：甘老师,2015年5月25日,前言,动态规划三要素：阶段，状态，决策。如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。,在生产和经营管理中，经常遇到要合理地安排生产(或购买)与库存的问题，达到既要满足社会的需要又要尽量降低成本费用。因此，正确制定生产(或采购)策略，确定不同时期的生产量(或采购量)和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存贮问题的最优化目标。,生产计划问题,大批量生产可以降低成本，但当产量大于销量时就会造成产品积压而增加库存费用；单纯按市场要求安排生产也会因为开工不足或加班加点造成生产成本增加。因此合理利用存贮资源调节产量，满足要求是十分有意义的。,现设有一个生产部门，生产计划周期为n个阶段，已知最初库存量为，阶段需求量为，单位产品的消耗费用是，单位产品的阶段库存费用为，仓库容量为，阶段生产能力为，生产固定成本为。问如何安排现阶段的产量，使计划期内的费用综合为最小？,该问题本身就是一个多阶段决策问题，设状态变量为为k阶段初的库存量，由于计划期初的库存量已知，计划期末的库存量通常也是给定的，为简单起见，假定=0，于是状态变量的约束条件是：决策变量uk选为阶段k的产量，它满足的约束条件是：状态转移方程为，它满足无后效性的要求。,阶段效用由两阶段组成，一部分为生产费用，另一部分为存贮费用，即：动态规划基本方程为：,某机床厂根据合同，在一至四月份为客户生产某种机床。工厂每月的生产能力为10台，机床可以库存，存储费用为每台每月0.2万元，每月需要的数量及每台机床的生产成本如下表。试确定每月的生产量，要求既能满足每月的需求，又能使生产成本和存储费用之和达到最小,3.逆序逆推计算又x5=0，d4=6所以有x4+u4=6又因为每个月的最大生产能力为10台。第1，2，3月的需求量为6，7，12台，故x4=0，1，2，3，4，5台,表1k=4时,表3k=2,4、k=1时确定x1的取值范围X1=0确定u1的取值范围因为d1=6，x1=0。故6u110所以u1=10，9，8，7，6,表4k=1,综上所述，该生产与存储问题的最优化安排是：第1个月生产10台，费用为70万元；第2个月生产10台，费用为72.8万元；第3个月生产5台，费用为41.4万元；第4个月生产6台，费用为45.6万元。一至四月的生产与存储费用最小为229.8万元。,不确定性的采购问题,在实际问题中，还遇到某些多阶段决策过程，不是像前面所讨论的确定性那样，状态转移是完全确定的，而是出现些随机性因素，状态转移不能完全确定，它是按照某种已知的概率分布取值的。具有这种性质的多阶段决策过程就称为随机性的决策过程。用动态规划的方法可处理这种随机性问题，又称随机性动态规划。,例：某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概率如下表。试确定该部门在五周内购进这批原料的最优策略，使采购价格得期望值最小。,解：阶段k：按采购期限（周）分为5段，k1，2，3，4，5状态变量Sk：第k周的原料实际价格决策变量Xk：第k周若采购则xk1，若不采购xk0 xk为01变量skE：当第k周决定等待，而