运筹学—第七章-动态规划.pptVIP

因为s1=100，所以f1（100）=2680，逆向追踪得： x1*=0 s1=100 x2*=0 x3*=s3=81 x4*=s4=54 第1，2期把全部完好机器投入低负荷下生产，第3，4期把全部完好机器投入高负荷下生产所得利润最大。 二、生产计划问题 例7.9 （生产—库存问题） 某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为2，3，2，4单位，假设每批产品固定成本为3千元，若不生产为0，每单位产品成本为1千元，每个时期最大生产能力不超过6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假定第1期初和第4期末库存量均为0，问该厂如何安排生产与库存，可在满足市场需求的前提下总成本最小。 解 以每个时期作为一个阶段，k=1，2，3，4； 决策变量xk表示第k阶段生产的产品数； 状态变量sk表示第k阶段初的库存量； 以dk表示第k阶段的需求，则状态转移方程： sk+1=sk+xk－dk k=4，3，2，1 s1=0，s5=0； 允许决策集合Dk（sk）的确定： xk的下限为max（0，dk－sk）； xk的上限为min（ ，6），故有： Dk（sk）=｛xk| max（0，dk－sk）≤xk≤min（ ，6）｝ 阶段指标函数rk（sk，xk）表示第k期的生产费用与存贮费用之和： 最优指标函数fk（sk）表示第k期库存为sk到第4期末的生产与存贮最低费用，动态规划基本方程为： 例7-9 （库存—销售问题） 设某公司计划在1至4月份从事某种商品经营。已知仓库最多可存储600件这种商品，已知1月初存货200件，根据预测知1至4月份各月的单位购货成本及销售价格如表7-13所示，每月只能销售本月初的库存，当月进货供以后各月销售，问如何安排进货量和销售量，使该公司四个月获得利润最大（假设四月底库存为零）。 44 42 4 39 40 3 42 38 2 45 40 1 销售价格P 购货成本C 月份 解 按月份划分阶段，k=1，2，3，4； 状态变量sk表示第k月初的库存量，s1=200，s5=0； 决策变量 xk表示第k月售出的货物数量， yk表示第k月购进的货物数量； 状态转移方程：sk+1=sk+yk－xk； 允许决策集合：0≤xk≤sk，0≤yk≤600－（sk－xk）； 阶段指标函数为：pkxk－ckyk表示k月份的利润，其中pk为第k月份的单位销售价格，ck为第k月份的单位购货成本； 最优指标函数fk（sk）表示第k月初库存为sk时从第k月至第4月末的最大利润，则动态规划基本方程为： * 第七章 动态规划 第一节 多阶段决策问题 例7.1 最短路问题 如图所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？ 3 5 2 5 6 3 2 1 7 3 7 5 6 2 2 5 4 3 2 1 B1 A B2 B3 C1 C2 C3 C4 E D2 D1 例7-2 机器负荷问题 某工厂有100台机器，拟分四个周期使用，在每一个周期有两种生产任务。据经验，把机器x1台投入第一种生产任务，则在一个生产周期中将有1/3台机器报废；余下的机器全部投入第二种生产任务，则有1/10的机器报废，如果干第一种生产任务每台机器可以收益10，干第二种生产任务每台机器可以收益7，问怎样分配机器使总收益最大？ ? 例7-3 资源分配问题 假设有一种资源其数量为a，现将它分配给n个使用者。若分配给第i个使用者的数量为xi（i=1，…，n），产生的相应收益为gi（xi），问如何分配使总收益最大？ 投资决策问题、生产存贮问题、采购问题、设备更新问题等都具有多阶段决策问题的特征，都可以用动态规划方法求解。 第二节 动态规划的基本概念和基本原理 ?一、动态规划的基本概念 1.阶段（stage） 描述阶段的变量称为阶段变量（k） k=1，A——B； k=2，B——C； k=3，C——D； k=4，D——E。 2.状态（state） 状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。 描述状态的变量称为状态变量（sk) 。 状态变量sk的取值集合称为状态集合，第k阶段的状态集合记为Sk ， 3 5 2 5 6 3 2 1 7 3 7 5 6 2 2 5 4 3 2 1 B1 A B2 B3 C1 C2 C3 C4 E D2 D1 状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通过