当前位置:首页 >> 理学 >>

清华大学运筹学课件动态规划


动态规划

主要内容 基本概念 多阶段问题 建模与求解 迭代求解方法

基本概念

例、(无阶段划分)最短路问题 下图五个城市,任何两个城市间均有道路相连,往返 路程一样,由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程
v5
2

3
2

v1

6

5
v2

7 5 0.5

v4

5
v3

1

状态与状态集 S ? ?vi , i ? 1,? ,5? 决策与决策集
U ( s ) ? ?vi , i ? 1,? ,5? , ?s ? S

v5

2
v1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

策略与策略集
P ? ?ui ? U ? vi ? , i ? 1,? ,5?

状态转移函数 阶段指标函数

T ( s, u ) ? S , ?s ? S , u ? U ( s )
d ( s, u ), ?s ? S , u ? U ( s )

( d ( s, s ) ? 0 )

问题 对每个初始状态,以极小化阶段指标函数之和为 目标,确定一个能够转移到末状态 v5 的最优策略

v5

2
v1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

马尔可夫(Markov)性(或无后效性) 以任何状态为初始状态进行决策所产生的 效果,不受如何到达这个状态的决策影响

v5

2
v1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

最优性原理 若 v j 在自 vi 到 v5 的最优路线上,那么这条路线 上自 v j 到 v5 的部分就是自 v j 到 v5 的最优路线 理由:马尔科夫性

v5

2
v1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

定义各点到目的地的最优值函数

f ? s ? , ?s ? S

根据最优性原理,最优值函数一定满足最优值方程
f ? s ? ? min d ? s, u ? ? f ?T ? s, u ? ? , ?s ? S
u?U ? s ?

?

?

动态规划的核心是解最优值方程

多阶段问题

(多阶段决策)最短路问题
2
B1 C1 5 8 3 4 6 C2 5

D1

4
A

3 5 6

E1 4
3 F

5
B2

8
7 7

3

D2 2

C3
8
C4

4

1

3

E2

4

D3

选择从 A 至 F 的最短路铺设输油管道

阶段1
s1 u1

阶段2 阶段3 阶段4 阶段5
s2 u2
2

s3 u3

s4 u4

s5 u5

s6

状态 sk 状态集 S k

4

B1

C1 5 8 3 4 6 C2 5

D1
6

3 5

决策 uk
E1 4

A
5

8

3

D2 2
1 3

3
E2

F

决策集 U k ( sk ) 策略
pk ,5 ? ?uk ,? , u5 ?

B2

C3 4 7 8 7 4 C4

D3

策略集 Pk ,5

如: S 2 ? ?B1 , B2 ? U 4 ( D2 ) ? ?E1 , E2 ? Pk ,5 ? ?U k ( sk ),?,U 5 ( s5 )?

2
B1

4

C1 5 8 3 4 6 C2 5

D1

3 5 6

E1 4
3

A

5
B2

8
7 7

3

D2 2

F

C3
8
C4

4

1

3

E2

4

D3

状态转移函数 Tk ( sk , uk ) ? Sk ?1 , ?sk ? Sk , uk ?U k ( sk ) 阶段指标函数 过程指标函数
d k ( sk , uk ), ?sk ? S k , uk ? U k ( sk )
Vk ,5 ( pk ,5 | sk ) ? ? di ? si , ui ?
i ?k 5

用动态规划的术语描述最短路问题 已知 状态集 S k , k ? 1,2,?,6 决策集 U k ( sk ), ?sk ? S k , k ? 1,2,?,5 状态转移函数
Tk ( sk , uk ) ? uk , ?sk ? S k , uk ? U k ( sk ), k ? 1, 2,? ,5

阶段指标函数
d k ( sk , uk ), ?sk ? S k , uk ? U k ( sk ), k ? 1, 2,? ,5

问题

求 p1,5 ? P1,5 使下述过程指标函数达到最小
V1,5 ( p1,5 | s1 ) ? ? d k ? sk , uk ?
k ?1 5

