工程数学-201107(6)

第三章 动态规划

动态规划是多阶段决策问题，相对地，线性规划、非线性规划问题称为静态规划问题。

§1 最优化原理

全局最优，则局部最优。（如何理解）

最短路问题

B E A F

22

b

2

① 1 3 2 7 3 4 6

e

c

② 7 a

5 ③ 1 ⑤ 3 ⑦ 6 f

d

8 ⑥ 2

u0 4 ④

g

4

货郎问题

设f(vi,V)表示从vi出发，经过V中的所有点恰一次后回到v0的最佳路线总长度，则所求的就是f(v0,{v1,v2,?,vn})。

?d01?f(v1,{v2,v3,?,vn}),??d?f(v2,{v1,v3,?,vn}),?f(v0,{v1,v2,?,vn})?min?02? ?,?d?f(v,{v,v,?,v})?n12n?1?0n??d12?f(v2,{v3,v4,?,vn}),??d?f(v3,{v2,v4,?,vn}),?f(v1,{v2,v3,?,vn})?min?13? ?,?d?f(v,{v,v,?,v})?n23n?1?1n?f(vi,V)?min?dij?f(vj,V?vj)?

vj?V例：

v0 v1 v3 v2

??d01?f(v1,{v2,v3}),??f(v0,{v1,v2,v3})?min?d02?f(v2,{v1,v3}),?

??d03?f(v3,{v1,v2})????d12?f(v2,{v3}),??f(v1,{v2,v3})?min??

??d13?f(v3,{v2})??

§2 用最优化原理解非线性规划问题

就下面的非线性规划问题，讨论最优化原理解题思想，并具

23

体求解该题

22?maxF?4x12?x2?2x3?12?t3x1?2x2?x3?9 ?s..?x1,x2,x3?0?f3(9)?max{2x32?12?f2(9?x3)}

0?x3?9f2(y)?max{?x22?f1(y?2x2)}

0?2x2?yf1(z)?max{4x12}

0?3x1?z

z2解得：f1(z)?4，故

9(y?2x2)2f2(y)?max{?x2?4}0?2x2?y927164?max{x22?yx2?y2}0?2x2?y999784?max{(x2?y)2???y2}0?2x2?y979?42y9

f3(9)?max{2x32?12?f2(9?x3)}0?x3?94?max{2x32?12?(9?x3)2}0?x3?99?max{0?x3?9222x3?8x3?12?36}92218(x3?)2??}911

?max{0?x3?9?17424

25

§3 动态规划算法设计

填表的思想及优势

fn=fn-1+fn-2 f100 f1=1 f2=1 1 1 2 3 5 8 13 21 ……..

1．博弈论中的一个问题

甲乙两人对弈，胜算概率相同，求“甲再胜i盘胜利，乙再胜j盘胜利”时甲胜利的概率。

i?0,j?0?1,?f(i,j)??0,i?0,j?0

?1[f(i-1,j)?f(i,j-1)],i?0,j?0?2 0 1 2 i

2．划分问题

用动态规划思想，设计填表法，求解下面的划分问题 在集合A＝｛a1，a2，?，an｝上定义正整数函数s，令

0 / 0 0 0 1 1 1/2 1/4 2 1 3/4 1/2 ? j 1 26

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库工程数学-201107(6)在线全文阅读。