文档介绍：运筹学第三版动态规划第9章动态规划应用举例
五、动态规划
第8章动态规划的基本方法
第9章动态规划应用举例
清华大学出版社
第9章动态规划应用举例
第1节资源分配问题
第2节生产与存储问题
第3节* 背包问题
第4节* 复合系统工作可靠性问题
第5节排序问题
第6节设备更新问题
第7节* 货郎担问题
清华大学出版社
第1节资源分配问题
所谓分配问题,就是将数量一定的一种或若干种资源(例如原材料、资金、机器设备、劳力、食品等等),恰当地分配给若干个使用者,而使目标函数为最优。
清华大学出版社
13>.1资源分配问题
设有某种原料,总数量为a,用于生产n种产品。若分配数量xi用于生产第i种产品,其收益为
问应如何分配,才能使生产n产品的总收入最大?
此问题可写成静态规划问题:
当
都是线性函数时,它是一个线性规划问题;当
是非线性函数时,它是一个非线性规划问题。但当n比较大时,具体求解是比较麻烦的。由于这类问题的特殊结构,可以将它看成一个多阶段决策问题,并利用动态规划的递推关系来求解。
清华大学出版社
在应用动态规划方法处理这类“静态规划”问题时,通常以把资源分配给一个或几个使用者的过程作为一个阶段,把问题中的变量xi为决策变量,将累计的量或随递推过程变化的量选为状态变量。
清华大学出版社
设状态变量sk表示分配用于生产第k种产品至第n种产品的原料数量。
决策变量uk表示分配给生产第k种产品的原料数,即uk=xk
状态转移方程:
允许决策集合:
令最优值函数
表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收入。因而可写出动态规划的逆推关系式为:
利用这个递推关系式进行逐段计算,最后求得即为所求问题的最大总收入。
清华大学出版社
例1 某工业部门根据国家计划的安排,拟将某种高效率的设备五台,分配给所属的甲、乙、丙三个工厂,各工厂若获得这种设备之后,可以为国家提供的盈利如表9-1所示。
问:这五台设备如何分配给各工厂,才能使国家得到的盈利最大。
清华大学出版社
解: 将问题按工厂分为三个阶段,甲、乙、丙三个工厂分别编号为1、2、3
设sk表示为分配给第k个工厂至第n个工厂的设备台数。xk表示为分配给第
k个工厂的设备台数。则
为分配给第k+1个工厂至第n个工厂的设备台数。
表示为sk台设备分配到第k个工厂所得的盈利值。
表示为sk台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。
因而可写出逆推关系式为
清华大学出版社
下面从最后一个阶段开始向前逆推计算。
第三阶段:
设将s3台设备(s3=0,1,2,3,4,5)全部分配给工厂丙时,则最大盈利值为
其中x3=s3=0,1,2,3,4,5
因为此时只有一个工厂,有多少台设备就全部分配给工厂丙,故它的盈利值就是该段的最大盈利值,如下表。
5
12
12
5
4
12
12
4
3
11
11
3
2
6
6
2
1
4
4
1
0
0
0
0
5
4
3
2
1
0
x3*
f3(s3)
P3(x3)
x3
s3
表中x3*表示使f3(s3)为最大值时的最优决策。
清华大学出版社
第二阶段:
设把s2台设备(s2=0,1,2,3,4,5)分配给工厂乙和工厂丙时,则对每个s2值,有一种最优分配方案,使最大盈利值为
其中
因为给乙工厂x2台,其盈利为p2(x2) ,余下的s2??x2台就给丙工厂,则它的盈利最大值为f3(s2 ?? x2) 。现要选择x2的值,使
取最大值。其数值计算如表9-3所示。
清华大学出版社
表9-3
2
21
11+0
11+4
11+6
10+11
5+12
0+12
5
1,2
16
11+0
11+4
10+6
5+11
0+12
4
2
14
11+0
10+4
5+6
0+11
3
2
10
10+0
5+4
0+6
2
1
5
5+0
0+4
1
0
0
0
0
5
4
3
2
1
0
清华大学出版社
第一阶段:
设把s1台(这里只有s1=5的情况)设备分配给甲、乙、丙三个工厂时,则最大盈利值为
其中
因为给甲工厂x1台,其盈利为p1(x1) ,剩下的5??x1台就分给乙和丙两个工厂,则它的盈利最大值为f2(5??x1) 。现要选择x1值,使
取最大值,它就是所求