最短路问题的动态规划模型

min V1,5 ( p1,5 | s1 ) ? ? d k ? sk , uk ? s.t. sk ?1 ? Tk ? sk , uk ? , sk ? Sk , uk ? U k ( sk ), 1 ? k ? 5
满足马尔可夫性: 给定 sk ,系统在 k 阶段以后的状态和系统经由什 么路径到达 sk 无关,即和 s1 , s2 ,?, sk ?1 的取值无关
k ?1

5

?

最优值函数一定满足最优值方程
f ? s ? ? min d ? s, u ? ? f ?T ? s, u ? ? , ?s ? S
u?U ? s ?

?

?

多阶段最短路问题的逆推求解 定义最优值函数 f ? s ? 为从 s 到终点的最短路程,并根 据多阶段结构将其表示为
f ? s ? ? f k ? s ? , ?s ? S k , k ? 1,? , 6

终止条件: f ? s ? ? f 6 ? s ? ? 0, ?s ? S6 利用多阶段结构,可得到最优性方程的以下等价式
f ? s ? ? min d ? s, u ? ? f ?T ? s, u ? ?
u?U ? s ?

?

fk ? s ? ?

u?U k s

? min ?d ? ?

? ?

k

? s, u ? ?

f k ?1 ?Tk ? s, u ? ? , ?s ? S k

结论:最优值函数 f ? s ? 可以用以下公式逆推确定
f 6 ( s) ? 0, ?s ? S6
u?U 5 ( s )

f5 ( s ) ? min d5 ? s, u ? ? f 6 ?T5 ? s, u ? ? , ?s ? S5 f 4 ( s) ? min d 4 ? s, u ? ? f5 ?T4 ? s, u ? ? , ?s ? S4 f3 ( s ) ? min d3 ? s, u ? ? f 4 ?T3 ? s, u ? ? , ?s ? S3 f 2 ( s) ? min d 2 ? s, u ? ? f3 ?T2 ? s, u ? ? , ?s ? S2 f1 ( s) ? min d1 ? s, u ? ? f 2 ?T1 ? s, u ? ? , ?s ? S1
u?U1 ( s ) u?U 2 ( s ) u?U 3 ( s ) u?U 4 ( s )

最短路问题的逆推结果(最优决策可由最优值得到)

?12? ?13?
B1

2

?17 ?
A

4

C1 5 8 3 ?10 ? 4 6 C2 5

?7 ?
D1

5

?15?
B2

8
7

?8? 3
C3

?5?6 ?5?
D3

3 5

?4?
E1 4

?0?
F

D2 2

?3? 3
E2

4

1

? 9 ?8 7
C4

3

4

多阶段最短路问题的顺推求解 定义最优值函数 f ? s ? 为从起点到 s 的最短路程,并根 据多阶段结构将其表示为
f ? s ? ? f k ? s ? , ?s ? S k , k ? 1,? , 6

初始条件: f ? s ? ? f1 ? s ? ? 0, ?s ? S1 由于对任意 k 成立 S k ?1 ? Tk ? S k , U k ? S k ? ? ,所以
f ?s? ? ?
T ? s ,u ? ? s s ?S ,u?U ? s ?

min

?d ? s , u ? ? f ? s ??
?d ? s , u ? ? f ? s ?? ,
k k

f k ?1 ? s ? ?

Tk ? s ,u ? ? s s ?S k ,u?U k ? s ?

min

?s ? S k ?1

结论:最优值函数 f ? s ? 可以用以下公式顺推确定
f1 ( s) ? 0, ?s ? S1 f 2 (s) ? f3 ( s) ? f 4 (s) ? f5 ( s) ? f6 (s) ?
T1 ? s ,u ? ? s s ?S1 ,u?U1 ( s ) T2 ? s ,u ? ? s s ?S2 ,u?U 2 ( s ) T3 ? s ,u ? ? s s ?S3 ,u?U 3 ( s ) T4 ? s ,u ? ? s s ?S4 ,u?U 4 ( s ) T5 ? s ,u ? ? s s ?S5 ,u?U 5 ( s )

