第三部分动态规划（书第五部分） 动态规划为运筹学的一个分支，是解决多阶段决策过程最优化问题的一种数学方法，产生于50年 代。美R.Bellman(1951),将多阶段决策问题转化为一系列互相联系的单阶段问题，然后逐个加以解决， 提出了“最优性原理”，并研究了许多实际问题，创立了动态规划。 动态规划是现代企业管理中的一种重要的决策方法，可用来求解最优路线问题、资源分配问题、生 产调度问题、库存问题、排序问题、生产过程最优控制问题，特别对于离散性问题较有效，是有用的工 具。 动态规划是求解某类问题的一种方法，考察问题的一种途径，而不是一种特殊算法（不像线性规划）。 因而不像线性搞活那样有标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处 理。应以丰富的想象力去建立模型，用创造性的技巧去求解。 动态规划的模型分类： 1.离散决策过程和连续决策过程（根据多阶段决策过程的时间参量是离散的还是连续的变量）。 2.确定性决策过程和随机性决策过程（根据决策过程的演变是确定性的还是随机性的）。 组合起来有：离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。 本部分主要研究确定性决策过程，第四章介绍动态规划的基本概念、理论和方法，第五章将通过典 型问题来说明它的应用。 第四章动态规划的基本方法（书第8章) §4.1多阶段决策过程及实例（书§8.1） 有一类活动的过程，可分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整 个过程达到最好的活动效果，因此各个阶段的决策不是任意确定的，它依赖于当前面临的状态，又影响 以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动 路线。这种将一个问题看作是一个前后关联具有链状结构的多阶段过程，称为多阶段决策过程。 决策 决策 决策 状态 状态……状态 ·状态 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态， 又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，因此把 处理它的方法称为“动态规划方法”。 一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因 素，也可把它视为多阶段决策问题，用动态规划方法去处理。 例4.1.1（最短路线问题，P192图8-2）给定一个线路网络，两点之间连线上的数字表示两点间的距 离（或费用）。试求一条由A到G的路线，使总距离为最短（或总费用最小）。 例4.1.2（机器负荷分配问题）某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生 产时，产品的年产量g和投入生产的机器数量u的关系为g=g(),这时机器的年完好率为a,0<a<1,即 如果年初完好机器的数量为“，到年终时完好的机器就为au。在低负荷下生产时，产品的年产量h和投 入生产的机器数量u的关系为h=h(),这时机器的年完好率为b,0<b<1,即如果年初完好机器的数量为 弘，到年终时完好的机器就为b。假定开始时完好的机器数量为S1。要求制定一个五年计划，在每年开 始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最 高
1 第三部分 动态规划（书第五部分） 动态规划为运筹学的一个分支，是解决多阶段决策过程最优化问题的一种数学方法，产生于 50 年 代。美 R.Bellman(1951)，将多阶段决策问题转化为一系列互相联系的单阶段问题，然后逐个加以解决， 提出了“最优性原理”，并研究了许多实际问题，创立了动态规划。 动态规划是现代企业管理中的一种重要的决策方法，可用来求解最优路线问题、资源分配问题、生 产调度问题、库存问题、排序问题、生产过程最优控制问题，特别对于离散性问题较有效，是有用的工 具。 动态规划是求解某类问题的一种方法，考察问题的一种途径，而不是一种特殊算法（不像线性规划）。 因而不像线性搞活那样有标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处 理。应以丰富的想象力去建立模型，用创造性的技巧去求解。 动态规划的模型分类： 1.离散决策过程和连续决策过程（根据多阶段决策过程的时间参量是离散的还是连续的变量）。 2.确定性决策过程和随机性决策过程（根据决策过程的演变是确定性的还是随机性的）。 组合起来有：离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。 本部分主要研究确定性决策过程，第四章介绍动态规划的基本概念、理论和方法，第五章将通过典 型问题来说明它的应用。 第四章 动态规划的基本方法（书第 8 章） §4.1 多阶段决策过程及实例(书§8.1) 有一类活动的过程，可分为若干个互相联系的阶段，在它的每一个阶段都需要做出决策，从而使整 个过程达到最好的活动效果，因此各个阶段的决策不是任意确定的，它依赖于当前面临的状态，又影响 以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动 路线。这种将一个问题看作是一个前后关联具有链状结构的多阶段过程，称为多阶段决策过程。 决策 决策 决策 状态 状态 … … 状态 状态 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态， 又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，因此把 处理它的方法称为“动态规划方法”。 一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因 素，也可把它视为多阶段决策问题，用动态规划方法去处理。 例 4.1.1 (最短路线问题，P192 图 8-2)给定一个线路网络，两点之间连线上的数字表示两点间的距 离（或费用）。试求一条由 A 到 G 的路线，使总距离为最短（或总费用最小）。 例 4.1.2（机器负荷分配问题）某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生 产时，产品的年产量 g 和投入生产的机器数量 u 的关系为 g=g(u)，这时机器的年完好率为 a,0<a<1, 即 如果年初完好机器的数量为 u, 到年终时完好的机器就为 au。在低负荷下生产时，产品的年产量 h 和投 入生产的机器数量 u 的关系为 h=h(u)，这时机器的年完好率为 b,0<b<1, 即如果年初完好机器的数量为 u, 到年终时完好的机器就为 bu。假定开始时完好的机器数量为 s1。要求制定一个五年计划，在每年开 始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最 高
还有其他的资源（人力，物力）分配问题、生产贮存问题、最优装载问题、水库优化问题、最优控 制问题等等，都具有多阶段决策问题的特性，均可用动态规划方法去求解。 §4.2动态规划的基本概念和基本方程（书§8.2） 下面通过讨论例1.1(P192图8-2)的解法来说明动态规划的基本思想，并阐述基本概念。 从A到G分6个阶段：A到B,B到C,C到D,D到E,E到F,F到G。 在第1阶段，A为起点，有2个选择：→B1,→B2。若选择→B1,则得到下阶段的起点B1,若选择 →B2,则得到下阶段的起点B2。如果所做的决策是→B2,则得到下阶段的起点为B2。 在第2阶段，对起点B2,有3个选择：→C2,→C3,C4。若选择→C2,则得到下阶段的起点C2, 若选择→C3,则得到下阶段的起点C3,若选择→C4,则得到下阶段的起点C4。如果所做的决策是→C2, 则得到下阶段的起点为C2。 依次类推，可看到各个阶段所做的选择不同，则得到的路线就不同。 很明显，当某阶段的起点给定时，它直接影响后面各阶段的行进路线和整个路线的长短，而后面各 阶段路线的发展不受这点以前各阶段路线的影响。 故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的 一条路线为最短其路线。 方法一：枚举法，即把由A到G的所有可能的路线的距离都算出来，互相比较得最短者。 可能的路线个数：2×3×2x2×2×1=48。 显然此方法计算相当繁，计算量大，当段数很多时，不现实。 方法二：动态规划方法。 4.2.1动态规划的基本概念 (1)阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。 阶段的划分一般根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策过程。 用k表示第k个阶段。 如在例4.1.1中，根据空间位置把问题的过程划分为6个阶段，分别用=1,23,4,5,6表示。 (2)状态：表示每个阶段开始时所处的自然状况或客观条件，它描述了研究问题过程的状况，又 称不可控因素，用$4表示第k个阶段的状态。通常，一个阶段可有若干个状态，这些状态的集合称为允 许状态集，用S表示第k个阶段的允许状态集，显然S4∈S4。 如在例41.1中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路 的终点。第一阶段有1个状态就是A,第二阶段有2个状态，即B1,B2,因此s1∈S={A},S2∈S2={B1, B2} 状态必须具有如下性质。 无后效性（马尔科夫性）：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各 段状态的影响。换句话说：过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以 往历史的一个总结。 (3)决策：表示当过程处于某一阶段的某个状态时，可以作出的不同决定（或选择），从而确定 下一阶段的状态。用，(s)表示第k个阶段状态为s%时所做的决策以得到第什1阶段的状态。通常，在 状态S联处有若干个决策可供选择，这些决策的集合称为允许决策集，U(s)表示，显然(s)∈U4(S)。 如在例4.1.1，h(B2)∈U2(B2)={→C2,→C3,→C4}
2 还有其他的资源（人力，物力）分配问题、生产贮存问题、最优装载问题、水库优化问题、最优控 制问题等等，都具有多阶段决策问题的特性，均可用动态规划方法去求解。 §4.2 动态规划的基本概念和基本方程(书§8.2) 下面通过讨论例 1.1（P192 图 8-2）的解法来说明动态规划的基本思想，并阐述基本概念。 从 A 到 G 分 6 个阶段：A 到 B，B 到 C，C 到 D，D 到 E，E 到 F，F 到 G。 在第 1 阶段，A 为起点，有 2 个选择：→B1，→B2。若选择→B1，则得到下阶段的起点 B1，若选择 →B2，则得到下阶段的起点 B2。如果所做的决策是→B2，则得到下阶段的起点为 B2。 在第 2 阶段，对起点 B2，有 3 个选择：→C2，→C3，→C4。若选择→C2，则得到下阶段的起点 C2， 若选择→C3，则得到下阶段的起点 C3，若选择→C4，则得到下阶段的起点 C4。如果所做的决策是→C2， 则得到下阶段的起点为 C2。 依次类推，可看到各个阶段所做的选择不同，则得到的路线就不同。 很明显，当某阶段的起点给定时，它直接影响后面各阶段的行进路线和整个路线的长短，而后面各 阶段路线的发展不受这点以前各阶段路线的影响。 故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的 一条路线为最短其路线。 方法一：枚举法，即把由 A 到 G 的所有可能的路线的距离都算出来，互相比较得最短者。 可能的路线个数：2×3×2×2×2×1=48。 显然此方法计算相当繁，计算量大，当段数很多时，不现实。 方法二：动态规划方法。 4.2.1 动态规划的基本概念 （1）阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。 阶段的划分一般根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策过程。 用 k 表示第 k 个阶段。 如在例 4.1.1 中，根据空间位置把问题的过程划分为 6 个阶段，分别用 k=1,2,3,4,5,6 表示。 （2）状态：表示每个阶段开始时所处的自然状况或客观条件，它描述了研究问题过程的状况，又 称不可控因素，用 sk表示第 k 个阶段的状态。通常，一个阶段可有若干个状态，这些状态的集合称为允 许状态集，用 Sk表示第 k 个阶段的允许状态集，显然 sk∈Sk。 如在例 4.1.1 中，状态就是某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某支路 的终点。第一阶段有 1 个状态就是 A，第二阶段有 2 个状态，即 B1，B2，因此 s1∈S1={A}，s2∈S2={B1， B2}。 状态必须具有如下性质。 无后效性（马尔科夫性）：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各 段状态的影响。换句话说：过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以 往历史的一个总结。 （3）决策： 表示当过程处于某一阶段的某个状态时，可以作出的不同决定（或选择），从而确定 下一阶段的状态。用 uk(sk)表示第 k 个阶段状态为 sk时所做的决策以得到第 k+1 阶段的状态。通常，在 状态 sk处有若干个决策可供选择，这些决策的集合称为允许决策集，Uk(sk)表示，显然 uk(sk)∈Uk(sk)。 如在例 4.1.1，u2(B2)∈U2(B2)={→C2，→C3，→C4}
(4)状态转移方程：确定过程由一个状态到另一个状态的演变过程。若给定第k阶段的状态，则 当该段的决策4一经确定，第k+1阶段的状态S+1也就完全确定，即s+1的值随s和4的值变化而变化。 把这种确定的对应关系，记为sk+=T(Sk,),它描述了由k阶段到k+1阶段的状态转移规律，称为状态 转移方程。 如例4.1.1中，如果S2=B2,为→C2,则s3=C2,即=T2(B2,→C2=C2。 (5)策略：是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程， 称为问题的k后子过程。由k后子过程中每段的决策按顺序排列组成的决策序列{(S),+1(S+),… 山n(s)}称为k后子过程策略。记为 Pn(S)={uk(S,+i(s+i）,…,n(sn）} 其中s+=TS%),…,Ssm=Tm1(Sm-l,-)。当k=1时，P1n()称为全过程策略，简称策略。 显然，Pn()={(S),Pk+1n(S+i)},其中Sk+1=T(Sk,)。 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集，用P(S)表示。显然， Bsx)={(k,Pk+,n川山：∈Uk(S),Pk+n∈P+1n(Sk+i),Sk+1=T(Sk,山)}。从允许策略集中找出达到最优 效果的策略，称为最优策略。 (6)指标函数：用来衡量所实现过程优劣的一种数量指标。 阶段指标函数：用来衡量一个阶段优劣的一种数量指标，用(S%)表示第k阶段状态为s%所做决 策为时的指标函数。 k后子过程指标函数：用来衡量k后子过程优劣的一种数量指标，用 'kn(Sk,,Sk+l,k+l,…,Sm,m,Sn+l） 表示，其中s+1=T(S%k),,…,S+1=TSn山n)。特别地， ,,产立y,（G,西)一和式 i=k 或 (s4s+1,h,…,Smn+1F石y,（S,4）—乘式 = 如在例4.1.1中，指标函数的含义为距离。当s2=B2,为→C2时，阶段指标函数2(S2,)=d(B2,C2=8, 后子过程的指标函数是阶段指标函数的和。 当S给定，k后子过程策略P(s)给定，则k后子过程的指标函数'n也就确定了，故可记 Vn(SkPn(Sx)）='n(Skk,sk+l,+l,…,Sm4,Sn+I） (T)最优值函数：指标函数的最优值，即'(S,P,(s)在最优策略下的值，它表示从第k阶段状 态s开始到第n阶段终止在最优策略下的指标函数值，记作(s)。因此 fi(Sk)=opt Vkn(sk,pkn(SK)) Pkn(5g )EPn(5k) 其中“op”表示“min”或“mar”,最优解即为最优策略，记作Pk,n(Sk)。 如在例4.1.1中，(s)表示s到G的最短距离。 4.2.2动态规划的基本思想和基本方程 1.最短路线的特性 如果由起点S经过P点和H点而到达终点E是一条最短路线，则由点P出发经过H点到达E点的这 条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定是最短路线。 3
3 （4）状态转移方程: 确定过程由一个状态到另一个状态的演变过程。若给定第 k 阶段的状态 sk，则 当该段的决策 uk一经确定，第 k+1 阶段的状态 sk+1也就完全确定，即 sk+1 的值随 sk和 uk的值变化而变化。 把这种确定的对应关系，记为 sk+1=Tk(sk,uk)，它描述了由 k 阶段到 k+1 阶段的状态转移规律，称为状态 转移方程。 如例 4.1.1 中，如果 s2 =B2，u2 为→C2，则 s3=C2，即=T2(B2,→C2)=C2。 （5）策略： 是一个按顺序排列的决策组成的集合。由过程的第 k 阶段开始到终止状态为止的过程， 称为问题的 k 后子过程。由 k 后子过程中每段的决策按顺序排列组成的决策序列{uk(sk), uk+1(sk+1),… un(sn)}称为 k 后子过程策略。记为 pk,n(sk)={uk(sk), uk+1(sk+1),…，un(sn)} 其中 sk+1=Tk(sk,uk)，…，sn=T n-1(sn-1,un-1)。当 k=1 时，p1,n(s1)称为全过程策略，简称策略。 显然，pk,n(sk)= {uk(sk), pk+1,n(sk+1)}，其中 sk+1=Tk(sk,uk)。 在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集，用 Pk,n(sk)表示。显然， Pk,n(sk)= 1, 1, 1, 1 1 {( , ) | ( ), ( ), ( , )} k kn k k k kn knk k k k k u p u U s p P s s Tsu + + + ++ ∈∈ = 。从允许策略集中找出达到最优 效果的策略，称为最优策略。 （6）指标函数：用来衡量所实现过程优劣的一种数量指标。 阶段指标函数：用来衡量一个阶段优劣的一种数量指标，用 vk(sk,uk)表示第 k 阶段状态为 sk所做决 策为 uk时的指标函数。 k 后子过程指标函数：用来衡量 k 后子过程优劣的一种数量指标，用 Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1) 表示，其中 sk+1=Tk(sk,uk), ,…，sn+1=Tn(sn,un)。特别地， Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1)= (, ) n jjj j k vsu = ∑ ——和式 或 Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1)= (, ) n jj j j k π vsu = ——乘式 如在例 4.1.1 中，指标函数的含义为距离。当 s2=B2,u2 为→C2 时，阶段指标函数 v2(s2,u2)=d(B2,C2)=8， 后子过程的指标函数是阶段指标函数的和。 当 sk给定，k 后子过程策略 pk,n(sk)给定，则 k 后子过程的指标函数 Vk,n 也就确定了，故可记 Vk,n(sk,pk,n(sk))=Vk,n(sk,uk,sk+1,uk+1,…,sn,un,sn+1) （7）最优值函数：指标函数的最优值，即 Vk,n(sk,pk,n(sk))在最优策略下的值，它表示从第 k 阶段状 态 sk开始到第 n 阶段终止在最优策略下的指标函数值，记作 fk(sk)。因此 fk(sk)= , , () () kn k kn k p sPs opt ∈ Vk,n(sk,pk,n(sk)) 其中“opt”表示“min”或“max”，最优解即为最优策略，记作 * , ( ) kn k p s 。 如在例 4.1.1 中，fk(sk)表示 sk到 G 的最短距离。 4.2.2 动态规划的基本思想和基本方程 1. 最短路线的特性 如果由起点 S 经过 P 点和 H 点而到达终点 E 是一条最短路线,则由点 P 出发经过 H 点到达 E 点的这 条子路线,对于从点 P 出发到达终点的所有可能选择的不同路线来说，必定是最短路线
例4.1.1中，若A到B1到C2到D1到E2到F2到G是A到G的最短路线，则D1到E2到F2到G应 是由D,到G的所有可能选择的不同路线中的最短路线。（反证） 根据最短路线的特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法， 求出各点到G点的最短路线，最后求得由A到G的最短路线。 所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 下面按照动态规划的方法，将例4.1.1从最后一段开始计算，由后向前逐步推移至A点。 k-6时，由F1到G只有一条路线，故f6F)=4,f6(F2=3,6(F1):→G,6(F2:→G。 =5时，出发点E1,E2,E3三个。若从点E1出发，则有→F1,→F2,则 f5(E1=min{d(E1,F)+f6(Fi),d(Ei,F2tf6(F2)}=min{3+4,5+3}=7 其相应的决策为us(E)上→F1,这说明E1到终点G的最短距离为7，最短路线E,到F到G。 同理，从E2,E3出发有： Fs(E2=min{d(E2,Fi+f6(Fi),d(E2,F2+f6(F2)}=min{3+4,2+3=5 其相应的决策为u(E2):一F2, Fs(E3)=min{d(E3,Fitf6(F),dE3,F2)+f6F2)}=min{6+4,6+3}=9 且us(E):→F2。 类似地： k=4时，f4(DF7,4(D)→E2,f4D2F6,4(D2):→E2,fD3=8,4(D3→E2。 k=3时，(C1=13,(C1)→D1,f(C2)=10,s(C2:→D1,f(C3=9,s(C3:→D2,(C4)=12,u3(C4:→D3。 k=2时，(B1尸13,2(B1):→C2,(B2)尸16,2(B2)→C3。 k=1时，f(4)=min{d(A,Btf(B1),d(A,B2tf5(B2)}=min{5+13,3+16}=18,(A):→B1。 于是从起点A到终点G的最短距离为18。 为寻找最短路线，再按计算的顺序反推之，求得最优决策函数序列{；，即 u1(A):→B1,u2(B1):→C2,u(C2:→D1,4(D1→E2,us(E2:→F2,6(F2):→G 组成一个最优策略，最短路线为：A到B1到C2到D到E2到F2到G。 从上面的计算过程可以看出，在求解的各个阶段，利用k阶段与+1阶段之间的递推关系： fs)=4R(4)+f(T,4},k=5,43,2,1 f6(S6)=v(s6,→G)=d(s6,G) 一般情况下，k阶段与+1阶段的递推关系式可写为： [f(s)=opt{y(sk,44)+f+(T(s,4)},k=n-1,…,1 (s) (4.2.1) f(s)=opt v(su) u.EU(sn） 即 f(s)=opI{v(,4s)+f(T(s,4a},k=n,…,1 4Ek(级) (4.2.2) (S)=0 递推关系(4.2.1)和(4.2.2)称为动态规划的基本方程。 递推关系(4.2.1)和(4.2.2)中，相应的最优解即为最优决策4，(S)。 2.动态规划方法的基本思想 (1)动态规划方法的关键在于写出基本的递推关系式和恰当的边界条件（简言之为基本方程）
4 例 4.1.1 中，若 A 到 B1到 C2 到 D1到 E2 到 F2到 G 是 A 到 G 的最短路线，则 D1 到 E2 到 F2 到 G 应 是由 D1 到 G 的所有可能选择的不同路线中的最短路线。（反证） 根据最短路线的特性,寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法， 求出各点到 G 点的最短路线，最后求得由 A 到 G 的最短路线。 所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 下面按照动态规划的方法，将例 4.1.1 从最后一段开始计算，由后向前逐步推移至 A 点。 k=6 时，由 F1 到 G 只有一条路线，故 f6(F1)=4，f6(F2)=3，u6(F1)：→G，u6(F2)：→G。 k=5 时，出发点 E1，E2，E3 三个。若从点 E1 出发，则有→F1，→F2，则 f5(E1)=min{d(E1, F1)+ f6(F1), d(E1, F2)+ f6(F2)}=min{3+4, 5+3}=7 其相应的决策为 u5(E1)= →F1，这说明 E1 到终点 G 的最短距离为 7，最短路线 E1 到 F1到 G。 同理，从 E2, E3 出发有： F5(E2)=min{d(E2, F1)+ f6(F1), d(E2, F2)+ f6(F2)}=min{3+4, 2+3}=5 其相应的决策为 u5(E2):→ F2， F5(E3)=min{d(E3, F1)+ f6(F1),d(E3, F2)+ f6(F2)}=min{6+4, 6+3}=9 且 u5(E3):→ F2。 类似地： k=4 时, f4(D1)=7，u4(D1):→ E2，f4(D2)=6，u4(D2):→ E2，f4(D3)=8，u4(D3):→ E2。 k=3 时, f3(C1)=13，u3(C1):→D1，f3(C2)=10，u3(C2):→ D1，f3(C3)=9，u3(C3):→D2，f3(C4)=12，u3(C4):→D3。 k=2 时, f2(B1)=13，u2(B1):→C2，f2(B2)=16，u2(B2):→C3。 k=1 时, f1(A)=min{d(A, B1)+f2(B1), d(A, B2)+f2(B2)}=min{5+13, 3+16}=18，u1(A):→ B1。 于是从起点 A 到终点 G 的最短距离为 18。 为寻找最短路线，再按计算的顺序反推之，求得最优决策函数序列{uk}，即 u1(A):→ B1，u2(B1):→C2，u3(C2):→D1，u4(D1):→E2，u5(E2):→ F2，u6(F2):→G 组成一个最优策略，最短路线为：A 到 B1 到 C2到 D1 到 E2到 F2 到 G。 从上面的计算过程可以看出，在求解的各个阶段，利用 k 阶段与 k+1 阶段之间的递推关系： 1 ( ) 66 66 6 ( ) min { ( , ) ( ( , ))}, 5,4,3,2,1 () (, ) (,) k kk kk kk k k kk k uUs fs vsu f Tsu k f s v s G ds G + ∈ ⎧ =+ = ⎪ ⎨ ⎪⎩ = →= 一般情况下，k 阶段与 k+1 阶段的递推关系式可写为： 1 ( ) ( ) ( ) { ( , ) ( ( , ))}, 1, ,1 ( ) { ( , )} k kk n nn kk kk k k k k uUs nn nn n uUs f s opt v s u f T s u k n f s opt v s u + ∈ ∈ ⎧ = + =− ⎪ ⎨ = ⎪ ⎩ " (4.2.1) 即 1 ( ) 1 1 ( ) { ( , ) ( ( , ))}, , ,1 ( )0 k kk kk kk k k k k uUs n n f s opt v s u f T s u k n f s + ∈ + + ⎧ =+ = ⎪ ⎨ ⎪⎩ = " (4.2.2) 递推关系(4.2.1)和(4.2.2)称为动态规划的基本方程。 递推关系(4.2.1)和(4.2.2)中，相应的最优解即为最优决策 ( ) k k u s 。 2. 动态规划方法的基本思想 （1）动态规划方法的关键在于写出基本的递推关系式和恰当的边界条件（简言之为基本方程）
先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量，以及定义指标函数和 最优值函数，把大问题化成一族同类型的子问题，逐个求解，即从边界条件开始，逐段递推寻优，在每 一个子问题的求解中，均利用了它前面的子问题的最优化结果。依次进行，最后一个子问题所得的最优 解就是整个问题的最优解。 (2)在多阶段决策过程中，动态规划方法既把当前一段和未来各段分开，又把当前效益与未来效 益结合起来考虑，因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般不同。 (3)由于初始状态己知，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可 逐次变换得到，从而确定了最优路线。 如例411，初始状态A己知，则按下面箭头所指的方向逐次变换有： 4(A):→B 4(B)→C24(C2)→D 4,(D)→E2 4(E2)→F34,(E)→G C2 +E2 2 G 上述最短路线问题的计算过程，也可借助如下图形直观简明的表示出来。(PI98) 用直线连接的点表示该点到终点G的最短路线，未用直线连接的点说明它不是该点到终点G的最短 路线，圈上的数表示该点到终点G的最短距离。 上述在图上直接作业的方法叫标号法。 如果规定从A点到G点为顺行方向，则由G点到A点为逆行方向，从G点开始从后向前标号的解法 称为逆序解法。 由于从A点计算到G点和从G点计算到A点的最短路线是相同的，因而标号也可以由A开始从前向 后标号，视G点为起点，A为终点，按动态规划方法处理。以G为始端A为终端，从A到G的解法称为 顺序解法。 由上可见，顺序解法和逆序解法只表示行进方向的不同或对始端终端看法的颠倒。 但用动态规划方法求最优解时，都是在行进方向规定后，均逆着这个规定的行进方向，从最后一段 向前递推计算，逐段寻找最优途径。 3.动态规划与穷举法的比较 (1)计算量少。 (2)丰富了计算结果。在逆序（或顺序）解法中，不仅得到了由A(G)到G(A)的最短路线及相应的 最短距离，而且得到了从所有各中间点出发到$G(A)$的最短路线及相应的距离。亦即求出的不是一个最 优策略，而是一族的最优策略。 4.建立动态规划模型的前提 建立动态规划模型时，需做到： (1)将问题的过程划分为恰当的阶段： (2)正确选择状态变量$%，使它既能描述过程的演变，又能满足无后效性： (3)确定决策变量4及每阶段的允许决策集合U4(S): (4)正确写出状态转移方程s+1=T八s%,): (5)正确写出k后子过程的指标函数'km的关系，满足三个性质： (a)是定义在全过程和所有后部子过程上的数量函数： (b)具有可分离性，并满足递推关系，即
5 先将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量，以及定义指标函数和 最优值函数，把大问题化成一族同类型的子问题，逐个求解，即从边界条件开始，逐段递推寻优，在每 一个子问题的求解中，均利用了它前面的子问题的最优化结果。依次进行，最后一个子问题所得的最优 解就是整个问题的最优解。 （2）在多阶段决策过程中，动态规划方法既把当前一段和未来各段分开，又把当前效益与未来效 益结合起来考虑，因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般不同。 （3）由于初始状态已知，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可 逐次变换得到，从而确定了最优路线。 如例 4.1.1，初始状态 A 已知，则按下面箭头所指的方向逐次变换有: 1 1 uA B ( ):→ 21 2 uB C ( ):→ 32 1 uC D ( ):→ 41 2 uD E ( ):→ 52 2 uE F ( ):→ 6 2 uF G ( ):→ A B1 C2 D1 E2 F2 G 上述最短路线问题的计算过程，也可借助如下图形直观简明的表示出来。(P198) 用直线连接的点表示该点到终点 G 的最短路线，未用直线连接的点说明它不是该点到终点 G 的最短 路线，圈上的数表示该点到终点 G 的最短距离。 上述在图上直接作业的方法叫标号法。 如果规定从 A 点到 G 点为顺行方向，则由 G 点到 A 点为逆行方向，从 G 点开始从后向前标号的解法 称为逆序解法。 由于从 A 点计算到 G 点和从 G 点计算到 A 点的最短路线是相同的，因而标号也可以由 A 开始从前向 后标号，视 G 点为起点，A 为终点，按动态规划方法处理。以 G 为始端 A 为终端，从 A 到 G 的解法称为 顺序解法。 由上可见，顺序解法和逆序解法只表示行进方向的不同或对始端终端看法的颠倒。 但用动态规划方法求最优解时，都是在行进方向规定后，均逆着这个规定的行进方向，从最后一段 向前递推计算，逐段寻找最优途径。 3. 动态规划与穷举法的比较 （1）计算量少。 （2）丰富了计算结果。在逆序（或顺序）解法中，不仅得到了由 A(G)到 G(A)的最短路线及相应的 最短距离，而且得到了从所有各中间点出发到$G(A)$的最短路线及相应的距离。亦即求出的不是一个最 优策略，而是一族的最优策略。 4．建立动态规划模型的前提 建立动态规划模型时，需做到： （1）将问题的过程划分为恰当的阶段； （2）正确选择状态变量 sk，使它既能描述过程的演变，又能满足无后效性； （3）确定决策变量 uk及每阶段的允许决策集合 Uk(sk)； （4）正确写出状态转移方程 sk+1=T(sk,uk)； （5）正确写出 k 后子过程的指标函数 Vk,n 的关系，满足三个性质： （a）是定义在全过程和所有后部子过程上的数量函数； （b）具有可分离性，并满足递推关系，即
Vn(Sk,4k,…,Sn,4n,Sa+l)=(Sk,山g,'k+n(Sk4,kl,…,n,n,Sn+i》 即yn(S,Pn(S》=Ψ(S,4e,'n(S1P+n(》,其中Pn（)=4,P+(i}，s1=TS,4)。 (C)(S,4,'4n)对于变量V4n严格单调。 例如，设指标函数是取各阶段指标函数之和的形式，即Vn（S,4,,,4,5)=∑y(S,4,), 则 Vn(Sk,k,…,5n,4n,Sa+i)=V%(Sk,4g)+V+ln(Sk+1,山kl,…,Sn,4n,Sn+i） 即 Vin(SkPn(S))=V(5xu)+Vn(5 Pn(5) m显然满足指标函数的三个性质。 上述五点是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素。而一个问题的动 态规划模型是否正确给出，集中反映在恰当地定义最优值函数和正确地写出递推关系式及边界条件上。 5.基本方程 根据动态规划有顺序、逆序之分，则如何表述动态规划基本方程呢？ 设指标函数为各阶段指标函数之和，即 4=立y4) 则'n(S,P(S》=v(S,4)+'4n(Sk+1,Pk+n(Sk》，其中S4=T(S,4e), Pn(S)={uk,Pk+n(Sk)}∈Pn(S)={(uk,Pk+lnl4k∈Uk(Sk)2Pkn∈PHn(Sk+1）,Sk+=T(Sk,uk)} 于是，对k=n,…,1,有 f(S)='n(S,Pn(s》=op1,'n(S,Pn(sx》 Pan(sa)EPn(sg) opt v(Sk,ux)+Vs(S Pcin(55=T(5,ug) {ukP及i(neR(se) opt fv(Su)+opt Vn(S Pn())5=T(5ug) UsEU(Sk) P(SK+)EP(5+) =opt v(Sxug)+f()S=T(S,ug) ∈U(s) opt v(s,ug)+fT (S,ug)) MLEU(Sk) 即 (5)=opt v(su)+(T(sgu))3,k=n,...1 ∈U(s4) fn+1(Sn+1)=0 一一动态规划逆序解法的基本方程 最后求出(S)。设上述递推关系中相应的最优解为山4(S),则最优策略为 {4(s),4(s2)2…,4n-(Sn-1),4(sn)}S2=T(S,4(s),,Sn=Tm-1(sn-1,n-1(sn-i) 一顺序确定最优策略 对于一般的指标函数
6 , 1 1, 1 1 1 ( , , , , , ) ( , , ( , , , , , )) V su sus suV s u sus kn k k n n n k k k k n k k n n n " " + + ++ + =ψ 即 , , 1, 1 1, 1 ( , ( )) ( , , ( , ( ))) V s p s suV s p s kn k kn k k k k k n k k n k =ψ + ++ + ，其中 , 1, 1 ( ) { , ( )} kn k k k n k p s up s = + + ， 1 (, ) k kk k s Tsu + = 。 （c） 1, (, , ) k k k kn ψ suV + 对于变量Vk n +1, 严格单调。 例如，设指标函数是取各阶段指标函数之和的形式，即 , 1 (, , ,, , ) (, ) n kn k k n n n j j j j k V su sus vsu + = " = ∑ ， 则 , 1 1, 1 1 1 (, , ,, , ) (, ) ( , , ,, , ) V su sus vsu V s u sus kn k k n n n k k k k n k k n n n " " + + ++ + = + 即 , , 1, 1 1, 1 ( , ( )) ( , ) ( , ( )) V s p s vsu V s p s kn k kn k k k k k n k k n k = + + ++ + Vk,n 显然满足指标函数的三个性质。 上述五点是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素。而一个问题的动 态规划模型是否正确给出，集中反映在恰当地定义最优值函数和正确地写出递推关系式及边界条件上。 5．基本方程 根据动态规划有顺序、逆序之分，则如何表述动态规划基本方程呢？ 设指标函数为各阶段指标函数之和，即 , 1 (, , , ) (, ) n kn k k n j j j j k V su s vsu + = " = ∑ 则 , , 1, 1 1, 1 ( , ( )) ( , ) ( , ( )) V s p s vsu V s p s kn k kn k k k k k n k k n k = + + ++ + ，其中 1 (, ) k kk k s Tsu + = ， , 1, 1 , ( ) { , ( )} ( ) kn k k k n k kn k p s up s P s = ∈ + + = 1, 1, 1, 1 1 {( , ) | ( ), ( ), ( , )} k kn k k k kn kn k k k k k u p u U s p P s s Tsu + + + ++ ∈ ∈ = 于是，对 k n = , ,1 " ，有 , , 1, 1 , 1, 1 1, 1 * ,, ,, () () 1, 1 1, 1 1 { , ( )} ( ) ( ) ( )} ( ( ) ( , ( )) ( , ( )) { ( , ) ( , ( ))} ( , ) {(, ) kn k kn k k k n k kn k k kk knk knk k k kn k kn k kn k kn k p sPs k k k knk knk k k k k up s P s kkk uUs p s P s f s V s p s opt V s p s opt v s u V s p s s T s u opt v s u opt + + ++ ++ ∈ + ++ + + ∈ ∈ ∈ = = =+ = = + 1, 1 1, 1 1 ) 11 1 ( ) 1 ( ) ( , ( ))} ( , ) { ( , ) ( )} ( , ) { ( , ) ( ( , ))} k kk k kk knk knk k k k k kk k k k k kk k uUs kk k k kk k uUs V s p s s Tsu opt v s u f s s T s u opt v s u f T s u + ++ + + ++ + ∈ + ∈ = = += = + 即 1 ( ) 1 1 ( ) { ( , ) ( ( , ))}, , ,1 ( )0 k kk kk kk k k kk k uUs n n f s opt v s u f T s u k n f s + ∈ + + ⎧ =+ = ⎪ ⎨ ⎪⎩ = " ——动态规划逆序解法的基本方程 最后求出 1 1 f ( ) s 。设上述递推关系中相应的最优解为 * ( ) k k u s ，则最优策略为 ** * * * * 1 1 2 2 1 1 2 11 1 1 1 1 1 1 { ( ), ( ), , ( ), ( )} ( , ( )), , ( , ( )) n n nn n n n n n u s u s u s u s s Tsu s s T s u s " " −− −− −− = = ——顺序确定最优策略 对于一般的指标函数
'n(sk,Pn(s)》=Ψ(，4，V+n(s+,Pk+ln(sk+i》 其中P(S)={4,P+(}，41=T(S,山)，则同样地， f(Sk)=Vin(Sk P.n(S))=opt V.n(Sk Pi(S)) PA(S4)EP。(S) opt u(Sk,ug Vecin (Sk1 Pn(Sk1))}S=T(sk,ux) tugPi(5(5) opt w(Sk,ug,opt Vn (Sk,Ptn(Sk))}Sk=T(Ss,uk) 4∈U() P1n(a(i） =OpttΨ(Sk,uk,f+1(Sk+)}Sk+1=T(Sk,山) 4∈U(s） =opt wi(Sx,ugf(T(Sk,ug))} 4∈04(S4) 即f(S)=opt{x(Sk,4k,f(Tk(S,4)}。 对于动态规划顺序解法，用S%表示第k阶段末的状态。决策变量，(S)表示第k阶段末状态为S%时 第k阶段所做的决策，允许决策范围为UK(S)。状态转移方程为Sk-1=T(Sk,4)。策略 Pu(s)=((b4,(s)小…，4--b4(s》，其中5k-1=T(S,4)，…，S=T(s2,2），则 Px(S)={B-(S-),4},其中Sk-1=T(Sk,山)。阶段指标函数为以(Sk,山)，k前过程指标函数为 (S0,4,S…Sk-1,4k,S)，其中Sk-1=T(Sk,4s),，S0=T(S1,4)。(S0,4,…S-1,4,S)可记为 u(Pu(5.)5)。最优值函数为f(S)=p1,(P(Sbs)。 px(5 )ER(st) 若，4,4，)=)，则P,人)=P5)+,4)，其中 Sk-1=T(Sk,4)。于是，对k=1,…,n,有 f(S)=Vi(Pix (S ),5x)=opt V.(pL(Sk).S) pua(5)eRx(5) opt Vik-i(P(Sk-1),S-1)+v(Sk,ug)}S-1=T (Sx,ux) {PAk-(sk-b4e(g） opt{opt Vki(p-i(5k).5)+v(sxuk)5-=T (5,u) e(）Pnk-(s-)eB-(-t） =0pt{f-(sk-1)+(S,4)}s-1=Tg(sk,4g) 联eU(s) optf(T (skug))+v (Sk:ug 4∈U(s) 即 f(s)=optfT (sgug))+(sg,ug).k=1,....n 4∈U(s&) fo(so)=0 一一动态规划顺序解法的基本方程 最后求出f(Sn)。设上述递推关系中相应的最优解为(S.),则最优策略为 {4(S),4(S2)2…,4n-1(sm-i),4n(Sn)},sm-1=Tm(Sn,n(sn)…,S1=T(S2,4(S2) —逆序确定最优策略 个
7 , , 1, 1 1, 1 ( , ( )) ( , , ( , ( ))) V s p s suV s p s kn k kn k k k k k n k k n k =ψ + ++ + 其中 , 1, 1 ( ) { , ( )} kn k k k n k p s up s = + + ， 1 (, ) k kk k s Tsu + = ，则同样地， , , 1, 1 , 1, 1 1, 1 * ,, ,, () () 1, 1 1, 1 1 { , ( )} ( ) ( ) ( )} ( ) ( ) ( , ( )) ( , ( )) { ( , , ( , ( ))} ( , ) { (, , kn k kn k k k n k kn k k kk knk knk k k kn k kn k kn k kn k p sPs k k k knk knk k k k k up s P s kkk uUs p s P s f s V s p s opt V s p s opt s u V s p s s T s u opt s u opt V ψ ψ + + ++ ++ ∈ + ++ + + ∈ ∈ ∈ = = = = = 1, 1 1, 1 1 11 1 ( ) 1 ( ) ( , ( ))} ( , ) { ( , , ( )} ( , ) { ( , , ( ( , ))} k kk k kk knk knk k k k k kkk k k k kkk uUs kk k k kk k uUs s p s s Tsu opt s u f s s T s u opt s u f T s u ψ ψ + ++ + + ++ + ∈ + ∈ = = = = 即 1 ( ) ( ) { ( , , ( ( , ))} k kk kk kk k k kk k uUs f s opt s u f T s u ψ + ∈ = 。 对于动态规划顺序解法，用 sk表示第 k 阶段末的状态。决策变量 uk(sk)表示第 k 阶段末状态为 sk时 第 k 阶段所做的决策，允许决策范围为 ( ) r U s k k 。状态转移方程为 1 (, ) r k k kk s T su − = 。策略 1, 1 1 2 2 1 1 ( ) ( ( ), ( ) , ( ), ( )) kk k k kk p s us us u s u s = " − − ，其中 1 (, ) r k k kk s T su − = ， … ， 1 2 22 (, ) r s = T su ， 则 1, 1, 1 1 ( ) { ( ), } kk k k k ps p s u = − − ，其中 1 (, ) r k k kk s T su − = 。阶段指标函数为 (, ) r kkk vsu ，k 前过程指标函数为 1, 0 1 1 1 (,, , , ) V sus s u s k k kk " − ，其中 1 (, ) r k k kk s T su − = ，…， 0 1 11 (, ) r s = T su 。 1, 0 1 1 1 (,, , , ) V sus s u s k k kk " − 可记为 1, 1, ( ( ), ) Vpss k kk k 。最优值函数为 1, 1, 1, 1, () () ( ) ( ( ), ) kk kk kk k kk k p s Ps f s opt V p s s ∈ = 。 若 1, 0 1 1 1 (,, , , ) (, ) k r k kk j j j j V sus u s vsu = " = ∑ ，则 1, 1, 1, 1 1, 1 1 1 ( ( ), ) ( ( ), ) ( , ) r V p s s V p s s vsu k kk k k k k k kk k = + − −− − ， 其中 1 (, ) r k k kk s T su − = 。于是，对 k n =1, , " ，有 1, 1, 1, 1 1 1, 1, 1 1 1, 1 1 * 1, 1, 1, 1, () () 1, 1 1, 1 1 1 1 { ( ), } ( ) 1, 1 ( ) ( )} ( ) ( ) ( ( ), ) ( ( ), ) { ( ( ), ) ( , )} ( , ) { kk kk k k k kk r k kk kk kk kk k kk k k kk k p s Ps r r k k k k kkk k k kk p s u Ps k uUs p s Ps f s V p s s opt V p s s opt V p s s v s u s T s u opt opt V − − −− −− ∈ − −− − − ∈ − ∈ ∈ = = = += = 1, 1 1 1 1 11 1 ( ) 1 ( ) ( ( ), ) ( , )} ( , ) { ( ) ( , )} ( , ) { ( ( , )) ( , )} r k kk r k kk r r k k k kkk k k kk r r k k kkk k k kk uUs r r k k kk kkk uUs p s s vsu s T su opt f s v s u s T s u opt f T s u v s u −− − − −− − ∈ − ∈ + = = += = + 即 1 ( ) 0 0 ( ) { ( ( , )) ( , )}, 1, , () 0 r k kk r r kk k k k k kk k uUs f s opt f T su vsu k n f s − ∈ ⎧ = += ⎪ ⎨ ⎪⎩ = " ——动态规划顺序解法的基本方程 最后求出 ( ) n n f s 。设上述递推关系中相应的最优解为 * ( ) k k u s ，则最优策略为 ** * * * * 11 22 1 1 1 1 2 2 22 { ( ), ( ), , ( ), ( )}, ( , ( )), , ( , ( )) r r n n nn n n n nn us us u s us s T sus s T sus " " −− − = = ——逆序确定最优策略
