即f(Sk)= OPtIk(Sk,uk,…Sn+l) 其中OPt是最优化( OPtimisation)的缩写,可根据题意取max或min 在引例中,指标函数Vkn表示在第k阶段由点Sk至终点E的距离。f(sk) 表示第k阶段点Sk到终E的最短距离。f2(B1)=10表示从第2阶段中的点B1 到点E的最短距离。 7、基本方程(递推关系式) 从引例求A到E的最短路的计算过程中可以看出,在求解的各个阶段, 我们利用了k阶段与k+1阶段之间的递推关系 f(s)=min U, (s,, dk)+f2 SK+) d4()∈D4(SA)(k=4,32.1) f(s3)=0 般地, 若Vn=∑,,d则有 IK(sk)=OPIUK (Sk, dk )+/2+(Sk+), dk∈D(Sk)k=n,n-1,…1 fn(Sn)=0(边界条件) 若Vn=∏U(s,d)则有 f(s)=0p{(,d4)f1(3) d4(S)∈D(Sk),(k=n,n-1,…1) fn(Sn)=l(边界条件) 以上递推关系式称为动态规划的基本方程。 、动态规划方法的基本思想与最优化原理 1、基本思想:动态规划方法的关键在于正确地写出基本方程,因此首先 必须将问题的过程划分为多个相互联系的多阶段决策过程,恰当地选取状态变 量和决策变量及定义最优指标函数,从而把问题化成一族冋类型的子问题。然 后从边界条件开始,逆过程行进方向,逐段递推寻优。在每个子问题求解时
6 即 fk(Sk)=0PtVk,n(Sk,uk,…Sn+1) 其中 0Pt 是最优化（0Ptimiyation）的缩写，可根据题意取 max 或 min。 在引例中，指标函数 Vk,n 表示在第 k 阶段由点 Sk 至终点 E 的距离。fk(sk) 表示第 k 阶段点 Sk 到终 E 的最短距离。f2(B1)=10 表示从第 2 阶段中的点 B1 到点 E 的最短距离。 7、基本方程（递推关系式） 从引例求 A 到 E 的最短路的计算过程中可以看出，在求解的各个阶段， 我们利用了 k 阶段与 k+1 阶段之间的递推关系； ( ) ( ) ( ) ( ) ( ) ( ) ( ) = = = + + + 0 , 4,3,2,1 min , 5 5 1 1 f s d s D S k f s U s d f s k k k k k k k k k k k 一般地， 若 ( ) = = n j k Vk n U j S j d j , , , 则有 = = − = + + + + + ( ) 0( ) ( ) , 1, 1 ( ) 0 ( , ) ( ) , 1 1 1 1 n n 边界条件 k k k k k k k k k k f s d D s k n n f s Pt U s d f s 若 = = n j k k n j j d j V , U (s , ),则有 = = − = + + + + ( ) 1( ) ( ) ( ),( , 1, 1) ( ) 0 ( , ) ( ) 1 1 1 1 n n 边界条件 k k k k k k k k k k k f s d s D s k n n f s pt U s d f s 以上递推关系式称为动态规划的基本方程。 三、动态规划方法的基本思想与最优化原理 1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先 必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变 量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然 后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时
均利用它前面己求出的子问题的最优化结果依次进行,最后一个子问题所得的 最优解,就是整个问题的最优解。 在多阶段决策过程中,动态规划方法是既把当前的一段和未来的各段分 开,又把当前效益和未来效益结合起来考虑的一种最优化方法。因此,每阶段 决策的选取是从全局来考虑,与该段的最优选择一般是不同的。 动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化 最优化原理 动态规划方法基于R· Bellman等人提出的最优化原理:“作为整个过程 的最优策略具有这样的性质,即无论过去的状态和决策如何,对于先前的决策 所形成的状态而言,余下的诸决策必须构成最优策略。”简言之,“一个最优策 略的子策略总是最优的”。 但是,最优化原理仅是策略最优性的必要条件,而基本方程是策略最优性 的充要条件。由此可见,基本方程是动态规划理论与方法的基础。 §2、动态规划模型的建立与求解 一、构成动态规划模型的条件 建立动态规划模型,就是分析问题并建立问题的动态规划基本方程。为此, 必须满足以下条件 1、将问题的过程划分成恰当的阶段; 2、正确选择状态变量S,使它既能描述过程的演变,又要满足无后效性; 3、确定决策变量dk及每阶段的允许决策集合D(Sk) 4、正确写出状态转移方程 5、正确写出指标函数Vkn的关系式,它应具有以下三个性质 (1)是定义全过程和所有后部子过程上的数量函数;
7 均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的 最优解，就是整个问题的最优解。 在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分 开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段 决策的选取是从全局来考虑，与该段的最优选择一般是不同的。 动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化 性。 2、最优化原理 动态规划方法基于 R·Bellman 等人提出的最优化原理：“作为整个过程 的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策 所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策 略的子策略总是最优的”。 但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性 的充要条件。由此可见，基本方程是动态规划理论与方法的基础。 §2、动态规划模型的建立与求解 一、构成动态规划模型的条件 建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此， 必须满足以下条件： 1、将问题的过程划分成恰当的阶段； 2、正确选择状态变量Sk，使它既能描述过程的演变，又要满足无后效性； 3、确定决策变量 dk 及每阶段的允许决策集合 Dk(Sk)； 4、正确写出状态转移方程； 5、正确写出指标函数 Vk,n 的关系式，它应具有以下三个性质； （1）是定义全过程和所有后部子过程上的数量函数；