min

d1 ? s , u ? ? f1 ? s ? , ?s ? S2 d 2 ? s , u ? ? f 2 ? s ? , ?s ? S3 d3 ? s , u ? ? f3 ? s ? , ?s ? S4 d 4 ? s , u ? ? f 4 ? s ? , ?s ? S5 d5 ? s , u ? ? f5 ? s ? , ?s ? S6

min

min

min

min

最短路问题的顺推结果(最优决策可由最优值得到)

?6?
C1 5 ?11? B1 3 ?7 ? 8 D1 3 ?14 ? 4 4 5 E1 4 ?0? ? 6 C2 5 ?126 A ?10? 3 D2 2 ?14? 3 8 5 ?5? C3 4 ?14 ?1 E2 7 3 8 D3 B2 ? 12 ? 7 4 C4
2

?4?

?17 ?
F

一般性动态规划模型(其中 ? 表示某种运算,如加法)

min (or max ) d1 ? s1 , u1 ? ? d 2 ? s2 , u2 ? ??? d n ? sn , un ? s.t.
逆推求解
f n ?1 ( s) ? 0, ?s ? Sn ?1
u?U k ( s )

sk ?1 ? Tk ? sk , uk ? , sk ? Sk , uk ?U k ( sk ), 1 ? k ? n

( 0 的含义根据问题定)

f k ( s ) ? min d k ? s, u ? ? f k ?1 ?Tk ? s, u ? ? , ?s ? Sk , k ? n,? ,1

顺推求解
f1 ( s) ? 0, ?s ? S1 f k ?1 ( s) ?
Tk ? s ,u ? ? s s ?Sk ,u?U k ( s )

min

d k ? s , u ? ? f k ? s ? , ?s ? S k ?1 , k ? 1,? , n

问题:动态规划方法能否保证最优解? 动态规划方法如何节省计算量?

穷举(可保证最优解)
2
B1 C1 5 8 3 4 6 C2 5

D1

4

3 5 6

E1 4
3

A

5
B2

8
7 7

3

D2 2

F

C3
8
C4

4

1

3

E2

4

D3

总路径数

加法次数

2 ? 3 ? 2 ? 2 ? 24

5 ? 24 ? 120

逆推求解

?12? ?13?
B1

2

?17 ?
A

4

C1 5 8 3 ?10 ? 4 6 C2 5

?7 ?
D1

5

?15?
B2

8
7

?8? 3
C3
4

?5?6 ?5?
D3

3 5

?4?
E1 4

?0?
F

D2 2

?3? 3
E2

1

? 9 ?8 7
C4

3

4

加法次数

等价于穷举 无重复计算

2 ? 3 ? 2 ? 4 ? 3 ? 2 ? 2 ? 22

顺推求解

?6? ?4?
B1

2

?0?
A

4

C1 5 8 3 ?7 ? 4 6 C2 5

?11?
D1

5

?5?
B2

8

4 ?14 ?1 3 7 8 D3 ? 12 ? 7 4 C4

?10? 3
C3

?126 ?

3 5

?14?
E1 4

?17 ?
F

D2 2

?14? 3
E2

加法次数

等价于穷举 无重复计算

? 2 ? 2 ? 2 ? ? ? 2 ? 2 ? 4 ? ? 3 ? 2 ? 2 ? 22

建模与求解

投资分配问题 10万元资金,投资三个项目,收益分别为
2 g1 ( x1 ) ? 4 x1 , g 2 ( x2 ) ? 9 x2 , g 3 ( x3 ) ? 2 x3

如何分配投资额? 上述问题可以表示成非线性规划问题
2 max 4 x1 ? 9 x2 ? 2 x3

s.t. x1 ? x2 ? x3 ? 10 xi ? 0, i ? 1,2,3

不是凸规化,用非线性优化算法不能保证得到最优解

建立序贯决策模型 阶段 状态 决策 状态集 允许决策集 阶段指标 三个决策阶段,顺序决策三个项目投资额

