《规划数学 确定型动态规划PPT》由会员分享，可在线阅读，更多相关《规划数学 确定型动态规划PPT（69页珍藏版）》请在金锄头文库上搜索。
1、第八章 动态规划,1,建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量Sk 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量Uk及允许决策集合Dk 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,第八章 动态规划,2,4、确定状态转移方程Sk+1=Tk(Sk,Uk)
2、 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、正确写出指标函数Vk,n的关系，它应满足下面三个性质： Vk,n是定义在全过程和所有后部子过程上的数量函数 具有可分离性，并满足递推关系，即Vk,n(Sk,Uk ,Sk1,Sn+1)=k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1) 函数k（Sk，Uk ，Vk1,n）对于变量Vk1,n要严格单调。 6、恰当地定义最优指标函数 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值。,第八章 动态规划,3,动态规划模型分类,7、写出恰当的边界条件
3、，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优解，并找到相应的最优策略。,第6章 动态规划,动态规划的基本理论 （2学时） 确定型动态规划 （2学时） 随机型动态规划 （1学时） 动态规划的软件计算 （1学时）,第14讲 确定型性动态规划 (6.2),最短路问题 资源分配问题 生产与存储问题 动态规划和静态规划的关系 自学背包问题、排序问题、货郎担问题,资源分配问题： 把有限的资源(如资金、材料、设备、人力等)分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。 资源可以有一种或若干种
4、， 只有一种资源可供分配的问题称之为一维资源分配问题。,资源分配问题 (6.2.2),例1：某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。,1、一维资源分配问题,动态规划的数学模型 将三个分厂看作是三个阶段，即阶段变量 k=1,2,3; 状态变量sk 表示第k 阶段初可分配的设备台数,0sk 5; 决策变量xk 表示第k 阶段分配给分厂k 的设备台数， 允许决策集合Xk (sk)= xk 0 xk sk; 状态转移方程为 sk+1 = sk
5、- xk ; 阶段指标Pk(sk, xk) 表示第k 阶段从sk台设备中分配给k 分厂xk 台设备的阶段效益; 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略取得的最大的效益值; 递推方程函数式,第三阶段：设将S3台设备（S30,1,2,3,4,5）全部分配给丙厂时，最大盈利值为： f3(S3)maxP3(X3) 其中X3S30,1,2,3,4,5 X3*表示使得f3(S3)为最大值时的最优决策。,逆序求解,表91,第二阶段：设将S2台设备（S20,1,2,3,4,5）分配给乙厂和丙厂时，对每一个S2值，都有一种最优分配方案，使得最大盈利值为：f2(S2)max P
6、2(X2)+ f3(S2X2) ，X20,1,2,3,4,5,表92,第一阶段：设将S1台设备（S15）分配给甲厂、乙厂和丙厂时，则最大盈利值为：f1(S1)max P1(X1)+ f2(5X1) 其中，X10,1,2,3,4,5,按计算表格的顺序反推，可知最优分配方案有两个： 1）由X1*0，S2S1X1*505。再由表92，可知X2*2。S3S2X2*523，故X3*S33。即得甲厂分得0台，乙厂分得2台，丙厂分得3台。 2）由X1*2，S2S1X1*523。再由表92，可知X2*2。S3S2X2*321，故X3*S31。即得甲厂分得2台，乙厂分得2台，丙厂分得1台。 以上两种最优方案的总
7、盈利均为21万元。,例2 机器负荷问题某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率为a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好的机器数量S11000台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。,2、资源连续分配问题,动态规划的数学模型 每年为一个阶段，即阶段变量 k=1,2,3,4,5; 状态变量sk 表示第k年初所拥有的完好机器台数，s1 =1000; 决策变量uk 表示第k年投入高负荷生产的机器数 ， 允许
8、决策集合Uk (sk)= uk 0 uk sk; skuk表示为第k年初分配在低负荷下生产的机器数量。 状态转移方程为 sk+1 =auk +b(skuk ) =0.7uk+0.9(skuk) =0.9sk 0.2uk; 阶段指标vk(sk, xk) 表示第k年的产量 ：vk(sk,uk) = 8uk +5(skuk )=5sk +3uk ; 最优指数函数fk(sk)表示第k阶段从sk 开始到最后阶段采用最优分配策略实现的最大产量;,解：,K=5,从第5阶段开始，向前逆推计算,f5(s5)是关于u5 的单增函数，故u*5 =s5 时，f5(s5)最大， f5(s5)=8 s5,K=4,f4(s
9、4)是关于u4 的单增函数，故u*4 =s4 时， f4(s4)=13.6 s4,K=3,f3(s3)是关于u3 的单增函数，故u*3 =s3 时， f3(s3)=17.52 s3,K=2,f2(s2)是关于u2 的单调减函数，故u*2 =0 时， f2(s2)=20.8 s2,依次类推，可求得： u1*0，f1(s1)23.7 s1,最优生产策略：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
10、= 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,即前两年应把年初全部完好的机器投入低负荷下生产，后三年应把年初全部完好的机器投入高负荷下生产。这样最高产量为23700台。,企业一年中的产品生产往往是分期分批生产的。 组织每批产品的生产，都要花费一些生产准备费和存贮费用。 若某一时期增大生产批量则可减少生产批次，从而降低生产成本。 与此同时，批量大了，必然增加库存而使存贮费用增加。 在
11、企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。,生产存储问题 (6.2.3),1、生产计划问题： 例3 某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产品的固定成本为3千元，若不生产就为0，每单位产品成本为1千元，每个时期生产能力所允许的最大生产批量为不超过6个单位，每个时期末未售出的产品，每单位需付存货费0.5千元。还假定在第一个时期的初始库存量为0，第四个时期之末的库存量也为0。试问：该厂应如何安排各个时期的生产与库存，才能在满足
12、市场需求的条件下，总成本最小。,动态规划的数学模型 该问题分成四个阶段，k表示年度，k1，2，3，4; 状态变量sk-1表示为第k年初的库存量，第k1年末的库存量。 决策变量uk 表示为第k年的生产量，dk表示为第k年的需求量。 允许决策集合Dk(sk)= uk 0 uk 6 状态转移方程为 sk =sk-1+ukdk;s00; s40 第k年的生产成本为：,解：,第k期末库存量为sk的存贮费用为: hk(sk)=0.5 sk 总成本为:ck(uk)hk(sk) fk(sk)表示由第1年的初始库存为0到第k年末的库存为Sk的最小总成本。,fk(sk)min ck(uk)hk(sk)fk-1(s
13、k-1) min ck(uk)hk(sk)fk-1(skdkuk) k=1,2,3,4 边界条件f0(s0)0,写出顺序递推关系式：,由于库存量必须非负, sk-1 skdkuk , ukskdk uk6 , 所以ukmin skdk，6,f1(s1)min c1(u1)h1(s1) f0(s0),s1 s0 +u1d1 d1=2 s10，u12，f1(0)5 s11，u13，f1(1)6.5 s12，u14，f1(2)8,对s1 9 之间的值分别进行计算。,k1,s13，u15，f1(3)9.5 s14，u16，f1(4)11,f2(s2)min c2(u2)h2(s2)f1(s2d2u2)
14、,k2,其中，u2min s23，6,s21，f2(1)min c2(u2)h2(1)f1(4u2),对s2 6 之间的值分别进行计算。,s20，f2(0)min c2(u2)h2(0)f1(3u2),u2=0,f2(0)9.5 u2=0,u2=0,f2(1)11.5，u2=0,s22，f2(2)min c2(u2)h2(2)f1(5u2) 14，u2=5 s23，f2(3)min c2(u2)h2(3)f1(6u2) 15.5，u2=6 s24，f2(4)min c2(u2)h2(4)f1(7u2) 17.5，u2=6 s25，f2(5)min c2(u2)h2(5)f1(8u2) 19.5
15、，u2=6 s26，f2(6)min c2(u2)h2(6)f1(9u2) 21.5，u2=6,f3(s3)min c3(u3)h3(s3)f2(s3d3u3) 其中，u3min s32，6 s3在0至d44之间,k3,s30，f3(0)minc3(u3)h3(0)f2(2u3),u3=0,s31，f3(1)min c3(u3)h3(1)f2(3u3) 16 u3=0,3 s32，f3(2)min c3(u3)h3(2)f2(4u3) 17.5 u3=4 f3(0)14 u3=0； f3(1) 16 u3=0,3； f3(2)17.5 u3=4 f3(3)19 u3=5,所以，u4=0，u3=
16、6，u2=0，u1=5, 最小总成本为20.5千元,f4(s4)min c4(u4)h4(s4)f3(s4d4u4) 其中，u4min s44，6 s40,k4,f4(0)min c4(u4)h4(0)f3(4u4),u4=0,f3(4)20.5 u3=6,例4：某车间需要按月在月底供应一定数量的某种部件给总装车间，由于生产条件的变化，该车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时数如下表所示。 设仓库容量限制为H=9，开始库存量为2，期终库存量为0，要求制定一个半年的逐月生产计划，既使得满足需要和库容量的限制，又使得生产这种部件的总耗费工时数为最少。,动态规划的数学模型 该问题分成六个阶段，k表示月份，k1,2,3,4,5,6 设sk表示为第k月初的库存量，第k1月末的库存量。 uk表示为第k月的生产量，dk表示为第k
