动态规划应用举例

2020/5/11,1,资源分配问题生产与存贮问题设备更新问题,动态规划应用举例,2020/5/11,2,6.3资源分配问题,6.3.1一维离散资源分配问题设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？,将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使目标函数为最优。,2020/5/11,3,决策集合：Dk(sk)=uk|0uk=xksk,uk:分配给生产第k种产品的原料数量，即uk=xk；,sk:分配给用于生产第k种至第n种产品的原料数量；,状态转移方程：sk+1=sk-uk=sk-xk,最优值函数fk(sk):数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：,2020/5/11,4,工业部拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,例1,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。,逆推法,2020/5/11,5,k=3时，0s35，0x3s3,可分配的机器数量,分配的机器数量,S3=?,=4,x3*(1)=1,x3*(0)=0,=max,x3=0,1,2020/5/11,6,2020/5/11,7,2020/5/11,8,当阶段k=2时，s3=s2-x2，0s25，0x2s2，有,2020/5/11,9,2020/5/11,10,2020/5/11,11,2020/5/11,12,结果列于下表：,f3(1-0)=f3(1),=4,f3(5-3)=f3(2),2020/5/11,13,当阶段k=1时，s2=s1-x1，s1=5，0x1s1，有,x1*(5)=0,2,2020/5/11,14,结果可写成表格的形式,max,逆推到第一张表,2020/5/11,15,x3*=3,x2*=2,2020/5/11,16,按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配0台，乙工厂分配2台,丙工厂分配3台。,甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元,问题：如果原设备台数是4台，求最优分配方案？如果原设备台数是3台，求最优分配方案？,2020/5/11,17,6.3.2一维连续资源分配问题:一般问题的提法是,如此进行n年，如何确定投入A的资源量u1、un，使总收入最大？,2020/5/11,18,此问题的静态规划问题模型为：,动态规划的逆推关系方程为：,最后求得f1(s1)即为所求问题的最大收入。,2020/5/11,19,例2机器负荷分配问题,解：设阶段数k表示年度。,试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。,低负荷下生产的机器台数是sk-uk。,2020/5/11,20,第k年度产量为,2020/5/11,21,u5*=s5,f5(s5)=8s5,u4*=s4,f4(s4)=13.6s4,2020/5/11,22,依次类推可得，u3*=s3f3(s3)=17.5s3u2*=0f2(s2)=20.8s2u1*=0f1(s1)=23.7s1,最高产量为23700。,因此最优策略为:u1*=0,u1*=0,u3*=s3,u4*=s4u5*=s5,u5*=s5,f5(s5)=8s5,u4*=s4,f4(s4)=13.6s4,2020/5/11,23,作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？,2020/5/11,24,在生产和经营管理中，经常遇到要合理安排生产（或购买）与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用。因此，正确指定生产（或采购）策略，确定不同时期的生产量（或购买量）和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标。,设某公司对某种产品要制定一项n个阶段的生产计划。已知它的初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产计划，从而使总成本最小？,第二节生产与存贮问题,2020/5/11,25,用动态规划方法来求解，把它看作一个n阶段决策问题。令：sk为状态变量，它表示第k阶段开始时的库存量。xk为决策变量，它表示第k阶段的生产量。则状态转移方程为：sk+1=sk+xk-dk第k阶段的成本费用包括生产成本和存贮费用两项：,2020/5/11,26,Ck(xk)表示第k阶段生产产品xk时的成本费用，包括生产准备成本k和产品成本axk（其中a为单位生产成本）,hk(xk)表示在第k阶段结束时库存量所需的的费用。,最优值函数fk（sk）表示从第k阶段初库存量为sk到第n阶段末库存量为0时的最小总费用。则基本方程为:,(k=n,n-1，,1),2020/5/11,27,其中。这是因为一方面每阶段生产的上限为m；另一方面保证第n阶段结束时库存量可以取0。而这是因为为了保证第k阶段能满足需求。,2020/5/11,28,例：某工厂生产并销售某种产品，已知今后4个月市场需求预测如表所示。并且有如下假定：固定成本为3千元，若不生产就为0；每单位产品成本为1千元；每个月生产能力所允许的最大生产批量为不超过6个单位；每个月末未售出的产品，每单位需付存储费0.5千元。还假定在第一个月的初始库存量为0，第四个月末的库存量也为0。问：如何安排各月的生产与库存，使总成本最小。,2020/5/11,29,用动态规划方法来求解：按四个月份将问题分为四个阶段，则在第k月的生产成本为：,2020/5/11,30,第k时期末库存量为sk+1时的存储费用为，故第k时期内的总成本为，而动态规划的基本方程为：,（k4，3，2，1）,其中,2020/5/11,31,下面从最后一个阶段开始向前逆推计算。当k=4时，s40，1，2，3，4，由于第4月末的库存量为0，第4阶段的生产量x4必为x4=d4-s4，其计算如下表：,2020/5/11,32,当k3时，由于第三、第四阶段的需求量分别为2、4，为了保证最后库存量能取0，s3的允许状态集合为0，1，2，3，4，5，6而，其中，。其计算如下表：,2020/5/11,33,2020/5/11,34,当k=2时，由于第一阶段的需求为2，而每阶段的最大生产能力为6，S2的最大取值为4，因此s20，1，2，3，4，而，其中，。其计算如下表：,2020/5/11,35,2020/5/11,36,当k1时，s1=0，。其计算如下表所示。,再按计算的顺序反推算，可找出每个月的最优生产决策为：其相应的最小总成本为20.5千元。,2020/5/11,37,个人、单位等随时均有设备更新问题。彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。,设备更新问题提法如下（以一台机器为例）：n为计划设备使用年数。Ik(t)为第k年（阶段）机器役龄为t年的一台机器运行（再使用一年）所得的收入。Ok(t)为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。Ck(t)为第k年机器役龄为t年的一台机器更新时所需更新的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。,第三节设备更新问题,2020/5/11,38,建立动态规划模型如下：阶段k（k=1，2，n）表示计划年限数。状态变量sk：第k年初，设备已使用过的年数，即役龄。决策变量xk：是第k年初更新（Replacement），还是保留使用（Keep）旧设备，分别用K，R表示。状态转移方程为：,阶段效益为：,为折扣因子，表示一年以后的收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？,2020/5/11,39,最优指标函数gk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为,实际上,2020/5/11,40,例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（