k 阶段开始可用投资额 sk
k 阶段实际投资额 xk

S1 ? ?10? , S k ? ? 0, 10? , k ? 2,3, 4
U k ? s ? ? ? 0, s ? , k ? 1, 2,3

d1 ? s, x ? ? 4 x, d 2 ? s, x ? ? 9 x, d3 ? s, x ? ? 2 x 2
Tk ? s, x ? ? s ? x, k ? 1, 2,3

状态转移函数

逆推求解( f k ( s) 表示 k 及以后阶段总收益) 逆推公式
f 4 ( s) ? 0, ?s ? S4
x?U k ( s )

f k ( s ) ? max d k ? s, x ? ? f k ?1 ?Tk ? s, x ? ? , ?s ? Sk

?s ? S3 : f3 ( s ) ? max 2 x 2 ? 2s 2
0? x ? s

?s ? S2 : f 2 ( s ) ? max 9 x ? 2 ? s ? x ? ? max ?2s 2 ,9s?
2 0? x ? s

(凸函数最大值在边界达到)
?s ? S1 ? s ? 10 : f1 (10) ? max 4 x ? max ?2(10 ? x) 2 ,9(10 ? x)? ? max ?2 ?102 ,9 ?10, 4 ?10? ? 200
0? x ?10

由最优值定最优决策
* * * * * * x1* ? 0, s2 ? 10 ? x1* ? 10, x2 ? 0, s3 ? s2 ? x2 ? 10, x3 ? 10

顺推求解( f k ( s) 表示 k 阶段以前总收益) 顺推公式
f1 ( s) ? 0, ?s ? S1 f k ?1 ( s) ?
s ? x?s s ?S1 ,0? x ? s

s ? x?s s ?Sk , x?U k ( s )

max

d k ? s , x ? ? f k ? s ? , ?s ? S k ?1

f 2 ( s) ? max 4 x ? max 4 x ? 4 ?10 ? s ?
10 ? x ? s 0? x ? s

f3 ( s ) ? max 9 x ? 4 ?10 ? s ? ? max 9 x ? 4 ?10 ? s ? x ? ? 9 ?10 ? s ?
s ? x?s 0? s ?10 0? x ? s 0 ? x ?10 ? s

f 4 ( s) ? max 2 x 2 ? 9 ?10 ? s ? ? max 2 x 2 ? 9 ?10 ? s ? x ?
s ? x?s 0 ? s ?10 0? x ? s 0 ? x ?10 ? s

? max 9 ?10 ? s ? , 2 ?10 ? s ?
?

?

2

?

* * * * * s4 ? 0, x3 ? 10, s3 ? 10 ? 0 ? 10, x2 ? 0, s2 ? 0 ? 10 ? 10, x1* ? 0

连续状态变量的离散化求解方法 连续状态变量动态规划问题关键是求解下述递推方程
f k ( s) ? min d k ? s, u ? ? f k ?1 ?Tk ? s, u ? ? , ?s ? S k
u?U k ( s )

只有在特殊情况下才能得到 f k ( s) 的解析表达式

一般情况下,可以用离散点集近似连续状态变量集 S k 将原问题近似转换成和最短路问题类似的多阶段问题

投资分配问题的离散化求解方法 将连续区间 ?0, 10? 离散化为有限点集 ?0, 2,4,6,8,10?
0
0
2 4

等价于 求右边 的最长 路问题
10

2
? 4
6

? ?
?

0

6 8
10

8
10

4 ? ?s1 ? s2 ?

9 ? ?s2 ? s3 ?

2 ? ?s3 ? s4 ?

2

逆序求解

?0? ?18?
4 ? ?72? ? 6 ?128? ? 8 ?200? ? 10
9 ? ?s2 ? s3 ?

?0?

0

?8?
?32? ?72? ?128? ?200?
10
2 ? ?s3 ? s4 ?
2

0

?36?

2

2

?200?

10

4

0

?0?

