- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
分析得知：从D1和D2到E的最短路径唯一。
管 理 运 筹 学
3
第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题：
表10-2 阶段3
本阶段始点 （状态）
C1 C2 C3
本阶段各终点（决策）
D1 8+10=18 7+10=17 1+10=11 D2 6+6=12 5+6=11 6+6=12
k 1
( sk 1 )}
k 1, 2,, n
以上式子称为动态规划最优指标的递推方程，是动态规划的基本 方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最 优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。
管 理 运 筹 学
11
三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的。
管
理
运
筹
学
15
表10－6
s3
x3
0 1
r3 ( s3 , x3 )
2 3 4 5
f 3 ( s3 ) x*3
0
0
－
－
－
－
－
0
0
1 2
3
－ －
－
4 －
－
－ 6
－
－ －
11
－ －
－
－ －
－
4 6
11
1 2
3
4 5
－ －
－ －
－ －
管 理 运
－ － －
筹 学
12 － 12 12 12
4 5
16
其中 x*3 表示取3子过程上最优指标值 f 3 ( s3 )时的 x3 决策，例如在表10-6中可知当s3 =4时，有 r3 (4,4) 12; 有 * f 3 (4) 12, 此时 x 3 4 ，即当 s3 4 时，此时取 x3 4 （把4台设备分配给第3厂）是最优决策，此时阶段指标值 （盈利）为12，最优3子过程最优指标值也为12。 第二阶段： 当把 s2 (s2 0,1,2,3,4,5) 台设备分配给第2工厂和第3工 厂时，则对每个s 2 值，有一种最优分配方案，使最大盈利 即最优2子过程最优指标函数值为 f 2 ( s2 ) max[r2 ( s2 , x2 ) f 3 ( s3 )]
一、基本概念： 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划 分。 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是数 量，也可以是字符，数量状态可以是连续的，也可以是离散的。
3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所 在状态的函数，记为xk(sk)。
决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。
也就是s3 x3 时，第3阶段的指标值（即第3厂的盈利）
为最大，即
max r3 ( s3 , x3 ) r3 ( s3 , s3 )
x3
由于第3阶段是最后的阶段，故有
f 3 ( s3 ) max r3 ( s3 , x3 ) r3 ( s3 , s3 ).
x3
其中 x3可取值为0,1,2,3,4,5。其数值计算见表10－6。
过程指标函数Vk,n(sk, xk, xk+1,…, xn)：从状态sk出发，选择决策xk,
xk+1, …, xn所产生的过程指标。动态规划要求过程指标具有可分离 性，即 Vk,n(sk, xk, xk+1, …, xn) = rk(sk, xk)+Vk+1(sk+1, xk+1, …, xn)
称指标具有可加性，或 Vk,n(sk, xk, xk+1, …, xn) = rk(sk, xk)×Vk+1(sk+1,
11＋4
11＋0
21
2
运
筹
学
18
其中在 s2 4 的这一行里， 当 x2 1 时， 当 x2 2 时，可知
r2 ( s2 , x2 ) f 3 ( s2 x2 ) r2 (4,1) f 3 (4 1) r2 (4,1) f 3 (3) 5 11 16
x2
管
理
运
筹
学
17
因为 s3 s2 x2,上式也可写成
x2
f 2 ( s2 ) max r2 ( s2 , x2 ) f 3 ( s2 x2 )
表10－7
其数值计算如表10－7所示。
s2
0 1 2
x2
0 1 － 2
r2 ( s2 , x2 ) f 3 ( s3 x2 )
本阶段最优终点 到E的最短距离 （最优决策)
12 11 11 D2 D2 D1
分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。
管
理
运
筹
学
4
第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：
2
讨论：
1、以上求从A到E的最短路径问题，可以转化为四个性质完全相
同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路 径问题。
从最短路上每一点到终点的部分道路,也一定是从该点到终点的最短路.
第四阶段：两个始点D1和D2，终点只有一个；
表10-1
阶段4
本阶段始点 （状态） D1 D2 本阶段各终点（决策） E 10 6 10 6 到E的最短距离 本阶段最优终点 （最优决策) E E
xk+1, …, xn)称指标具有可乘性。
管
理
运
筹
学
9
二、基本方程： 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指
标Vk,n的最优值，即
f k (sk )
opt
xk Dk ( s k )
{ k , n ( s k , P , n )} V k
管
理
运
筹
学
10
对于可加性指标函数，上式可以写为
C3
6+11=17 2+11=13 3+11=14 1+11=12
分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。
管 理 运 筹 学
5
第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：
2 3 4 5
f1 ( x) x*1
0,2
0 21
3＋16 7 14
9+10
12+5
13+0 21
然后按计算表格的顺序推算，可知最优分配方案有两个： * * 1.由于 x 1 0 ，根据 s2 s1 x 1 5 0 5 ，查表10－7可 知 x*2 2，再由s3 s2 x*2 5 2 3，求得 x*3 s3 3。即分配 给甲厂0台，乙厂2台，丙厂3台。 2.由于 x*1 2 ，根据 s2 s1 x*1 5 2 3 ，查表10－7可
管 理 运 筹 学
20
知 x*2 2 ，再由s3 s2 x*2 3 2 1 ,求得 x*3 s3 1 ，
3
7 9 12
5
10 11 11
4
6 11 12
5
13
11 表10-5
管 理 运 筹 学
12
13
解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分 别编号为1、2、3厂。设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、 3）。-即第k阶段剩余的可分配设备 xk=分配给第k个厂设备台数。 已知s1=5, 并有
表10-4 阶段1 本阶段始 点(状态) A 本阶段各终点（决策） B1 B2 B3 3+14=17 B4 2+12=14 到E的最 短距离 12 本阶段最优终 点(最优决策) C2
4+12=16 3+13=16
最后，可以得到：从A到E的最短路径为A B4 C3 D1 E
管
理
运
筹
学
6
以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。
s2 T1 (s1 , x1 ) s1 x1 s3 T2 ( s2 , x2 ) s2 x2
从s k 与xk 的定义，可知
以下我们从第三阶段开始计算。
管 理 运 筹 学
14
s3 x3
第三阶段: 显然将 s3 ( s3 0,1,2,3,4,5)台设备都分配给第3工厂时，
管
理
运
筹
学
12
§3
一、资源分配问题
动态规划的应用(1)
例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工
厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这
5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？
盈利
工厂 设备台数 0 甲 厂 0 乙 厂 0 丙 厂 0
1
