数学模型 §1.5动态视剡 动态规划是一类多阶段决策过程的最优 化方法。 基本方法是:按阶段把一个大问题化成 系列相互有联系的子问题,建立相应 的递推公式,解一系列的子问题,最后 求得整个问题的最优解
§1.5 动态规划 动态规划是一类多阶段决策过程的最优 化方法。 基本方法是：按阶段把一个大问题化成 一系列相互有联系的子问题，建立相应 的递推公式，解一系列的子问题，最后 求得整个问题的最优解
动态规划的基本概念和基本方法(数学丝 例最短路问题 B 3 76 E 8 6 3 阶段 2 3 求A到E的最短路。 从A到E的路有:3×3×2×1=18(条)
例 最短路问题 一、动态规划的基本概念和基本方法 E B1 D2 D1 A B3 B2 C3 C2 C1 2 4 3 7 4 6 3 2 4 4 1 5 1 4 6 3 3 3 3 4 7 11 7 8 4 6 3 4 11 0 1 2 3 4 阶段 从A到E的路有： 3 3 21 = 18 (条) 求A到E的最短路。 4 5 7 8 9 10 12 13
(数学模型 1.概念 阶段:根据时间或空间划分。本例按空间分成4个阶段 状态:某阶段出发的位置。 既是某支路本阶段的起点,又是前一阶段 的终点。 本例4个阶段的状态集: (母},{B1,B2,B3,{C1,C2,C3},{D1,D2B, 状态变量s:描述状态的变量 s1的取值:A s2的取值:B1,B2,B3 S3的取值:C1,C2,C3 s4的取值:D,D2
1. 概念 • 阶段： 根据时间或空间划分。 • 状态： 某阶段出发的位置。 既是某支路本阶段的起点，又是前一阶段 的终点。 本例按空间分成4个阶段 本例4个阶段的状态集： {A}, { , , }, B1 B2 B3 { , , }, C1 C2 C3 { , }, D1 D2 • 状态变量 sk : 描述状态的变量。 s1 的取值：A 2 1 2 3 s 的取值：B ,B ,B 3 1 2 3 s 的取值：C ,C ,C 4 1 2 s 的取值：D ,D #
数学模型) 决策:从给定状态到下一阶段某状态的选择。 决策变量xk=xk(sk):描述决策的变量 如:x1(A)=B1,路程为2;x1(A)=B2,路程为4 本例可记为A→B1;A→B2 有:x1∈X1={B1,B2,B3; x2∈X2={C1,C2,C3} x3∈X3={D1,D2}; 容许决策集合 4∈X4={E}. 状态转移方程:描述状态转移规律的函数关系 k+1 =T(S k 9k 策略:决策序列 4 KAD
• 决策： 从给定状态到下一阶段某状态的选择。 • 决策变量 xk=xk (sk )： 描述决策的变量。 如： ( ) , 2; x1 A = B1 路程为 ( ) , 4. x1 A = B2 路程为 有： { , , }; x1 X1 = B1 B2 B3 { , , }; x2 X2 = C1 C2 C3 { , }; x3 X3 = D1 D2 { }. x4 X4= E 容许决策集合 • 状态转移方程：描述状态转移规律的函数关系 ( , ) k 1 k xk s = T s + • 策略：决策序列 1 2 本例可记为 A → B ;A → B 4 2
如:(x(4)=B,x(B)=C,x:(2)=D,X团1)=E {x1(4)=B2,x2(B2)=C1,x3(C1)=D1,x4(D1)=E 本例共有18个策略,欲从中选出最优策略(路长最短者)。 ·k子策略:策略中,从第k个决策开始到最后一个 决策所成之子序列。 如: {x2(B2)=C1,x3(C1)=D1,x4(D1)=E x3(C1)=D1,x4(D1)=E ·报酬函数:一决策对应的“费用”,记为 k(k, k 如:v2(B1,x2(B1)=C2)=4(B1→>C2,的路程) KAD
如： { ( ) , ( ) , ( ) , ( ) } x1 A = B1 x2 B1 = C2 x3 C2 = D1 x4 D1 = E { ( ) , ( ) , ( ) , ( ) } x1 A = B2 x2 B2 = C1 x3 C1 = D1 x4 D1 = E 本例共有18个策略，欲从中选出最优策略(路长最短者)。 • k 子策略： 策略中，从第k个决策开始到最后一个 决策所成之子序列。 如： { ( ) , ( ) , ( ) } x2 B2 = C1 x3 C1 = D1 x4 D1 = E { ( ) , ( ) } x3 C1 = D1 x4 D1 = E • 报酬函数: 一决策对应的“费用”，记为 ( , ) k k xk v s 如： v2 (B1 , x2 (B1 ) = C2 ) = 4 （B1 → C2 ,的路程）2 5
数学模型 目标(指标)函数:衡量策略好坏的函数。 从Sk出发到终点的目标函数记为: kn(k,kg xn),k=1,2,…, 视Sk为确定状态,k,…n是变化的 ·从sk出发到终点的最优目标值: f(Sk)=opt vk,(sk,xk,,xn) k=1, 2,...,n (opt为min或max) 例中:f(4)为A到E的最短路程, 相应的策略为所求的最优策略—最短路。 f∫(Sk)对应的策略为Sk到终点最优子策略。 KAD
• 目标（指标）函数：衡量策略好坏的函数。 从 sk 出发到终点的目标函数记为： vkn(sk , xk , , xn ), k = 1,2, ,n 视 sk 为确定状态， xk , , xn 是变化的。 • 从 sk 出发到终点的最优目标值： ( ) ( , , , ) , , kn k k n x x f k sk opt v s x x k n = (opt 为 min 或 max) k = 1,2, ,n 例中： ( ) f1 A 为A 到E 的最短路程， 相应的策略为所求的最优策略— 最短路。 ( ) k k f s 对应的策略为 sk 到终点最优子策略。 2 6
(数学模型 2.最优化原理 例中:有最优策略 {x1(4)=B2,x2(B2)=C1,x3(C1)=D1,x4(D1)=E 即{A→B2→C1→>D1→B A到E的最短路,路长为f(A)=11 子策略:{B2→>C1→>D1→E} B2到E的最短路,路长为f2(B2)=7 {C1→D1→E} C1到E的最短路,路长为∫(C1)=4 # KAD
2. 最优化原理 例中：有最优策略 { ( ) , ( ) , ( ) , ( ) } x1 A = B2 x2 B2 = C1 x3 C1 = D1 x4 D1 = E 即 { } A → B2 → C1 → D1 → E 1 ( ) = 11 —A到E的最短路，路长为 f A 子策略： { } B2 → C1 → D1 → E — B2到E的最短路，路长为 2 ( 2 ) = 7 f B { } C1 → D1 → E — C1到E的最短路，路长为 3 ( 1 ) = 4 f C …… 7 2 #
(数学模型 最优策略有性质一最优化原理: 无论过去的状态和决策如何,对某确定的状态, 余下的决策必须构成最优子策略。 或,对某状态而言,该状态到终点的最优策略 只与后面的选择有关,与前面的选择无关。 或,已知现在,将来与过去无关。 即后部子问题的最优策略是父问题的最优子策略。 #
最优策略有性质—最优化原理： 无论过去的状态和决策如何，对某确定的状态， 余下的决策必须构成最优子策略。 或，对某状态而言，该状态到终点的最优策略 只与后面的选择有关，与前面的选择无关。 或，已知现在，将来与过去无关。 即后部子问题的最优策略是父问题的最优子策略。 8 2 #
(数学模型 利用该原理得寻优方法: 行进方向 问题:A E 寻伏方向 子问题: 将问题化成一系列相互有联系的子问题 先求出“最小子问题”中,各状态到E的最优子策略, 再求出“次小子问题”中(第3阶段),各状态到 E的最优子策略,如此向前推进,而每次都利用后 部子问题中已得到的最优子策略。 如:已得C1到E的最优子策略:C1→>D1→B 在求B2到E的最住走法时,如果该阶段取B2→C1 KAD
利用该原理得寻优方法： 问题： A E 子问题： 行进方向 寻优方向 先求出“最小子问题”中，各状态到E的最优子策略， 将问题化成一系列相互有联系的子问题， 再求出“次小子问题”中（第3阶段），各状态到 E的最优子策略，如此向前推进，而每次都利用后 部子问题中已得到的最优子策略。 如：已得C1到E的最优子策略： { } C1 → D1 → E 在求B2到E的最佳走法时，如果该阶段取 B2 → C1 9 2
(数学模型 则后面的最佳走法是:C1→D1→E} 即得最优子策略:{B2>C1→>D1>E} 在第1阶段,若取A→B2,则得A到E的最佳走法: A→B2>C1→D1→>E} 如果是A→>B1,则利用B1到E的最佳走法得: (A→B→C2→D2→E} 或 A→B1→>C1→D1>E} 减少了计算量,即不必再验证后面走法的最优性; 丰富了结果,即得从任何一点出发到终点的最短路。 KAD
则后面的最佳走法是： 即得最优子策略： { C1 → D1 → E } B2 → { } C1 → D1 → E 在第1阶段，若取 A → B2 ，则得A到E的最佳走法： {A → B2 → C1 → D1 → E } 如果是 A → B1 ，则利用B1到E的最佳走法得： {A → B1 → C2 → D2 → E } {A → B1 → C1 → D1 → E } 或 • 减少了计算量，即不必再验证后面走法的最优性； • 丰富了结果，即得从任何一点出发到终点的最短路。 2 10