6 8

4 ? ?s1 ? s2 ?

顺序求解

? 40 ?
0 ? 32 ?

? 90 ? ? 72 ?
2
0

? 0 ? 10

2 ? 24 ? 4 ? ?16 ? ? 6 ?8? ? 8 ? 0?
10

? 54 ?

? 36 ?
?18 ?
8 6

4

0 ? 200 ?

? 0?
10
9 ? ?s2 ? s3 ? 2 ? ?s3 ? s4 ?
2

4 ? ?s1 ? s2 ?

背包问题 10吨卡车,装三种货物,单位重量和价值如下 货物编号 单位重量(吨) 单位价值 1 3 4 2 4 5 3 5 6

如何装载使总价值最大? 静态优化模型
max 4 x1 ? 5 x2 ? 6 x3 s.t. 3 x1 ? 4 x2 ? 5 x3 ? 10 x1 , x2 , x3 非负整数

这是一个NP难问题

建立序贯决策模型 阶段 状态 决策 状态集 三个决策阶段,顺序决策三种货物装载量

k 阶段开始可用装载量 sk ,s1 ? 10
k 阶段实际装载量 xk

0 ? sk ? s1 , s4 ? 0 3 x1 ? s1 , 4 x2 ? s2 , 5 x3 ? s3 ,xk 非负整数

允许决策集 阶段指标

4 x1 , 5 x2 , 6 x3

状态转移方程 s2 ? s1 ? 3x1 , s3 ? s2 ? 4 x2 , s4 ? s3 ? 5 x3

转化成最长路问题
10

0
5 10

10

0
6
12

10

7
6

? ?
6
5

0

4 10 8 12

7

0
5

4

6

4

0
5

2

0 3 0
1

4
3

1

0

0 0

2

1
0

0

状态转移 阶段指标

s2 ? s1 ? 3x1 , s3 ? s2 ? 4 x2 , s4 ? s3 ? 5 x3 4 x1 , 5 x2 , 6 x3

顺序求解

? 0? 0
5 10 ? 4? 0 7 5
10

? 0?

0

4 10 8 12

?8?

0 4 5 0

? 5? 6 ? 8? 6 4 ?9? 0
3

0 10 ? 4? 6 7 12

10

? ?
6
5
4 3 2

?12 ?
1

?10 ? 2 ?12 ? 0 1 ?13? 0 0

0

1
0

? 9? ?10 ? ?12 ? ?13?

最优解

* * x1* ? 2, x2 ? 1, x3 ? 0 最优目标 f3 (0) ? 13

旅行商问题 下图四个城市,任何两个城市间均有道路相连,路程 由图中数字所示。从 v1 出发,找出一条经过其他每个 城市最终回到 v1 的最短路线
v1

6

8
6 9 5 8

v2

9

7 5

8 5 7
v4

v3

转换成多阶段决策问题 直接以城市为状态会存在后效性问题,如下图,v3 处的 容许决策取决于第二阶段状态值
v2 v2 v2

v1

v3
v4

v3
v4

v3
v4

v1

无后效性的状态设置方法
sk ,i : k 步到达城市 vi , 1 ? k ? 3, 2 ? i ? 4

v2 | v3 5

v2 | ?v3 , v4 ?

8
v1

5 6

v2 8 5 9 v3 5 7 v4 8

v2 | v4 8
v3 | v2 5 v3 | v4

6
v3 | ?v2 , v4 ? 7 v1 | ?v2 , v3 , v4 ?

9 8

v4 | v2

v4 | ?v2 , v3 ?

9

v4 | v3 7

逆推求解

?14 ? ? 20 ?
v2 8 5 ? 23? 8 18 9 ? ? 5 v1 v3 6 5 7 v4 8 ? 22 ?

v2 | v3 5 ?15? v2 | v4 8 ?14 ? v3 | v2 5 ?15? 9 v3 | v4 ?15? 8 v4 | v2

? 6?
v2 | ?v3 , v4 ?

6

?7?
v3 | ?v2 , v4 ? 7

