十动态规划的应用---资源分配问题（课堂PPT）

设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)，问应如何分配，才能使生产n种产品的总收入最大？,资源分配问题,1资源平行分配问题,静态规划模型,不考虑回收,1,例3某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,2,如何划分阶段,s1的可达状态集合,s2的可达状态集合,s3的可达状态集合,决策变量uk(sk),0sk,3个阶段,xk,状态转移方程？,3,s1,s2,s3,3,2,1,x1,x2,x3,基本方程?,指标函数gk(xk)?,s4,4,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。,决策变量xk:,分配给生产第k个工厂的设备数量,分配给第k个工厂至第3个工厂的设备数量（第k阶段开始剩余的设备数量）。,状态变量sk:,5,Dk(sk)=uk|0uk=xksk,基本方程：,数量为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,4,5，0x3s3,s3=0,s3=3,046111212,s3=2,s3=1,7,x3*(5)=4,5,x3*(4)=4,046111212,结果可写成表格的形式:,s3=4,s3=5,8,k=2，s3=s2-x2，s2=0,1,2,3,4,5，0x2s2，有,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=1时，s2=s1-x1，s1=5，0x1s1，有,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。即得甲工厂分配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=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=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),0uksk,分析：,第k年低负荷下投入的机器数,skuk,阶段？,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.每年年初的完好机器数。2.如规定