十动态规划的应用___资源分配问题.ppt

《十动态规划的应用___资源分配问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)，问应如何分配，才能使生产n种产品的总收入最大？资源分配问题1资源平行分配问题MaxZ=g1(x1)+g2(x2)++gn(xn)s.t.x1+x2++xn=axi0i=1,2,,n静态规划模型不考虑回收例3某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。04611121205101111

2、1103791213012345丙乙甲工厂盈利设备台数甲乙丙012345037912130510111111046111212如何划分阶段s1的可达状态集合s2的可达状态集合s3的可达状态集合决策变量uk(sk)0sk3个阶段xk状态转移方程？甲乙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程?指标函数gk(xk)?s4解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。决策变量xk::分配给生产第k个工厂的设备数量分配给第k个工

3、厂至第3个工厂的设备数量（第k阶段开始剩余的设备数量）。状态变量sk:甲乙丙012345037912130510111111046111212Dk(sk)={uk

4、0uk=xksk}基本方程：数量为sk的设备分配给第k个工厂至第3个工厂所得到的最大总收益状态转移方程:sk+1=sk-xkxk的取值范围？甲乙丙012345037912130510111111046111212x3*(0)=0x3*(1)=1x3*(2)=2x3*(3)=3k=3，s3=0,1,2,3,4,5，0x3s3s3=0s3

5、=3甲乙丙012345037912130510111111046111212046111212s3=2s3=1甲乙丙012345037912130510111111046111212x3*(5)=4,5x3*(4)=4046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5结果可写成表格的形式:s3=4s3=5甲乙丙012345037912130510111111046111212k=2，s3=s2-x2，s2=0,1,2,

6、3,4,5，0x2s2，有x2*(0)=0s2=0x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(1)=1s2=1甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(2)=2s2=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(

7、s3)x*301234501234504611121212046111212012344,5x2*(3)=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5s2=3甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(4)

8、=1,2s2=4s2=5甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5x2*(5)=2结果列于下表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101

9、221,22k=1时，s2=s1-x1，s1=5，0x1s1，有x2s2f2(s2)x*2012345051014162101221,22x1*(5)=0,2甲乙丙012345037912130510111111046111212结果可写成表格的形式x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234550+213+167+149+1012+513+0210,2最优分配方案一：由x1*=0，根据s2=s1-x1*=5-0