? 0?
v1 | ?v2 , v3 , v4 ?

?13?

?9? 9 v4 | ?v2 , v3 ?

v4 | v3 7

v1 ? v3 ? v4 ? v2 ? v1 最优路程: 23 最优路径:

迭代求解方法

值迭代方法

(无阶段划分)最短路问题 下图五个城市,任何两个城市间均有道路相连,往返 路程一样,由图中数字所示。求每个城市到第五个城 市的最短路线和最短路程
v5
2

3
2

v1
6 5
v2

7 5
0.5

v4 5
v3
1

d ? s, u ? ? f ?T ? s, u ? ?? , ?s ? S ? 最优值方程: f ? s ? ? umin ?U ? s ?

值迭代方法 首先取 f1 ? vi ? ? d ? vi , v5 ? , 1 ? i ? 5 然后对 k ? 1 按下述公式迭代
f k ?1 ? vi ? ? min d ? vi , v j ? ? f k ? v j ?
1? j ? 5

v5
2

3
2

v1

?

?

6

5
v2

7 5
0.5

v4 5
v3
1

如果到某个 k 满足 f k ?1 ? vi ? ? f k ? vi ? , ?1 ? i ? 5
min ?d ? vi , v j ? ? f k ? v j ?? , ?1 ? i ? 5 那么就成立 f k ? vi ? ? 1 ? j ?5

于是得到最优值方程的解

f ? vi ? ? f k ? vi ? , ?1 ? i ? 5

最优路线可以由最优值函数确定

直接在图上进行值迭代
f1 ? vi ? ? d ? vi , v5 ?

? 2?
f 2 ? vi ? ? min d ? vi , v j ? ? f1 ? v j ?
1? j ? 5

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

?

?

v1

7 5 0.5

5
v3

? 2?
v1

v5

? 0?
3

1

2 2
6 5
v2

? 3?
v4

?7?

? 5?

7 5 0.5

5

1

? 5.5 ?

v3 ? 4 ?

f 2 ? vi ?

? 2?
f 3 ? vi ? ? min d ? vi , v j ? ? f 2 ? v j ?
1? j ? 5

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

?

?

v1

7 5 0.5

5

1

? 2?
v1

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

? 5.5 ?

v3 ? 4 ?

7 5 0.5

5

1

? 4.5 ?

v3 ? 4 ?

f 3 ? vi ?

? 2?
f 4 ? vi ? ? min d ? vi , v j ? ? f 3 ? v j ?
1? j ? 5

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

?

?

v1

7 5 0.5

5

1

? 2?
v1

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

? 4.5?

v3 ? 4 ?

7 5 0.5

5

1

?

? 4.5?

v3 ? 4 ?

f 4 ? vi ? ? f 3 ? vi ? , ?i

根据最优值确定最优路线

? 2?
v1

v5

? 0?
3

2 2
6 5
v2

? 3?
v4

7 5 0.5

5

1

? 4.5?
最优路线: v1 ? v5

v3 ? 4 ?

最优值:

2
4.5

v2 ? v3 ? v4 ? v5 v3 ? v4 ? v5 v4 ? v5

4 3

保证最短路问题的值迭代法收敛的充要条件: 没有总路程之和小于零的回路
v5

例如,右图不满足条件
v3 ? v4 ? v5 ? v3 ? ?1 v1
6

2

3
2 7 ?5

v4 5
v3
1

理由: f1 ? vi ? ? d ? vi , v5 ?
f k ?1 ? vi ? ? min d ? vi , v j ? ? f k ? v j ?
1? j ? 5

5
v2

?

?

0.5

f k ?1 ? vi ? 就是 vi 经过不超过 k 个中转城市到达目的

? 地的最短路,城市数有限,最后必重复,没有负回

路的重复不可能减少任何点的总路程

策略迭代方法

无回路策略 一个策略就是在每个点的某种 决策构成的集合,写成
P ? ? p (vi ), 1 ? i ? 5?

v5

2
v1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

