欢迎来到天天文库
浏览记录
ID:51510021
大小:724.81 KB
页数:39页
时间:2020-03-25
《动态规划应用举例.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第九章:动态规划应用举例第一节:资源分配问题分配问题:将数量一定的一种或若干种资源(例如原材料,资金,机器设备,劳力,食品等等),恰当地分配给若干个使用者,使效益函数最优。1.1多元投资分配问题(离散)设有某种原料,总数量为a,用于生产n种产品。若分配数量xi用于生产第i种产品,其收益为gi(xi),问应如何分配,才能使生产n种产品的总收入最大?静态规划资源分配离散连续决策变量uk表示分配给生产第k种产品的原料数量,即uk=xk;设状态变量sk表示分配用于生产第k种产品至第n种产品的原料数量;状态转移方程:sk+1=sk-uk=sk-xk决策集合:Dk(sk)={uk
2、0uk=xksk}最
3、优值函数fk(sk)表示数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益,动态规划的递推关系为:例1某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂,各工厂若获得这种设备之后,可以为公司提供的盈利如表。问这五台设备如何分配给各工厂,才能使公司得到的盈利最大。解:将问题按工厂分为三个阶段,甲乙丙分别编号为1,2,3。用k表示,即阶段变量决策变量uk表示分配给第k个工厂的设备台数,即uk=xk;设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数;状态转移方程:sk+1=sk-uk=sk-xk决策集合:Dk(sk)={uk
4、0uk=xksk}最优值函数fk(s
5、k)表示数量为sk的设备台数分配给第k个工厂至第n个工厂所得到的最大总收益,动态规划的递推关系为:用逆推法当阶段k=3时,0s35,0x3s3,有x3(s3)结果列于下表:当阶段k=2时,s3=s2-x2,0s25,0x2s2,有结果列于下表:当阶段k=1时,s2=s1-x1,s1=5,0x1s1,有结果可写成表格的形式然后按计算表格的顺序反推,可知最优分配方案有两个:由于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-
6、x1*=5-2=3,查表知x2*=2,由s3=s2-x2*=3-2=1,故x3*=s3=1。即得甲工厂分配2台,乙工厂分配2台,丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元。问题:如果原设备台数是4台,求最优分配方案?如果原设备台数是3台,求最优分配方案?1.2资源连续分配问题:一般问题的提法是如此进行n年,如何确定投入A的资源量u1、…、un,使总收入最大?资源数量s1A种生产数量u1投入收益g(u1)年终资源回收率aB种生产数量s1-u1收益h(s1-u1)年终资源回收率b第一年资源数量s2=au1+b(s1-u1)第二年A种生产数量u2投入;收益g(u2);年终资源回收率a
7、B种生产数量s2-u2;收益h(s2-u2);年终资源回收率b到n年此问题的静态规划问题模型为:动态规划的逆推关系方程为:最后求得的f1(s1)即为所求问题的最大收入。例2机器负荷分配问题某种机器可在高低两种不同负荷下进行生产,设机器在高负荷情况下的产量函数为g=8x,其中x是投入生产的机器数量,年完好率为a=0.7,在低负荷情况下的产量函数为h=5y,其中y是投入生产的机器数量,年完好率为b=0.9。假定开始生产时完好机器的数量为1000台,试问每年如何安排机器在高低两种负荷下的生产,可使5年内生产的产品总产量最高。允许决策集合0uksk解:设阶段数k表示年度。状态变量sk为第k年
8、度初拥有的完好机器台数。决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。状态转移方程第k年度产量为指标函数为递推方程为当时当时依次类推可得,相应的相应的相应的因此最优策略为最高产量为23700。第二节生产与存贮问题所谓生产与库存问题就是一个生产部门,如何在已知生产成本、库存费用和各阶段市场需求条件下,决定各阶段产量,使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。生产与库存问题本身就是一个多阶段决策过程。设某一生产部门,生产周期分为n个阶段,已知最初库存量为x1,阶段市场的需求为dk,生产的固定成本为K,单位产品的消耗费用为L,单位
9、产品的阶段库存费用为h,仓库容量为M,阶段生产能力为B。问如何安排各阶段产量,使计划周期内的费用总和最小。状态变量xk选为阶段k的初始库存量,x1已知,xn+1=0。阶段k的库存量即不能超过库存容量M,也不能超过阶段k至阶段n的需求总量,即决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量,同时要大于该阶段的需求和库存量之差,即状态转移方程为
此文档下载收益归作者所有