资源描述：
《运筹学-动态规划应用举例课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九章动态规划应用举例§1资源分配问题将一定的资源(原料,资金,机器设备等)恰当的分配给若干使用者,使总的目标函数值为最优。属静态规划问题,人为的引入阶段因素。1.1一维资源分配问题静态规划模型Maxz=g1(x1)+g2(x2)+…+gn(xn)x1+x2+…+xn=axi≥0i=1,2,…,n原料总数为a,用于生产n种产品,xi为分配生产第i种产品的原料数量,收益为gi(xi)。如何分配收益最大？将n种产品(使用资源的对象、用户)划分为n个阶段；状态变量sk:分配给生产第k种产品至第n种产品的原料数量；决策变量xk(uk):分配给生产第k种产品的
2、原料数量；状态转移方程：sk+1=sk–xk状态允许集合(约束条件)：0≤sk≤a,s1=a决策允许集合：0≤xk≤sk,xn=sn动态规划递推关系例15台设备,3个工厂,可提供的盈利见下表,如何分配使利润最大？解:甲,乙,丙三个工厂分别编号为1,2,3设xk分配给第k个工厂的设备台数。静态规划模型Maxz=p1(x1)+p2(x2)+p3(x3)x1+x2+x3=5,x1,x2,x3≥0整数pk(xk)xk台设备分配到第k个工厂的盈利数。盈工厂利设备台数甲乙丙012345037912130510111111046111212资源分配问题的阶段划分原
3、则:有几个用户,就把问题分成几个阶段。本题按工厂的个数,分为3个阶段。分析:k=3,把第3阶段初所拥有的所有设备全部分给工厂3(单一用户分配)；k=2,把第2阶段初所拥有的所有设备全部分给工厂2和工厂3(2个用户分配)；k=1,把第1阶段初所拥有的5台设备全部分给工厂1,工厂2和工厂3(3个用户分配)。状态变量sk:分配给第k个工厂至第3个工厂的设备台数；0≤sk≤5,s1=5决策变量xk:分配给第k个工厂的设备台数；0≤xk≤sk,xn=sn状态转移方程：sk+1=sk-xksk+1分配给第k+1个工厂至第3个工厂的设备台数最优值函数fk(sk)s
4、k台设备分配给第k个工厂至第3个工厂的最大盈利值。递推基本方程k=30≤s3≤5,s3取值范围s3=0,1,2,3,4,5x3取值范围x3=s3=0,1,2,3,4,5将x3的值逐个代入基本方程,计算结果填入表中x3s3P3(x3)f3(s3)x3*012345012345046111212046111212012345k=20≤s2≤5, s2取值范围s2=0,1,2,3,4,5对s2的每取值,确定x2取值范围0≤x2≤s2根据状态转移方程s3=s2-x2,确定s3s2=0,x2=0s2=1,x2=0,1s2=2,x2=0,1,2s2=3,x2=0
5、,1,2,3s2=4,x2=0,1,2,3,4s2=5,x2=0,1,2,3,4,5s3=s2-x2=0=1,0=2,1,0=3,2,1,0=4,3,2,1,0=5,4,3,2,1,0k=1s1=5,0≤x1≤s1,x1取值范围x1=0,1,2,3,4,5根据状态转移方程s2=s1–x1,确定s2取值范围s2=5,4,3,2,,1,0x2s2P2(x2)+f3(s3)f2(s2)x2*0123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+01
6、1+411+0051014162101221,22x1s1P1(x1)+f2(s2)f1(5)x1*01234550+213+167+149+1012+513+0210,2从k=1,可得全过程最优指标函数f1(s1)=21按决策顺序可推出,有2个最优决策方案设备总数改为4台,取s1=4,只需修改k=1的表格4台x1*=1,x2*=2,x3*=1；f1(s1)=17或x1*=2,x2*=2,x3*=03台x1*=0,x2*=2,x3*=1；f1(s1)=14x1*=0x2*=2x3*=3s2=s1-x1*=5s3=s2-x2*=3(1)x1*=2x2*
7、=2x3*=1s2=s1-x1*=3s3=s2-x2*=1(2)这种只将资源合理分配不考虑回收,而决策变量取离散值的问题,称为资源平行分配问题。实际中,如货物分配,资金分配等。例有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见表。求对三个项目的最优投资分配，使总投资效益最大。解：阶段k：每个投资项目作为一个阶段；状态变量sk：投资第k个项目至第n个项目的资金数；状态允许集合:0≤sk≤4,s1=4决策变量uk:第k个项目的投资；决策允许集合Dk(uk):0≤u
8、k≤sk,un=sn状态转移方程：sk+1=sk-uk；阶段指标：vk(sk,uk)见表中所示；递推方程：f
