2019年大学课件动态规划应用举例.ppt

《2019年大学课件动态规划应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/7/291资源分配问题生产与存贮问题设备更新问题动态规划应用举例docin/sundae_meng2021/7/29docin/sundae_meng26.3资源分配问题6.3.1一维离散资源分配问题设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使目标函数为最优。MAX=g1(x1)+g2(x2)+‥‥+gn(xn)x1+x2+…+xn=axi

2、≥0i=1,2,…,ns.t.2021/7/29docin/sundae_meng3决策集合：Dk(sk)={uk

3、0uk=xksk}uk:分配给生产第k种产品的原料数量，即uk=xk；sk:分配给用于生产第k种至第n种产品的原料数量；状态转移方程：sk+1=sk-uk=sk-xk最优值函数fk(sk):数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：2021/7/29docin/sundae_meng4工业部拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂

4、若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。例1解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。逆推法﹗2021/7/29docin/sundae_meng5k=3时，0s35，0x3s3可分配的机器数量分配的机器数量sk+1=sk-uk=sk-xkf3(s3)=max﹝g3﹙x3﹚﹞0≤x3≤s3f4(s4)=0S3=?g3(0)g3(1)=4x3*(1)=1=g3﹙0﹚=0S3=0,f3(0)=max｛g3﹙x3﹚+f4(

5、s4)｝0≤x3≤s3x3*(0)=0=maxx3=0,1S3=1,f3(1)=max｛g3﹙x3﹚+f4(s4)｝0≤x3≤s32021/7/29docin/sundae_meng62021/7/29docin/sundae_meng72021/7/29docin/sundae_meng8当阶段k=2时，s3=s2-x2，0s25，0x2s2，有2021/7/29docin/sundae_meng92021/7/29docin/sundae_meng102021/7/29docin/sundae

6、_meng112021/7/29docin/sundae_meng12结果列于下表：f3(1-0)=f3(1)=4f3(5-3)=f3(2)2021/7/29docin/sundae_meng13当阶段k=1时，s2=s1-x1，s1=5，0x1s1，有S1=5,f1(S1)=max｛g1﹙x1﹚+f2(s2)｝0≤x1≤s1=max｛g1﹙x1﹚+f2(s1-x1)｝x1=0,1,2,3,4,5=maxg1(0)+f2(5)g1(1)+f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)

7、+f2(1)g1(5)+f2(0)x1*(5)=0,20+213+167+149+1012+513+0=max2021/7/29docin/sundae_meng14结果可写成表格的形式S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一张表2021/7/29docin/sundae_meng15S3*=s2*-x2*=5-2=3x3*=3x2*=22021/7/29docin/sundae_meng16按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配0台，乙工厂分

8、配2台,丙工厂分配3台。甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元问题：如果原设备台数是4台，求最优分配方案？如果原设备台数是3台，求最优分配方案？2021/7/29docin/sundae_meng176.3.2一维连续资源分配问题:一般问题的提法是A种生产数量u1投入收益g(u1)年终资源回收率a如此进行n年，如何确定投入A的资源量u1、…、un，使总收入最大？B种生产数量s1-u1收益h(s1-u1)年终资源回收率b资源数量s1第一年资源数量s2=au

9、1+b(s1-u1)第二年A种生产数量u2投入;收益g(u2);年终回收率aB种生产数量s2-u2;收益h(s2-u2);年终回收率b到n年2021/7/29docin/sundae_meng18此问题的静态规划问题模型为：动态规划的逆推关系方程为：最后求得f1(s1)即为所求问题的最大收入。2021/7/29docin/sundae_meng19高负荷:产量函数g=8u1,u1是投入生产的机器数量，年完好率为a=0.7，低负