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

设有某种原料，总数量为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台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。046111212051011111103791213012345丙乙甲工厂盈利设备台数甲乙丙012345037912130510111111046111212如何划分阶段s1的可达状态集合s2的可达状态集合s3的可达状态集合决策变量uk(sk)0sk3个阶段xk状态转移方程？甲乙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程?指标函数gk(xk)?kkkxss1s4解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。决策变量xk::分配给生产第k个工厂的设备数量分配给第k个工厂至第3个工厂的设备数量（第k阶段开始剩余的设备数量）。状态变量sk:甲乙丙012345037912130510111111046111212Dk(sk)={uk|0uk=xksk}0)()]([max44110sfsfxgsfkkkksxkkkk基本方程：数量为sk的设备分配给第k个工厂至第3个工厂所得到的最大总收益状态转移方程:sk+1=sk-xkxk的取值范围？甲乙丙0123450379121305101111110461112120)0()}()({max)0(344330333gsfxgfsx11)3(3fx3*(0)=0x3*(1)=1x3*(2)=2x3*(3)=3k=3，s3=0,1,2,3,4,5，0x3s3s3=0s3=3甲乙丙0123450379121305101111110461112120461112124)1()0(max)}()({max)1(331,0443303333ggsfxgfxsx6)2(3fs3=2s3=1甲乙丙01234503791213051011111104611121212)4(3f12)5(3fx3*(5)=4,5x3*(4)=4046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5结果可写成表格的形式:s3=4s3=5甲乙丙012345037912130510111111046111212k=2，s3=s2-x2，s2=0,1,2,3,4,5，0x2s2，有x2*(0)=0s2=00)0()}()({max)0(233220222gsfxgfsxx3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5322ssxx2*(1)=1s2=1甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,550540max)0()1()1()0(max)}()({max)1(1,032321,03322022222xxsxfgfgsfxgfx2*(2)=2s2=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5100104560max)0()2()1()1()2()0(max)}()({max)2(2,1,03232322,1,03322022222xxsxfgfgfgsfxgf1401141065110max)0()3()1()2()2()1()3()0(max)}()({max)3(3,2,1,0323232323,2,1,03322022222xxsxfgfgfgfgsfxgfx2*(3)=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5s2=3甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,516011411610115120max)0()4()1()3()2()2()3()1()4()0(max)}()({max)4(4,3,2,1,032323232324,3,2,1,03322022222xxsxfgfgfgfgfgsfxgfx2*(4)=1,2s2=4210114116111110125120max)0()5()1()4()2()3()3()2()4()1()5()0(max)}()({max)5(5,4,3,2,1,03232323232325,4,3,2,1,03322022222xxsxfgfgfgfgfgfgsfxgfs2=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+0051014162101221,22k=1时，s2=s1-x1，s1=5，0x1s1，有x2s2f2(s2)x*2012345051014162101221,2221013512109147163210max)0()5()1()4()2()3()3()2()4()1()5()0(max)}()({max)(2121212121215,4,3,2,1,0,2211011111fgfgfgfgfgfgsfxgsfxsxx1*(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=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台，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234540+163+147+109+512+013+0171,2最优分配方案一：由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台，x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234530+143+107+59+012+013+0140最优分配方案一：由x1*=0，根据s2=s1-x1*=3-0=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配1台，总盈利为14万元。2资源连续分配问题A种生产数量u1投入收益g(u1)年终资源回收率aB种生产数量s1-u1收益h(s1-u1)年终资源回收率b资源数量s1第一年资源数量s2=au1+b(s1-u1)第二年A种生产数量u2投入;收益g(u2);年终资源回收率aB种生产数量s2-u2;收益h(s2-u2);年终资源回收率b到n年如此进行n年，如何确定投入A的资源量u1、…、un，使总收入最大？此问题的静态规划问题模型为：nisuusbaususbaususbaustsushugZiinnnnniiii,,2,1,0)()()(..)}()({max12223111211s（拥有的总资源数已知）高负荷:产量函数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阶段？动态规划基本（递推）方程？515,1),(kkkkusvV指标函数第k年度产量为)(58),(kkkkkkusuusvfk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0ukskk=5,4,3,2,1sk+1阶段指标f6(s6)=0则状态转移方程为sk+1=0.7uk+0.9(sk-uk)k=1,2,…,5解：设阶段序数k表示年度，sk为第k年初拥有的完好机器台数，第k年度高负荷下投入的机器数为uk台。fk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0ukskk=5,4,3,2,1f6(s6)=0基本方程为f4(s4)=13.6s4u*4=s4k=4u*5=s5k=5f5(s5)=8s5}53{max)}()(58{max)(550665550555555susfususfsusu}2.124.1{max)}(2.126.13{max))}(9.07.0()(58{max)(44044404445444044444444suusuusufususfsususu0依此类推可得，111*1222*23333*37.23)(08.20)(05.17)(ssfussfussfsu因此最优策略为5*54*43*3*2*1,,,0,0