第13讲 确定型动态规划.ppt

第八章 动态规划 动态规划模型分类 第14讲 确定型性动态规划 (6.2) 最短路问题 资源分配问题 生产与存储问题 动态规划和静态规划的关系 自学背包问题、排序问题、货郎担问题 资源分配问题 (6.2.2) 资源分配问题： 把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。 资源可以有一种或若干种， 只有一种资源可供分配的问题称之为一维资源分配问题。 例1：某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。 动态规划的数学模型 将三个分厂看作是三个阶段，即阶段变量 k=1,2,3; 状态变量sk 表示第k 阶段初可分配的设备台数,0≤sk ≤5; 决策变量xk 表示第k 阶段分配给分厂k 的设备台数， 允许决策集合Xk (sk)={ xk ︱0≤ xk ≤sk}; 状态转移方程为 sk+1 = sk - xk ; 阶段指标Pk(sk, xk) 表示第k 阶段从sk台设备中分配给k 分厂xk 台设备的阶段效益; 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略取得的最大的效益值; 递推方程函数式 第三阶段：设将S3台设备（S3＝0,1,2,3,4,5）全部分配给丙厂时，最大盈利值为： f3(S3)＝max[P3(X3)] 其中X3＝S3＝0,1,2,3,4,5 X3*表示使得f3(S3)为最大值时的最优决策。 第二阶段：设将S2台设备（S2＝0,1,2,3,4,5）分配给乙厂和丙厂时，对每一个S2值，都有一种最优分配方案，使得最大盈利值为：f2(S2)＝max[ P2(X2)+ f3(S2－X2) ] ，X2＝0,1,2,3,4,5 第一阶段：设将S1台设备（S1＝5）分配给甲厂、乙厂和丙厂时，则最大盈利值为：f1(S1)＝max[ P1(X1)+ f2(5－X1) ]其中，X1＝0,1,2,3,4,5 例2 机器负荷问题——某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量S1＝1000台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。 动态规划的数学模型 每年为一个阶段，即阶段变量 k=1,2,3,4,5; 状态变量sk 表示第k年初所拥有的完好机器台数，s1 =1000; 决策变量uk 表示第k年投入高负荷生产的机器数 ， 允许决策集合Uk (sk)={ uk ︱0≤ uk ≤ sk}; sk－uk表示为第k年初分配在低负荷下生产的机器数量。 状态转移方程为 sk+1 =auk +b(sk–uk ) =0.7uk+0.9(sk–uk) =0.9sk – 0.2uk; 阶段指标vk(sk, xk) 表示第k年的产量 ：vk(sk,uk) = 8uk +5(sk–uk )=5sk +3uk ; 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略实现的最大产量; K=4 K=2 最优生产策略：u*1 =0 ， u*2 =0 ， u*3 =s3 ，u*4 =s4 ，u*5 =s5 各阶段状态： s1 =1000， u*1 =0， s2 = 0.9s1 – 0.2u1 = 0.9s1 =900， u*2=0， s3 = 0.9s2 – 0.2u2 = 0.9s2 =810， u*3= s3 ， s4 = 0.9s3 – 0.2u3 = 0.7s3 =576， u*4= s4 s5 = 0.9s4 – 0.2u4 = 0.7s4=397 ， u*5= s5 s6 = 0.9s5 – 0.2u5 = 0.7s5=278 生产存储问题 (6.2.3) 企业一年中的产品生产往往是分期分批生产的。 组织每批产品的生产，都要花费一些生产准备费和存贮费用。 若某一时期增大生产批量则可减少生产批次，从而降低生产成本。 与此同时，批量大了，必然增加库存而使存贮费用增加。 在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。 1、生产计划问题： 例3 某工厂要对一种产品制订今后四个时期的生产计划，据估计在今