K=3 ……
7
k＝1 ＝ d(A ,B1) +f2(B1) f1(A)＝min ＝ d(A ,B2) +f2(B2) 5+13 ＝min 3+16
8
=18 u1(A)= B1
(三)基本方程 三 基本方程 fk(Sk)＝min{d(Sk , uk)+ fk+1(Sk+1)} k=6, …1 ＝ f7(S7)＝0 ＝ 或 fk(Sk)＝min{d(Sk , uk)+ fk+1(Sk+1)} k=5, …1 ＝ f6(S6)＝ min{d(S6 , u6)} ＝
0≤u5≤S5
u5 * =S5
14
K=4 f4(S4)＝ max{3u4+5S4 + f5(S5)} ＝
0 ≤ u4 ≤ S4
＝ max{3u4+5S4 +8(0.9S4- 0.2u4)}
0 ≤ u4 ≤ S4
＝ max{1.4u4+12.2S4}
0 ≤ u4 ≤ S4
＝ 13.6S4
u4 * =S4
2
(5)最优指标函数： 最优指标函数： 最优指标函数 fk (Sk)：第k段，在Sk状态时到终点 的最 状态时到终点G的最 ： 段 短距离 (6)阶段效益： 阶段效益： 阶段效益 d(Sk ，uk)为第 段，采取策略 k 到下一状 为第k段 采取策略u 为第 态的距离
3
例1 最短路径问题
1 5
C1
15
K=3 f3(S3)＝ max{3u3+5S3 + f4(S4)} ＝
0 ≤ u3 ≤ S3
＝ max{3u3+5S3 +13.6(0.9S3- 0.2u3)}
0 ≤ u3 ≤ S3
＝ max{0.28u3+17.24S3}
0 ≤ u3 ≤ S3
＝ 17.5S3
u3 * =S3
16
K=2 f2(S2)＝ max{20.7S2-0.5u2} ＝
§5.2
动态规划的基本概念和基本方程
(一)基本概念 一 基本概念 (1)阶段：k 阶段： 阶段 (2)状态变量：Sk 状态变量： 状态变量 (3)决策变量： uk(Sk) 决策变量： 决策变量 (4)策略 策略 (5)状态转移方程： Sk＋1 ＝T (Sk ， uk) 状态转移方程： ＋ 状态转移方程 (6)指标函数： Vk，n (Sk) 指标函数： ， 指标函数 (7)最优指标函数： fk (Sk) 最优指标函数： 最优指标函数
9
例2 已知某种完好的机器1000台， 台 已知某种完好的机器 高负荷时 低负荷时 S1=8y1 S2=5y2 a=0.7 b=0.9
问：每年初应如何安排分配机器， 每年初应如何安排分配机器， 可使得5年总收益最大？ 可使得 年总收益最大？ 年总收益最大
10
解 (1)阶段：k=1,2,3,4,5 n=5 阶段： 阶段 (2)状态变量 k ：第k年初始的完好设备数 状态变量S 状态变量 年初始的完好设备数 (3)决策变量 k：第k年初始分到高负荷下 决策变量u 决策变量 年初始分到高负荷下 的机器数 Sk- uk：第k年初始分到低负荷下 年初始分到低负荷下 的机器数
1
(二)前例 二 前例 前例1 (1)阶段：k＝1，2，…，6 n=6 阶段： ＝ ， ， ， 阶段 (2)状态变量：Sk－第k阶段所处的位置 状态变量： 状态变量 阶段所处的位置 状态集合 如S2 : (B1 , B2) (3)决策变量 k ：在第 段Sk状态时决定选 决策变量u 在第k段 决策变量 取的下一段的某点 (4)状态转移方程 ：Sk＋1 ＝uk 状态转移方程 ＋
18
第四年567台投入高负荷 台投入高负荷 第四年 S5＝ 0.9S4-0.2u4＝ 0.7S4 ＝397 第五年397台投入高负荷 台投入高负荷 第五年 基本方程 fk(Sk)＝OPT{d(Sk uk)+ fk+1(Sk+1)} k=n, …1 ＝ fk+1(Sk+1)＝0 ＝
19
12
基本方程 fk(Sk)＝max{d(Sk uk)+ fk+1(Sk+1)} k=5, …1 ＝ f6(S6)＝0 ＝
uk
即 fk(Sk)＝max{(3uk+5Sk)+ fk+1(0.9Sk- 0.2uk)} ＝
uk
k=4, …1 f5(S5)＝ max{3uk+5Sk} ＝
uk
13
K=5 f5(S5)＝ max{3u5+5S5}＝8S5 ＝ ＝
3 8
6 3 5
D1
2 2
E1
5 5 E2 2 6
3
B1
8
6 7 6
C2 C3 C4
F1
4
A
3
D2 1 3
2 3
G F2
6 3
B2
3 8 4
D3 3
E3
4
k＝6， f6(F1)＝4 f6(F2)＝3 ＝ ， ＝ ＝ k＝5 ＝ d(E1 ,F1) +f6(F1) f5(E1)＝min )＝ d(E1 ,F2) +f6(F2) 3+4 ＝min 5+3
11
(4)状态转移方程： 状态转移方程： 状态转移方程 Sk＋1 ＝0.7 uk+0.9(Sk - uk)= 0.9Sk - 0.2 uk ＋ (5)最优指标函数： 最优指标函数： 最优指标函数 fk (Sk)—从第 年末采取最优策略的最大收益 从第k-5年末采取最优策略的最大收益 从第 (6)一年收益： 一年收益： 一年收益 d(Sk , uk)=8uk+5(Sk - uk)= 3uk +5Sk
0 ≤ u2 ≤ S2
＝ 20.7S2 K=1 f1(S1)＝23.7 S1 ＝ 当S1＝1000时 时
u2* =0
u1* =0 f1(1000)＝23700 ＝
17
结论 第一年1000台投入低负荷 台投入低负荷 第一年 S2＝ 0.9S1-0.2u1＝ 0.9S1 ＝ 900 第二年900台投入低负荷 第二年 台投入低负荷 S3＝ 0.9S2-0.2u2＝ 0.9S2 ＝ 810 第三年810台投入高负荷 台投入高负荷 第三年 S4＝ 0.9S3-0.2u3＝ 0.7S3 ＝ 567
5
=7 u5(E1)= F1
同理 k＝4 ＝
f5(E2)＝5 u5(E2)＝ F2 ＝ ＝ f5(E3)＝9 u5(E3)＝ F2 ＝ ＝ d(D1 ,E1) +f5(E1)
f4(D1)＝min ＝ d(D1 ,E2) +f5(E2) 2+7 ＝min 2+5 =7 u4(D1)= E2
6
同理
f4(D2)＝6 u4(D2)＝ E2 ＝ ＝ f4(D3)＝8 u4(D3)＝ E2 ＝ ＝