十动态规划的应用---资源分配问题课件PPT12.ppt

设有某种原料，总数量为 a，用于生产 n 种产品若分配数量 xi 用于生产第 i 种产品，其收益为 gi ( xi )，问应如何分配，才能使生产 n 种产品的总收入最大？,资源分配问题,1 资源平行分配问题,静态规划模型,,不考虑回收,例3 某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表 问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大如何划分阶段,,s1的可达状态集合,s2的可达状态集合,s3的可达状态集合,,,,,,,,,决策变量 uk(sk),0 sk,3个阶段,xk,状态转移方程？,s1,s2,s3,3,2,1,,,,,x1,x2,x3,,,,基本方程?,指标函数gk(xk)?,s4,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3决策变量xk::,分配给生产第 k 个工厂的设备数量,分配给第 k 个工厂至第 3 个工厂的设备数量（第k阶段开始剩余的设备数量）状态变量 sk :,Dk ( sk )= uk|0uk= xk sk ,基本方程：,数量为 sk 的设备分配给第 k 个工厂至第 3 个工厂所得到的最大总收益,,,,状态转移方程:,sk+1 = sk - xk,xk的取值范围？,x3*(0) = 0,x3*(1) = 1,x3*(2) = 2,x3*(3) = 3,k =3，s3=0,1,2,3,4,5，0 x3 s3,s3 = 0,s3 = 3,0 4 6 11 12 12,s3 = 2,s3 = 1,x3*(5) = 4,5,x3*(4) = 4,0 4 6 11 12 12,结果可写成表格的形式:,s3 = 4,s3 = 5,k =2，s3 = s2 - x2，s2=0,1,2,3,4,5，0 x2 s2，有,x2*(0) = 0,s2 = 0,,,,,,x2*(1) =1,s2 = 1,x2*(2) =2,s2 = 2,x2*(3) =2,s2 = 3,x2*(4) =1,2,s2 = 4,s2 = 5,x2*(5) =2,结果列于下表：,k =1时， s2 = s1 - x1， s1 = 5， 0 x1 s1，有,,x1*(5) =0,2,结果可写成表格的形式,最优分配方案一：由 x1* = 0，根据 s2 = s1- x1* = 5- 0 = 5，查表知 x2* = 2，由s3 = s2- x2* = 5 - 2 = 3，故 x3* = s3 =3。

即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台最优分配方案？,最优分配方案二：由 x1* = 2，根据 s2 = s1 - x1* = 5- 2 = 3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台以上两个分配方案所得到的总盈利均为21万元问题： 如果原设备台数是4台，求最优分配方案？ 如果原设备台数是3台，求最优分配方案？,设备台数是4台，,,最优分配方案一：由 x1* = 1，根据 s2 = s1 - x1* = 4- 1 = 3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1即得甲工厂分配1台，乙工厂分配2台，丙工厂分配1台，总盈利为17万元最优分配方案二：由 x1* = 2，根据 s2 = s1 - x1* = 4- 2 = 2，查表知 x2*= 2，由 s3 = s2 - x2*= 2 - 2 =0，故 x3* = s3 =0即得甲工厂分配2台，乙工厂分配2台，丙工厂分配0台，总盈利为17万元设备台数是3台，,,,最优分配方案一：由 x1* = 0，根据 s2 = s1 - x1* = 3- 0 = 3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1。

即得甲工厂分配0台，乙工厂分配2台，丙工厂分配1台，总盈利为14万元2 资源连续分配问题,如此进行 n 年，如何确定投入 A 的资源量 u1、、un，使总收入最大？,此问题的静态规划问题模型为：,高负荷: 产量函数 g = 8x， 年完好率为 a=0.7，,,机器,例4 机器负荷分配问题,假定开始生产时完好机器的数量为1000台低负荷: 产量函数 h = 5y， 年完好率为 b=0.9试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高?,投入生产的机器数量,,,状态变量 sk,状态转移方程,决策(变量) uk,第 k 年初拥有的完好机器台数,第 k 年高负荷下投入的机器数,sk+1 = auk+ b(sk - uk) = 0.7uk+ 0.9 (sk - uk),0 uk sk,分析：,,第 k 年低负荷下投入的机器数,sk uk,,,,阶段？,动态规划基本（递推）方程？,指标函数,第k年度产量为,k = 5, 4, 3, 2, 1,,,,sk+1,,,阶段指标,f6(s6) = 0,则状态转移方程为,sk+1 = 0.7uk+ 0.9 (sk - uk) k = 1, 2, , 5,解：设阶段序数 k 表示年度，sk为第 k 年初拥有的完好机器台数，第 k 年度高负荷下投入的机器数为uk台。

基本方程为,f4(s4) = 13.6s4,u*4 = s4,k = 4,u*5 = s5,k = 5,f5(s5) = 8s5,,,0,依此类推可得，,因此最优策略为,最高产量为23700问题：1. 每年年初的完好机器数 2. 如规定在第五年结束时完好机器数为500台，该如何安排生产？,问题：1. 求每年年初的完好机器数,始端固定终端自由的最优策略,k = 4,k = 5,,2. 如规定在第五年结束时完好机器数为500台，该如何安排生产？,。