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

1、设有某种原料，总数量为 a，用于生产 n 种产品。若分配数量 xi 用于生产第 i 种产品，其收益为 gi ( xi )，问应如何分配，才能使生产 n 种产品的总收入最大？,资源分配问题,1 资源平行分配问题,静态规划模型,不考虑回收,1,例3 某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,2,如何划分阶段,s1的可达状态集合,s2的可达状态集合,s3的可达状态集合,决策变量 uk(sk),0 sk,3个阶段,xk,状态转移方程？,3,s1,s2,s3,3,2,1,x1,x2,

2、x3,基本方程?,指标函数gk(xk)?,s4,4,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。,决策变量xk:,分配给生产第 k 个工厂的设备数量,分配给第 k 个工厂至第 3 个工厂的设备数量（第k阶段开始剩余的设备数量）。,状态变量 sk :,5,Dk ( sk )= uk|0uk= xk sk ,基本方程：,数量为 sk 的设备分配给第 k 个工厂至第 3 个工厂所得到的最大总收益,状态转移方程:,sk+1 = sk - xk,xk的取值范围？,6,x3*(0) = 0,x3*(1) = 1,x3*(2) = 2,x3*(3) = 3,k =3，s3=0,1,2,3,

3、4,5，0 x3 s3,s3 = 0,s3 = 3,0 4 6 11 12 12,s3 = 2,s3 = 1,7,x3*(5) = 4,5,x3*(4) = 4,0 4 6 11 12 12,结果可写成表格的形式:,s3 = 4,s3 = 5,8,k =2，s3 = s2 - x2，s2=0,1,2,3,4,5，0 x2 s2，有,x2*(0) = 0,s2 = 0,9,x2*(1) =1,s2 = 1,10,x2*(2) =2,s2 = 2,11,x2*(3) =2,s2 = 3,12,x2*(4) =1,2,s2 = 4,13,s2 = 5,x2*(5) =2,14,结果列于下表：,k =

4、1时， s2 = s1 - x1， s1 = 5， 0 x1 s1，有,15,x1*(5) =0,2,16,结果可写成表格的形式,最优分配方案一：由 x1* = 0，根据 s2 = s1- x1* = 5- 0 = 5，查表知 x2* = 2，由s3 = s2- x2* = 5 - 2 = 3，故 x3* = s3 =3。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。,最优分配方案？,17,最优分配方案二：由 x1* = 2，根据 s2 = s1 - x1* = 5- 2 = 3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1。即得甲

5、工厂分配2台，乙工厂分配2台，丙工厂分配1台。,以上两个分配方案所得到的总盈利均为21万元。,问题： 如果原设备台数是4台，求最优分配方案？ 如果原设备台数是3台，求最优分配方案？,18,设备台数是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 =

6、s2 - x2*= 2 - 2 =0，故 x3* = s3 =0。即得甲工厂分配2台，乙工厂分配2台，丙工厂分配0台，总盈利为17万元。,19,设备台数是3台，,最优分配方案一：由 x1* = 0，根据 s2 = s1 - x1* = 3- 0 = 3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配1台，总盈利为14万元。,20,2 资源连续分配问题,21,如此进行 n 年，如何确定投入 A 的资源量 u1、un，使总收入最大？,此问题的静态规划问题模型为：,22,高负荷: 产量函数 g =

7、8x， 年完好率为 a=0.7，,机器,例4 机器负荷分配问题,假定开始生产时完好机器的数量为1000台。,低负荷: 产量函数 h = 5y， 年完好率为 b=0.9。,试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高?,投入生产的机器数量,23,状态变量 sk,状态转移方程,决策(变量) uk,第 k 年初拥有的完好机器台数,第 k 年高负荷下投入的机器数,sk+1 = auk+ b(sk - uk) = 0.7uk+ 0.9 (sk - uk),0 uk sk,分析：,第 k 年低负荷下投入的机器数,sk uk,阶段？,24,动态规划基本（递推）方程？,指标函数,第k年度产量为,k = 5, 4, 3, 2, 1,sk+1,阶段指标,f6(s6) = 0,25,则状态转移方程为,sk+1 = 0.7uk+ 0.9 (sk - uk) k = 1, 2, , 5,解：设阶段序数 k 表示年度，sk为第 k 年初拥有的完好机器台数，第 k 年度高负荷下投入的机器数为uk台。,基本方程为,26,f4(s4) = 13.6s4,u*4 = s4,k = 4,u*5 = s5,k = 5,f5(s5) = 8s5,0,27,依此类推可得，,因此最优策略为,最高产量为23700。,问题：1. 每年年初的完好