数学模型 §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