运筹学生产与存储问题

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