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

设有某种原料，总数量为a，用于生产n种产品。若分配数量xi

用于生产第i种产品，其收益为gi(xi)，问应如何分配，才能使生产n种产品的总收入最大？

资源分配问题1资源平行分配问题MaxZ=g1(x1)+g2(x2)++gn(xn)

s.t.

x1+x2+

+

xn=axi0i=1,2,

,n静态规划模型不考虑回收

例3

某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。046111212051011111103791213012345丙乙甲工厂盈利设备台数

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

分配给生产第k

个工厂的设备数量

分配给第k个工厂至第3

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

xksk}基本方程：数量为sk的设备分配给第k个工厂至第3个工厂所得到的最大总收益状态转移方程:sk+1=sk-

xkxk的取值范围？甲乙丙012345037912130510111111046111212x3*(0)

=0x3*(1)

=1x3*(2)

=2x3*(3)

=3k=3，s3=0,1,2,3,4,5，0x3s3s3=0s3=3甲乙丙012345037912130510111111046111212046111212s3=2s3=1甲乙丙012345037912130510111111046111212x3*(5)

=4,5x3*(4)

=4046111212x3s3g3(x3)f3(s3)x*301234501234504611121212046111212012344,5结果可写成表格的形式:s3=4s3=5甲乙丙012345037912130510111111046111212

k=2，s3=s2-x2，s2=0,1,2,3,4,5，0x2s2，有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(s3)x*301234501234504611121212046111212012344,5x2*(3)

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

=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+0051014162101221,22k=1时，s2=s1-x1，

s1=5，0x1s1，有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=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)

年终资源回收率a

B种生产数量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，使总收入最大？此问题的静态规划问题模型为：高负荷:产量函数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)0uksk分析：第k年低负荷下投入的机器数sk–uk阶段？动态规划基本（递推）方程？指标函数第k年度产量为fk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0