文档介绍：4-3 动态规划应用(一)建模练习
一、工程路线问题(也称最短路或最长路问题)
工程路线问题的一般提法:
从某地出发,途径若干个中间点最后到达目的地,试求距离最短或费用最省的路线。
具体有两种情况:
从出发点到目的地的每条路线均由n条边(弧)组成,因此问题可以化为n个阶段的多阶段决策过程。由于可以明确地划分出固定的阶段数,所以称为定步数问题,亦称定期的多阶段决策过程。
阶段数不固定则称为不定步数问题,或不定期的多阶段决策过程。
建模过程如表4-1。
表4-1 工程路线的建模过程
若是不定步数问题,则基本方程呈函数方程的形式:
二、资源分配问题:
资源的多元分配:
某种资源总量为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
该问题可以作为三阶段决策过程。
对A、B、C三个企业资金分配过程分别形成1、2、3三个阶段。
xk表示给企业分配资金数时拥有的资金数。
uk为给企业实际分配的资金数。
状态转移方程是xk+1=xk-uk。
阶段效应rk(xk,uk)如表4-2所示,记为gk(uk)。目标函数是:
表函数
表4-3资源的多元分配问题建模过程
2. 资源的多段分配——有消耗的资源多阶段地在两种不同的生产活动中投放的问题
问题的提法:假定拥有某种资源,总量为M,计划在A、B两种生产过程(部门)中连续使用n个阶段,已知在两个部门中分别投入资源ua、ub后可分别获得阶段效益g(ua) 、h(ub),同时知道每生产一个阶段后资源的完好率分别为a和b,(0<a<1,0<b<1),求n个阶段间总收益最大的资源分配计划。