文档介绍：4-3 动态规划应用(一)建模练习
一、工程路线问题(也称最短路或最长路问题)
工程路线问题的一般提法:
从某地出发,途径若干个中间点最后到达目的地,试求距离最短或费用最省的路线。
具体有两种情况:
从出发点到目的地的每条路线均由n条边(弧)组成,因此问题可以化为n个阶段的多阶段决策过程。由于可以明确地划分出固定的阶段数,所以称为定步数问题,亦称定期的多阶段决策过程。
阶段数不固定则称为不定步数问题,或不定期的多阶段决策过程。
建模过程如表4-1。
例子:定步数问题
例子:不定步数问题
s
a
b
c
d
t
2
4
4
3
4
4
2
1
2
5
表4-1工程线路问题的建模过程
逆序表示
Page105
若是不定步数问题,则基本方程呈函数方程的形式:
二、资源分配问题:
资源的多元分配:
某种资源总量为M,用于进行n种生产活动,已知用于活动k的资源量为uk时收益为gk(uk),( gk(uk)为uk的非递减函数),问如何分配资源,才能使n种生产活动的总收益最大?
例4-2:某公司拟将5万元资金投放下属A、B、C三个企业,各企业在获得资金后的收益如下表所示,用动态规划方法求总收益最大的投资分配方案(投资数取整数)。
表4-2 例4-2已知信息表
投放资金(万元)
0
1
2
3
4
5
资源投入后获得的利润
(万元)
A
0
2
2
3
3
3
B
0
0
1
2
4
7
C
0
1
2
3
4
5
阶段划分:
将n种活动作为一个相互衔接的整体,对一种活动的资源分配作为一个阶段。每个阶段确定一种活动的资源投放量,该问题就成为一个多阶段决策问题。