其中 p (vi ) 表示 vi 后面城市的下标

没有决策在一个回路上的策略称为无回路的策略 例如:下面是无回路的策略
p (v1 ) ? 4, p (v2 ) ? 4, p (v3 ) ? 4, p (v4 ) ? 5, p (v5 ) ? 5

下面不是无回路的策略
p (v1 ) ? 4, p (v2 ) ? 1, p (v3 ) ? 2, p (v4 ) ? 3, p (v5 ) ? 5

策略迭代法(策略空间迭代法) 任意选取一个无回路策略 P 1 ? ? p1 (vi ), 1 ? i ? 5? 求解线性方程组
f k ? vi ? ? ci pk ( vi ) ? f k v pk ( vi ) , ?1 ? i ? 4 f k ? v5 ? ? 0

?

?

? ? v ? , ?1 ? i ? 5 (无回路的策略保证方程有唯一解) 得 f k i ? ? v ? , ?1 ? i ? 5 确定改进的策略 利用 f k i

Pk ?1 ? ? pk ?1 (vi ), 1 ? i ? 5?

改进途经

? ? v ci pk ?1 ( vi ) ? f k pk ?1 ( vi ) ? min cij ? f k ? v j ? , ?1 ? i ? 4
1? j ? 5

?

?

?

?

重复上述过程直到策略不改变

有(无)回路的策略和方程组的关系 有回路策略
p (v1 ) ? v4 , p (v2 ) ? v1 p (v3 ) ? v2 , p (v4 ) ? v3 p (v5 ) ? v5
f k ? v1 ? ? c14 ? f k ? v4 ?

?

f k ? v2 ? ? c21 ? f k ? v1 ? f k ? v3 ? ? c32 ? f k ? v2 ? f k ? v4 ? ? c43 ? f k ? v3 ?

无解

无回路策略
p (v1 ) ? 4, p (v2 ) ? 4 p (v3 ) ? 4, p (v4 ) ? 5 p (v5 ) ? 5

f k ? v1 ? ? c1 4 ? f k ? v4 ?

?

f k ? v2 ? ? c24 ? f k ? v4 ? f k ? v3 ? ? c34 ? f k ? v4 ? f k ? v4 ? ? c45 ? f k ? v5 ?

? ?v ? , f ? ?v ? , f ? ?v ? ? ?v ? ? f f k ? v5 ? ? 0 ? f k 4 k 1 k 2 k 3

用策略迭代法解最短路问题的例子
p1 (v1 ) ? 4, p1 (v2 ) ? 4 p1 (v3 ) ? 4, p1 (v4 ) ? 5 p1 (v5 ) ? 5
f1 ? v1 ? ? 2 ? f1 ? v4 ? f1 ? v2 ? ? 5 ? f1 ? v4 ? f1 ? v3 ? ? 1 ? f1 ? v4 ? f1 ? v4 ? ? 3 ? f1 ? v5 ?

v5

2
v1
? ?v ? ? 5 f 1 1

3

2
6 5
v2

7 5 0.5

v4

5
v3

1

?

? ?v ? ? 8 f 1 2 ? ?v ? ? 4 f 1 3 ? ?v ? ? 3 f 1 4

? v ? ? v ? , ?1 ? i ? 4 min ci p2 ( vi ) ? f ? c ? f 1 p2 ( vi ) ij 1 j
1? j ? 5

?

?

?

?

?

p2 (v1 ) ? 5, p2 (v2 ) ? 3, p2 (v3 ) ? 4, p2 (v4 ) ? 5, p1 (v5 ) ? 5

继续迭代
p2 (v1 ) ? 5, p2 (v2 ) ? 3 p2 (v3 ) ? 4, p2 (v4 ) ? 5, p2 (v5 ) ? 5 v1
f 2 ? v1 ? ? 2 ? f 2 ? v5 ? f 2 ? v2 ? ? 0.5 ? f 2 ? v3 ? f 2 ? v3 ? ? 1 ? f 2 ? v4 ? f 2 ? v4 ? ? 3 ? f 2 ? v5 ?

