4-4节动态规划应用（二）
——求解方法讨论
核心
最优化原理
的应用
求解的一般方法
逆序求解
一、工程路线问题
? 1、定步数问题（逆序求解）
–分步计算法
–表格法
–标号法
2、不定步数问题
? （ 1）无回路有向网络
–对节点排序，化为定步数问题
–对节点排序，用分步计算法或表
格法逆序求解
–对节点排序，用二次标号法求解
(2)一般情况
? 函数迭代法
? 策略迭代法
定步数问题求解示例
? 1,定步数问题 （ 逆序求解 ）
? 例 4-6 某运输公司拟将一批货物自 s地运
至 t地, 其间交通系统网络如图 4-2所示 。 图
中节点表示地点, 边表示两地间的道路,
边上的数字表示两地间的运输费用, 求总
运输费用最低的路线 。
1 2 3 4
图 4-2
6
8
4 712
4
4
1
da
eb
h
t
g
fc
s
3
4
11
3
6
9
5
5
3
问题可归结为四阶段决策问题，用动
态规划方法求解如下：
（解法一） 分步计算法
（从第 4阶段开始）
①当 k=4时,i=h或 g,j=t； f5(t)=0
若 i=h,则
? ? thjtfcjfchf htijtj ??????? ? )(,05)()(m in)( *4554
?当 k=3时,i=d或 e,f； j=h或 g
? ? tjtfcjfcgf gtij
tj
????????
?
*
4554,003)()(m i n)(
? ?
gdj
gfc
hfc
jfcdf
dg
dh
ij
ghj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(,11
38
59
m i n
)(
)(
m i n)(m i n)(
*
3
4
4
4
,
3
若 i=g,则
若 i=d,则
若 i=e,则
? ?
hej
gfc
hfc
jfcef
eg
eh
ij
ghj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(,12
312
57
m in
)(
)(
m in)(m in)(
*
3
4
4
4
,
3
若 i=f,则
? ?
gfj
gfcjfcff fgij
gj
????
????
?
)(,835
)()(m in)(
*
3
443
?当 k=2时,i=a或 b,c； j=d或 e,f；
若 i=a,则
? ?
faj
ffc
dfc
jfcaf
af
ad
ij
fdj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;12
84
113
m i n
)(
)(
m i n)(m i n)(
*
2
3
3
3
,
2
? ?
fbj
ffc
efc
dfc
jfcbf
bf
be
bd
ij
fedj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;14
86
124
114
m in
)(
)(
)(
m in)(m in)(
*
2
3
3
3
3
,,
2若 i=b,则
若 i=c,则
? ?
dcj
ffc
dfc
jfccf
cf
cd
ij
fdj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;12
86
111
m in
)(
)(
m in)(m in)(
*
2
3
3
3
,
2
? ?
asj
cfc
bfc
afc
jfcsf
sc
sb
sa
ij
cbaj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;16
1211
143
124
m i n
)(
)(
)(
m i n)(m i n)(
*
1
2
2
2
2
,,
1
?当 k=1时,i=s; j=a或 b,c；
于是,
目标函数最优值（最低总费用）
R*=f1(s)=16
最优策略是
P*={j1*(s)=a,j2*(a)=f,j3*(f)=g,j4*(g)=t};
s a f g t,或
{s,a,f,g,t} ;
从 s地到 t地总运输费用最低的路线
（ 最优路线）是
（解法二）表格法
16)(1* ?? sfR最小费用：
tgfas ????最优路线：
? ?tggffaasp jjjj ????? )(,)(,)(,)( *****
最优策略：
最终结果
阶段 K j决策集
i状态集
t
4 h 5+0 5 t
g 3+0 3 t
3
h g
d 9+5 8+3 11 g
e 7+5 12+3 12 h
f --- 5+3 8 g
2
d e f
a 3+11 --- 4+8 12 f
b 4+11 4+12 6+8 14 f
c 1+11 --- 6+8 12 d
1 a b c
s 4+12 3+14 11+12 16 a
)(4 ij?
)(3 ij?
)(2 ij?
)(1 ij?
)(4 if
)(3 if
)(2 if
)(1 if
)(1 jfC kij ??
具体步骤：
① 给终点标号 0,先标离终点最近的阶段状
态, 将距离数写在相应的节点上方方格
内；
② 方格内的标号 =min﹛ 欲标号点到已标号
点的距离 +已标号点方格内的数字 ﹜ ；
③ 用直线段连接已标号点到终点的最短路
线 。
（解法三）标号法
da
eb
h
t
g
fc
s
3
4
11
3
4
6
9
7
12
5
5
3
4
4
6
1
8
1 2 3 4
0
5
3
11
12
8
12
14
12
16
2、不定步数问题
①
③
②
④
（ 1） 对无回路的有向网络
方法 1：先对节点排序，适当增加虚设节点，
化为定步数问题，然后按前面的情况求解
例 4-7 将图 4-3化为定步数问题
图 4-3 例 4-7网络图
s
a
b
t
3
4
1
5
2
s b a t4 1 5
a’
0
3 t’
0
2
1 2 3
?增加虚设节点 a’和 t’
?然后，按定步数问题求解
方法 2 先对节点排序，然后采用分步
计算法或表格法，根据最优化原理，逆
序求解。
? 例 4-8 求解图 4-5所示从 s到 t点的网络最短路问题
? 3 a 2 c 5
? s 4 4 t
? 4 1 2 2
? b 4 d
图 4-5
?
ts
a
b
c
d
3
4
1
2
4
2
4
5
2
4
?
? ?
?
?
用表格法逆序求解如下：
j
i
t d c a b
t 0
d 2+0 2 t
c 5+0 4+2 5 t
a 4+2 2+5 6 d
b 4+2 2+5 1+6 6 d
s 3+6 4+6 9 a
)(* ij
)(if)( jfdij ?
? ?tdjdajasjp ???? )(,)(,)( ****
最优策略为
? ?tdas,,,最优路线为
9* ?R从 s到 t的最短距离是
方法 3 二次标号法
? 圆圈内数字为节点序 （ 第一次标号 ） ；
? 方框内数字为该点到终点的最短距离
（ 第二次标号 ） ；
? 红线指示出最短路线为 {s,a,d,t}。
3
4
1
4
2
2
4
4
2
5
a ? c ?
s ? t ?
b d
? ?
9
6
0
5
26
??圆圈内数字为节点序 （ 第一次标号 ） ；
??方框内数字为该点到终点的最短距离
（ 第二次标号 ） ；
??红线指示出最短路线为 {s,a,d,t}。
（ 1） 一般情况下的不定步数问题
? 方法 1：函数迭代法
? ?
??
?
?
?
?
????
0)(
1,,2,1,)(m in)(
Nf
NijfCif ij
j
?
设 表示由 i点出发到终点 N的最短距离,
则 DP基本方程为
)(if
?基本思想,段数作参数, 分别求最优, 优
中再选优, 随之定段数 。
?步骤：
（ 1） 选初始函数
?
?
?
?
???
N0
1,,2,1)(1
i
NiCif iN ?
表示由 i点出发向终点 N走一步
的最短距离 。
)(if
? ?
??
?
?
?
??
???? ?
10)(
1,,2,1)(m i n)( 1
kNf
NijfCif kij
jk
?
（ 2） 定义
按此递推关系求出,
其中 表示由 i出发朝固定点 N走 k步的最
短长度 。
当 时, 迭代停止,
可以证明 n≤N-1。
就是 i到 N点的最短距离, N为阶段数,
? ? 1,,2,1)( ?? Niif k ?
)(ifk
1,,2,1)()(1 ???? Niifif nn ?
)(ifk
例 4-9 用函数迭代法求图 4-6中各点到节点 5的
最短路 。
?先写出距离矩阵
1
32
4
5
5
2
2
6
7 5
3
0.5
5
1
图 4-6
Cij j
i 1 2 3 4 5
1 0 6 5 2 2
2 6 0 0.5 5 7
3 5 0.5 0 1 5
4 2 5 1 0 3
5 2 7 5 3 0
用表格形式书写的距离矩阵
?
?
?
?
??
0)5(
4,3,2,1)(
1
51
f
icif i根据 选初始函数为：
3)4(,5)3(,7)2(,2)1( 451351251151 ???????? cfcfcfcf
迭代表格如下：
j
i 1 2 3 4 5
1 2 7 5 3 0
2 2 5.5 4 3 0
3 2 4.5 4 3 0
4 2 4.5 4 3 0
j* 5 3 4 5
)(ifk
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=1
1
2
3
4
f1(i)=ci5,f1(5)=0 i=1,2,3,4
f1（ 1） =c15=2
f1（ 2） =c25=7
f1（ 3） =c35=5
f1（ 4） =c45=3
① ⑤
② ⑤
③ ⑤
④ ⑤
函数迭代法计算过程
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=2
1
2
3
4
f2(i)=min[cij+f1(j)],f2（ 5） =0
f2（ 1） =
=min（ 0+2,6+7,5+5,2+3,2+0） =2
f2（ 2） =
=min（ 6+2,0+7,0.5+5,5+3,7+0） =5.5
f2（ 3） =
=min（ 5+2,0.5+7,0+5,1+3,5+0） =4
f2（ 4） =
=min（ 2+2,5+7,1+5,0+3,3+0） =3
① ⑤
② ③ ⑤
③ ④ ⑤
④ ⑤
)]([m i n 11 jfc jj ?
)]([m i n 12 jfc jj ?
)]([m i n 13 jfc jj ?
)]([m i n 14 jfc jj ?
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=3
1
2
3
4
f3(i)=min[cij+f2(j)],f3(5)=0
f3（ 1） =
=min（ 0+2,6+5.5,5+4,2+3,2+0） =2
f3（ 2） =
=min(6+2,0+5.5,0.5+4,5+3,7+0)=4.5
f3（ 3） =
=min（ 5+2,0.5+5.5,0+4,1+3,5+0） =4
f3（ 4） =
=min（ 2+2,5+5.5,1+4,0+3,3+0） =3
① ⑤
② ③
④ ⑤
③ ④ ⑤
④ ⑤
)]([m in 21 jfc jj ?
)]([m in 22 jfc jj ?
)]([m in 23 jfc jj ?
)]([m in 24 jfc jj ?
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=4
1
2
3
4
f4（ i） =min[cij+f3（ j） ],f4（ 5） =0
f4（ 1） =
=min(0+2,6+4.5,5+4,2+3,2+0)=2
f4（ 2） =
=min(6+2,0+4.5,0.5+4,3+3,7+0)=4.5
f4（ 3） =
=min（ 5+2,0.5+7,0+5,1+3,5+0） =4
f4（ 4） =
=min（ 2+2,5+4.5,1+4,0+3,3+0） =3
① ⑤
② ③
④ ⑤
③ ④ ⑤
④ ⑤
)]([m in 31 jfc jj ?
)]([m in 32 jfc jj ?
)]([m in 33 jfc jj ?
)]([m in 34 jfc jj ?
根据上面计算，得到如下最终结果,
? ?5)1(** ?? jp ? ?5,1
? ?5)4(,4)3(,3)2( **** ???? jjjp ? ?5,4,3,2
? ?5)4(,4)3( *** ??? jjp ? ?5,4,3
? ?5)4(** ?? jp ? ?5,4
最 优 策 略 最优路线 最短路长
2
4.5
4
3
方法 2：策略迭代法
?给出初始策略 {u0(i)};
?由策略 {uk(i)}求最优指标函数 {fk(i)};
?由最优指标函数 {fk(i)}求策略 {uk+1(i)};
?反复迭代,直至 {uk(i)}= {uk+1(i)}
二、资源分配问题
1,资源的多元分配
? 例 4-10 某公司将 5万元资金投入下属 A、
B,C三个企业, 投放收益见表 4-9,试求
总收益最大的投资方案 。
接 word文档
2、资源的多段分配
? 教材 156页例 4 – 4
三、生产库存问题
教材 P164例 4-5（接 word文档）
四、背包问题
五、其他
小结：
? 深入理解最优化原理
? 掌握建模条件（大前提、条件、方程）
? 记住求解要求
诀窍
多看参考资料
积累一批例子
第八次作业 （习题 4 ）
P175~P177：
用动态规划方法求解
4-1,4-2,4-3,4-5
——求解方法讨论
核心
最优化原理
的应用
求解的一般方法
逆序求解
一、工程路线问题
? 1、定步数问题（逆序求解）
–分步计算法
–表格法
–标号法
2、不定步数问题
? （ 1）无回路有向网络
–对节点排序，化为定步数问题
–对节点排序，用分步计算法或表
格法逆序求解
–对节点排序，用二次标号法求解
(2)一般情况
? 函数迭代法
? 策略迭代法
定步数问题求解示例
? 1,定步数问题 （ 逆序求解 ）
? 例 4-6 某运输公司拟将一批货物自 s地运
至 t地, 其间交通系统网络如图 4-2所示 。 图
中节点表示地点, 边表示两地间的道路,
边上的数字表示两地间的运输费用, 求总
运输费用最低的路线 。
1 2 3 4
图 4-2
6
8
4 712
4
4
1
da
eb
h
t
g
fc
s
3
4
11
3
6
9
5
5
3
问题可归结为四阶段决策问题，用动
态规划方法求解如下：
（解法一） 分步计算法
（从第 4阶段开始）
①当 k=4时,i=h或 g,j=t； f5(t)=0
若 i=h,则
? ? thjtfcjfchf htijtj ??????? ? )(,05)()(m in)( *4554
?当 k=3时,i=d或 e,f； j=h或 g
? ? tjtfcjfcgf gtij
tj
????????
?
*
4554,003)()(m i n)(
? ?
gdj
gfc
hfc
jfcdf
dg
dh
ij
ghj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(,11
38
59
m i n
)(
)(
m i n)(m i n)(
*
3
4
4
4
,
3
若 i=g,则
若 i=d,则
若 i=e,则
? ?
hej
gfc
hfc
jfcef
eg
eh
ij
ghj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(,12
312
57
m in
)(
)(
m in)(m in)(
*
3
4
4
4
,
3
若 i=f,则
? ?
gfj
gfcjfcff fgij
gj
????
????
?
)(,835
)()(m in)(
*
3
443
?当 k=2时,i=a或 b,c； j=d或 e,f；
若 i=a,则
? ?
faj
ffc
dfc
jfcaf
af
ad
ij
fdj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;12
84
113
m i n
)(
)(
m i n)(m i n)(
*
2
3
3
3
,
2
? ?
fbj
ffc
efc
dfc
jfcbf
bf
be
bd
ij
fedj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;14
86
124
114
m in
)(
)(
)(
m in)(m in)(
*
2
3
3
3
3
,,
2若 i=b,则
若 i=c,则
? ?
dcj
ffc
dfc
jfccf
cf
cd
ij
fdj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;12
86
111
m in
)(
)(
m in)(m in)(
*
2
3
3
3
,
2
? ?
asj
cfc
bfc
afc
jfcsf
sc
sb
sa
ij
cbaj
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
)(;16
1211
143
124
m i n
)(
)(
)(
m i n)(m i n)(
*
1
2
2
2
2
,,
1
?当 k=1时,i=s; j=a或 b,c；
于是,
目标函数最优值（最低总费用）
R*=f1(s)=16
最优策略是
P*={j1*(s)=a,j2*(a)=f,j3*(f)=g,j4*(g)=t};
s a f g t,或
{s,a,f,g,t} ;
从 s地到 t地总运输费用最低的路线
（ 最优路线）是
（解法二）表格法
16)(1* ?? sfR最小费用：
tgfas ????最优路线：
? ?tggffaasp jjjj ????? )(,)(,)(,)( *****
最优策略：
最终结果
阶段 K j决策集
i状态集
t
4 h 5+0 5 t
g 3+0 3 t
3
h g
d 9+5 8+3 11 g
e 7+5 12+3 12 h
f --- 5+3 8 g
2
d e f
a 3+11 --- 4+8 12 f
b 4+11 4+12 6+8 14 f
c 1+11 --- 6+8 12 d
1 a b c
s 4+12 3+14 11+12 16 a
)(4 ij?
)(3 ij?
)(2 ij?
)(1 ij?
)(4 if
)(3 if
)(2 if
)(1 if
)(1 jfC kij ??
具体步骤：
① 给终点标号 0,先标离终点最近的阶段状
态, 将距离数写在相应的节点上方方格
内；
② 方格内的标号 =min﹛ 欲标号点到已标号
点的距离 +已标号点方格内的数字 ﹜ ；
③ 用直线段连接已标号点到终点的最短路
线 。
（解法三）标号法
da
eb
h
t
g
fc
s
3
4
11
3
4
6
9
7
12
5
5
3
4
4
6
1
8
1 2 3 4
0
5
3
11
12
8
12
14
12
16
2、不定步数问题
①
③
②
④
（ 1） 对无回路的有向网络
方法 1：先对节点排序，适当增加虚设节点，
化为定步数问题，然后按前面的情况求解
例 4-7 将图 4-3化为定步数问题
图 4-3 例 4-7网络图
s
a
b
t
3
4
1
5
2
s b a t4 1 5
a’
0
3 t’
0
2
1 2 3
?增加虚设节点 a’和 t’
?然后，按定步数问题求解
方法 2 先对节点排序，然后采用分步
计算法或表格法，根据最优化原理，逆
序求解。
? 例 4-8 求解图 4-5所示从 s到 t点的网络最短路问题
? 3 a 2 c 5
? s 4 4 t
? 4 1 2 2
? b 4 d
图 4-5
?
ts
a
b
c
d
3
4
1
2
4
2
4
5
2
4
?
? ?
?
?
用表格法逆序求解如下：
j
i
t d c a b
t 0
d 2+0 2 t
c 5+0 4+2 5 t
a 4+2 2+5 6 d
b 4+2 2+5 1+6 6 d
s 3+6 4+6 9 a
)(* ij
)(if)( jfdij ?
? ?tdjdajasjp ???? )(,)(,)( ****
最优策略为
? ?tdas,,,最优路线为
9* ?R从 s到 t的最短距离是
方法 3 二次标号法
? 圆圈内数字为节点序 （ 第一次标号 ） ；
? 方框内数字为该点到终点的最短距离
（ 第二次标号 ） ；
? 红线指示出最短路线为 {s,a,d,t}。
3
4
1
4
2
2
4
4
2
5
a ? c ?
s ? t ?
b d
? ?
9
6
0
5
26
??圆圈内数字为节点序 （ 第一次标号 ） ；
??方框内数字为该点到终点的最短距离
（ 第二次标号 ） ；
??红线指示出最短路线为 {s,a,d,t}。
（ 1） 一般情况下的不定步数问题
? 方法 1：函数迭代法
? ?
??
?
?
?
?
????
0)(
1,,2,1,)(m in)(
Nf
NijfCif ij
j
?
设 表示由 i点出发到终点 N的最短距离,
则 DP基本方程为
)(if
?基本思想,段数作参数, 分别求最优, 优
中再选优, 随之定段数 。
?步骤：
（ 1） 选初始函数
?
?
?
?
???
N0
1,,2,1)(1
i
NiCif iN ?
表示由 i点出发向终点 N走一步
的最短距离 。
)(if
? ?
??
?
?
?
??
???? ?
10)(
1,,2,1)(m i n)( 1
kNf
NijfCif kij
jk
?
（ 2） 定义
按此递推关系求出,
其中 表示由 i出发朝固定点 N走 k步的最
短长度 。
当 时, 迭代停止,
可以证明 n≤N-1。
就是 i到 N点的最短距离, N为阶段数,
? ? 1,,2,1)( ?? Niif k ?
)(ifk
1,,2,1)()(1 ???? Niifif nn ?
)(ifk
例 4-9 用函数迭代法求图 4-6中各点到节点 5的
最短路 。
?先写出距离矩阵
1
32
4
5
5
2
2
6
7 5
3
0.5
5
1
图 4-6
Cij j
i 1 2 3 4 5
1 0 6 5 2 2
2 6 0 0.5 5 7
3 5 0.5 0 1 5
4 2 5 1 0 3
5 2 7 5 3 0
用表格形式书写的距离矩阵
?
?
?
?
??
0)5(
4,3,2,1)(
1
51
f
icif i根据 选初始函数为：
3)4(,5)3(,7)2(,2)1( 451351251151 ???????? cfcfcfcf
迭代表格如下：
j
i 1 2 3 4 5
1 2 7 5 3 0
2 2 5.5 4 3 0
3 2 4.5 4 3 0
4 2 4.5 4 3 0
j* 5 3 4 5
)(ifk
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=1
1
2
3
4
f1(i)=ci5,f1(5)=0 i=1,2,3,4
f1（ 1） =c15=2
f1（ 2） =c25=7
f1（ 3） =c35=5
f1（ 4） =c45=3
① ⑤
② ⑤
③ ⑤
④ ⑤
函数迭代法计算过程
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=2
1
2
3
4
f2(i)=min[cij+f1(j)],f2（ 5） =0
f2（ 1） =
=min（ 0+2,6+7,5+5,2+3,2+0） =2
f2（ 2） =
=min（ 6+2,0+7,0.5+5,5+3,7+0） =5.5
f2（ 3） =
=min（ 5+2,0.5+7,0+5,1+3,5+0） =4
f2（ 4） =
=min（ 2+2,5+7,1+5,0+3,3+0） =3
① ⑤
② ③ ⑤
③ ④ ⑤
④ ⑤
)]([m i n 11 jfc jj ?
)]([m i n 12 jfc jj ?
)]([m i n 13 jfc jj ?
)]([m i n 14 jfc jj ?
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=3
1
2
3
4
f3(i)=min[cij+f2(j)],f3(5)=0
f3（ 1） =
=min（ 0+2,6+5.5,5+4,2+3,2+0） =2
f3（ 2） =
=min(6+2,0+5.5,0.5+4,5+3,7+0)=4.5
f3（ 3） =
=min（ 5+2,0.5+5.5,0+4,1+3,5+0） =4
f3（ 4） =
=min（ 2+2,5+5.5,1+4,0+3,3+0） =3
① ⑤
② ③
④ ⑤
③ ④ ⑤
④ ⑤
)]([m in 21 jfc jj ?
)]([m in 22 jfc jj ?
)]([m in 23 jfc jj ?
)]([m in 24 jfc jj ?
阶段
K
起始
节点
最优指标函数值及其计算公式
（用方框圈出）
相应的
最优策
略
K=4
1
2
3
4
f4（ i） =min[cij+f3（ j） ],f4（ 5） =0
f4（ 1） =
=min(0+2,6+4.5,5+4,2+3,2+0)=2
f4（ 2） =
=min(6+2,0+4.5,0.5+4,3+3,7+0)=4.5
f4（ 3） =
=min（ 5+2,0.5+7,0+5,1+3,5+0） =4
f4（ 4） =
=min（ 2+2,5+4.5,1+4,0+3,3+0） =3
① ⑤
② ③
④ ⑤
③ ④ ⑤
④ ⑤
)]([m in 31 jfc jj ?
)]([m in 32 jfc jj ?
)]([m in 33 jfc jj ?
)]([m in 34 jfc jj ?
根据上面计算，得到如下最终结果,
? ?5)1(** ?? jp ? ?5,1
? ?5)4(,4)3(,3)2( **** ???? jjjp ? ?5,4,3,2
? ?5)4(,4)3( *** ??? jjp ? ?5,4,3
? ?5)4(** ?? jp ? ?5,4
最 优 策 略 最优路线 最短路长
2
4.5
4
3
方法 2：策略迭代法
?给出初始策略 {u0(i)};
?由策略 {uk(i)}求最优指标函数 {fk(i)};
?由最优指标函数 {fk(i)}求策略 {uk+1(i)};
?反复迭代,直至 {uk(i)}= {uk+1(i)}
二、资源分配问题
1,资源的多元分配
? 例 4-10 某公司将 5万元资金投入下属 A、
B,C三个企业, 投放收益见表 4-9,试求
总收益最大的投资方案 。
接 word文档
2、资源的多段分配
? 教材 156页例 4 – 4
三、生产库存问题
教材 P164例 4-5（接 word文档）
四、背包问题
五、其他
小结：
? 深入理解最优化原理
? 掌握建模条件（大前提、条件、方程）
? 记住求解要求
诀窍
多看参考资料
积累一批例子
第八次作业 （习题 4 ）
P175~P177：
用动态规划方法求解
4-1,4-2,4-3,4-5