v5

2 2
6 5
v2

3 7 5 0.5
v4

? ?v ? ? 2 f 2 1

5
v3

1

? ? f 2 ? v3 ? ? 4

? ? v ? ? 4.5 f 2 2 ? ?v ? ? 3 f 2 4

? v ? ? v ? , ?1 ? i ? 4 min ci p3 ( vi ) ? f ? c ? f 2 p3 ( vi ) ij 2 j
1? j ?5

?

?

?

?

?

p3 (v1 ) ? 5, p3 (v2 ) ? 3, p3 (v3 ) ? 4, p3 (v4 ) ? 5, p3 (v5 ) ? 5 P3 ? P2

停止

最优策略
p3 (v1 ) ? 5, p3 (v2 ) ? 3, p3 (v3 ) ? 4, p3 (v4 ) ? 5, p3 (v5 ) ? 5

最优路径:

v1 ? v5 v2 ? v3 ? v4 ? v5

v3 ? v4 ? v5
v4 ? v5

同值迭代法结果一样


相关文章:
清华大学运筹学课件动态规划_图文.pdf
清华大学运筹学课件动态规划 - 动态规划 主要内容 基本概念 多阶段问题 建模与
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
第八、九讲 动态规划(运筹学-清华大学,林谦)_图文.ppt
规划所求解问题的不同情况可采用后向(逆序) 动态规划和前向(顺序)动态规划两种...运筹学课件8 动态规... 95页 2下载券 运筹学第四版清华大学......
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学课件-动态规划_图文.ppt
运筹学课件-动态规划 - ? 第13章 动态规划 教学目标与要求 ? ? ? ?
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学课件(动态规划)分析_图文.ppt
运筹学课件(动态规划)分析 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化的...
运筹学课件第9章动态规划_图文.ppt
运筹学课件第9章动态规划 - 第9章 动态规划 教学目标与要求 ? ? ? ?
运筹学课件动态规划_图文.ppt
运筹学课件动态规划 - 第十章 动态规划(DP) Dynamic Program
运筹学-第3版-课件-第5章 动态规划_图文.ppt
第5章 动态规划 运筹帷幄之中 Dynamic Programming 决胜千里之外第 1页 综 述 动态规划运筹学的一个分支,是解决多阶段决策问题的一 种最优化方法。与线性规划...
运筹学课件8.动态规划(2010.6.10)_图文.ppt
运筹学课件8.动态规划(2010.6.10)_工学_高等教育_教育专区。合肥工业大学运筹学老师课件 第八章 动态规划 (Dynamic programming) 五十年代贝尔曼( 五十年代...
第三讲 动态规划 (高级运筹学课件)_图文.ppt
第三讲 动态规划 (高级运筹学课件)_理学_高等教育_教育专区。(高级运筹学课件) 第三讲 动态规划 (Dynamic Programming) 动态规划是 1951 年由美国数学家贝尔曼( ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学课件第9章 动态规划.ppt
运筹学课件运筹学课件隐藏>> 第9章 动态规划 重庆三峡学院 关文忠
运筹学课件第9章_动态规划_图文.ppt
运筹学课件第9章_动态规划 - 第9章 动态规划 教学目标与要求 ? ? ? ?
运筹学清华大学第三版课件_图文.ppt
运筹学清华大学第三版课件 - 运筹学(第三版)(本科版) 教学课件 钱颂迪 陈秉正 1 清华大学出版社 运筹学(第三版)(本科版)教学课件 本教学课件为方便教学,供...
运筹学课件--清华大学李明老师_图文.ppt
运筹学课件--清华大学李明老师 - Page 1 运筹学 ( Operation
运筹学第七章2007_图文.ppt
运筹学第七章2007 - 运筹学基础 主讲教师: 联系电话: 短号: E-mail: 教材 《运筹学教程》(第三版) 胡运权 主编 清华大学出版社 运筹学课件运筹帷幄...
更多相关文章: