第五章动态规划 动态规划是运筹学的一个重要分支，它是从1951年开始，由美国人 贝尔曼(R.Belman)为首的一个学派发展起来的。动态规划在经济、管 理、军事、工程技术等方面都有广泛的应用。 动态规划是解决多阶段决策过程的最优化问题的一种方法。所谓多阶 段决策过程是指这样一类决策过程：它可以把一个复杂问题按时间（或 空间)分成若干个阶段，每个阶段都需要作出决策，以便得到过程的最 优结局。由于在每个阶段采取的决策是与时间有关的而且前一阶段采取 的决策如何，不但与该阶段的经济效果有关，还影响以后各阶段的经济 效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法 称为动态规划方法。然而，动态规划也可以处理一些本来与时间没有关 系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时 段，就可以把它看作是多阶段的动态模型，用动态规划方法去处理。 动态规划对于解决多阶段决策问题的效果是明显的，但也有一定的局 限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合 一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急 剧增大。由于计算机的存贮量及计算速度的限制，目前的计算机仍不能 用动态规划方法来解决较大规模的问题，这就是所谓“维数障碍
第五章 动态规划 动态规划是运筹学的一个重要分支，它是从1951年开始，由美国人 贝尔曼（R.Belman）为首的一个学派发展起来的。动态规划在经济、管 理、军事、工程技术等方面都有广泛的应用。 动态规划是解决多阶段决策过程的最优化问题的一种方法。所谓多阶 段决策过程是指这样一类决策过程：它可以把一个复杂问题按时间（或 空间）分成若干个阶段，每个阶段都需要作出决策，以便得到过程的最 优结局。由于在每个阶段采取的决策是与时间有关的而且前一阶段采取 的决策如何，不但与该阶段的经济效果有关，还影响以后各阶段的经济 效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法 称为动态规划方法。然而，动态规划也可以处理一些本来与时间没有关 系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时 段，就可以把它看作是多阶段的动态模型，用动态规划方法去处理。 动态规划对于解决多阶段决策问题的效果是明显的，但也有一定的局 限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合 一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急 剧增大。由于计算机的存贮量及计算速度的限制，目前的计算机仍不能 用动态规划方法来解决较大规模的问题，这就是所谓“维数障碍
§1动态规划的基本概念 1.1多阶段决策问题 在研究社会经济、经营管理和工程技术领域内的有关问题 中，有一类特殊形式的动态决策问题一多阶段决策问题。在 多阶段决策过程中，系统的动态过程可以按照时间进程分为 相互联系而又相互区别的各个阶段，在每个阶段都要进行决 策。系统在每个阶段存在许多不同的状态，在某个时点的状 态往往要依某种形式受到过去某些决策的影响，而系统的当 前状态和决策又会影响系统过程今后的发展。因而在寻求多 阶段决策问题的最优解时，重要的是不能仅仅从眼前的局部 利益出发进行决策，而需要从系统所经过的整个期间的总效 应出发，有预见性地进行动态决策，找到不同时点的最优决 策及整个过程的最优策略。 下面举例说明什么是多阶段决策问题
§1 动态规划的基本概念 ◼ 1.1 多阶段决策问题 ` 在研究社会经济、经营管理和工程技术领域内的有关问题 中，有一类特殊形式的动态决策问题—多阶段决策问题。在 多阶段决策过程中，系统的动态过程可以按照时间进程分为 相互联系而又相互区别的各个阶段，在每个阶段都要进行决 策。系统在每个阶段存在许多不同的状态，在某个时点的状 态往往要依某种形式受到过去某些决策的影响，而系统的当 前状态和决策又会影响系统过程今后的发展。因而在寻求多 阶段决策问题的最优解时，重要的是不能仅仅从眼前的局部 利益出发进行决策，而需要从系统所经过的整个期间的总效 应出发，有预见性地进行动态决策，找到不同时点的最优决 策及整个过程的最优策略。 下面举例说明什么是多阶段决策问题
例1（最短路线问题）在线路网络图5一1中，从A至E有 批货物需要调运。图上所标数字为各节点之间的运输距离， 为使总运费最少，必须找出一条由A至E总里程最短的路线。 6 B3 图5一1 为了找到由A至E的最短线路，可以将该问题分成A一B一C D一E4个阶段，在每个阶段都需要作出决策，即在A点需决 策下一步到B还是到B2或B3；同样，若到达第二阶段某个状 态，比如B,,需决定走向C,还是C2;依次类推，可以看出： 各个阶段的决策不同，由A至E的路线就不同，当从某个阶段 的某个状态出发作出一个决策，则这个决策不仅影响到下一 个阶段的距离，而且直接影响后面各阶段的行进线路。所以 这类问题要求在各个阶段选择一个恰当的决策，使这些决策 序列所决定的一条路线对应的总路程最短
例1（最短路线问题）在线路网络图5—1中，从A至E有 一批货物需要调运。图上所标数字为各节点之间的运输距离， 为使总运费最少，必须找出一条由A至E总里程最短的路线。 A B1 B2 E B3 C2 C3 C1 D2 D3 D1 4 5 3 4 4 4 3 1 6 5 8 8 7 7 10 2 9 6 为了找到由A至E的最短线路，可以将该问题分成A—B—C— D—E 4个阶段，在每个阶段都需要作出决策，即在A点需决 策下一步到B1还是到B2或B3；同样，若到达第二阶段某个状 态，比如B1 ，需决定走向C1还是C2 ；依次类推，可以看出： 各个阶段的决策不同，由A至E的路线就不同，当从某个阶段 的某个状态出发作出一个决策，则这个决策不仅影响到下一 个阶段的距离，而且直接影响后面各阶段的行进线路。所以 这类问题要求在各个阶段选择一个恰当的决策，使这些决策 序列所决定的一条路线对应的总路程最短。 图5—1
例2（带回收的资源分配问题）某厂新购某种机床125台。 据估计，这种设备5年后将被其它设备所代替。此机车如在 高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在 低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应 如何安排这些机床的生产负荷，才能使5年内获得的利润最 大？ 本问题具有时间上的次序性，在五年计划的每一年都要 作出关于这些机床生产负荷的决策，并且一旦作出决策，不 仅影响到本年利润的多少，而且影响到下一年初完好机床数， 从而影响以后各年的利润。所以在每年初作决策时，必须将 当年的利润和以后各年利润结合起来，统筹考虑。 与上面例1、例2类似的多阶段决策问题还有资源分配、 生产存贮、可靠性、背包、设备更新问题等等
例2（带回收的资源分配问题）某厂新购某种机床125台。 据估计，这种设备5年后将被其它设备所代替。此机车如在 高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在 低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应 如何安排这些机床的生产负荷，才能使5年内获得的利润最 大？ 本问题具有时间上的次序性，在五年计划的每一年都要 作出关于这些机床生产负荷的决策，并且一旦作出决策，不 仅影响到本年利润的多少，而且影响到下一年初完好机床数， 从而影响以后各年的利润。所以在每年初作决策时，必须将 当年的利润和以后各年利润结合起来，统筹考虑。 与上面例1、例2类似的多阶段决策问题还有资源分配、 生产存贮、可靠性、背包、设备更新问题等等
1.2动态规划的基本概念 1.阶段 动态规划问题通常都具有时间或空间上的次序性，因此 求解这类问题时，首先要将问题按一定的次序划分成若干相 互联系的阶段，以便能按一定次序去求解。如例1，可以按 空间次序划分为A一B一C一D一E4个阶段，而例2，按照时 间次序可分成5个阶段。 2.状态 在多阶段决策过程中，每阶段都需要作出决策，而决策 是根据系统所处情况决定的。状态是描述系统情况所必需的 信息。如例1中每阶段的出发点位置就是状态，例2中每年初 拥有的完好机床数是作出机床负荷安排的根据，所以年初完 好机床数是状态。一般地，状态可以用一个变量来描述，称 为状态变量。记第k阶段的状态变量为X,k=1,2,.n
1.2 动态规划的基本概念 1.阶段 动态规划问题通常都具有时间或空间上的次序性，因此 求解这类问题时，首先要将问题按一定的次序划分成若干相 互联系的阶段，以便能按一定次序去求解。如例1，可以按 空间次序划分为A—B—C—D—E 4个阶段，而例2，按照时 间次序可分成5个阶段。 2.状态 在多阶段决策过程中，每阶段都需要作出决策，而决策 是根据系统所处情况决定的。状态是描述系统情况所必需的 信息。如例1中每阶段的出发点位置就是状态，例2中每年初 拥有的完好机床数是作出机床负荷安排的根据，所以年初完 好机床数是状态。一般地，状态可以用一个变量来描述，称 为状态变量。记第k 阶段的状态变量为xk ,k=1,2, …,n
3.决策 多阶段决策过程的发展是用各阶段的状态演变来描述的， 阶段决策就是决策者从本阶段某状态出发对下一阶段状态所 作出的选择。描述决策的变量称为决策变量，当第k阶段的 状态确定之后，可能作出的决策要受到这一状态的影响。这 就是说决策变量u还是状态变量X的函数，因此，又可将第 k阶段X状态下的决策变量记为u,(X)。 在实际问题中，决策变量的取值往往限制在某一范围之 内，此范围称为允许决策变量集合，记作Du)。 如例2中取 高负荷运行的机床数uk为决策变量，则0s≤X(X是k阶段 初完好机床数)为允许决策变量集合。 4.状态转移方程 在多阶段决策过程中，如果给定了k阶段的状态变量X 和决策变量uk,则第k+1阶段的状态变量xk+1也会随之而确 定。也就是说Xk+1是X和uk函数，这种关系可记为 Xk+1=T(☒kuk) 称之为状态转移方程
3.决策 多阶段决策过程的发展是用各阶段的状态演变来描述的， 阶段决策就是决策者从本阶段某状态出发对下一阶段状态所 作出的选择。描述决策的变量称为决策变量，当第k 阶段的 状态确定之后，可能作出的决策要受到这一状态的影响。这 就是说决策变量uk还是状态变量xk 的函数，因此，又可将第 k阶段xk状态下的决策变量记为uk (xk )。 在实际问题中，决策变量的取值往往限制在某一范围之 内，此范围称为允许决策变量集合，记作Dk (uk )。如例2中取 高负荷运行的机床数uk为决策变量，则0≤uk≤xk（xk是k阶段 初完好机床数）为允许决策变量集合。 4.状态转移方程 在多阶段决策过程中，如果给定了k 阶段的状态变量xk 和决策变量uk，则第k+1阶段的状态变量xk+1也会随之而确 定。也就是说xk+1是xk和uk函数，这种关系可记为 xk+1=T(xk , uk ) 称之为状态转移方程
5策略 在一个多阶段决策过程中，如果各个阶段的决策变量 u(X)(k=1,2,,n)都已确定，则整个过程也就完全确 定。称决策序列{u1(X1),u2(X2),,u(X)}为该过程的一个策 略，从阶段k到阶段的决策序列称为子策略，表示成uk() uk+1(k+1),,un(X)}。如例1中，选取一路线A—B1一C2 D,一E就是一个策略： {u1(A)=B1,u2(B)=C2,u3(C2)=D2,u4(D2)=E} 由于每一阶段都有若干个可能的状态和多种不同的决策， 因而一个多阶段决策的实际问题存在许多策略可供选择，称 其中能够满足预期目标的策略为最优策略。例1中存在12条 不同路线，其中A一B2一C1—D2一E是最短线路。 6.指标函数 用来衡量过程优劣的数量指标，称为指标函数。在阶段 k的X状态下执行决策uk,不仅带来系统状态的转移，而且 也必然对目标函数给予影响，阶段效应就是执行阶段决策时 给目标函数的影响
5.策略 在一个多阶段决策过程中，如果各个阶段的决策变量 uk (xk ) （k=1，2，…，n）都已确定，则整个过程也就完全确 定。称决策序列{u1 (x1 ), u2 (x2 ), …, un (xn )}为该过程的一个策 略，从阶段k到阶段n的决策序列称为子策略，表示成{uk (xk ), uk+1(xk+1), …, un (xn ) }。如例1中，选取一路线A—B1—C2— D2—E 就是一个策略： {u1 (A)= B1 , u2 (B1 )= C2 , u3 (C2 )= D2 , u4 (D2 )=E} 由于每一阶段都有若干个可能的状态和多种不同的决策， 因而一个多阶段决策的实际问题存在许多策略可供选择，称 其中能够满足预期目标的策略为最优策略。例1中存在12条 不同路线，其中A—B2—C1—D2—E是最短线路。 6.指标函数 用来衡量过程优劣的数量指标，称为指标函数。在阶段 k的xk状态下执行决策uk，不仅带来系统状态的转移，而且 也必然对目标函数给予影响，阶段效应就是执行阶段决策时 给目标函数的影响
多阶段决策过程关于目标函数的总效应是各阶段的阶段 效应累积形成的。常见的全过程目标函数有以下两种形式： (1)全过程的目标函数等于各阶段目标函数的和，即： R=r1(X1,u1)+r2(X2,u2)+..+rn(X,un) (2)全过程的目标函数等于各阶段目标函数的积，即： R=r(X1,u1)xr2(x2,U2)X...xr(xn un) 指标函数的最优值，称为最优函数值。一般，f(X1)表 示从第1阶段x1状态出发至第阶段（最后段）的最优指标 函数，(X)表示从第k阶段X状态出发至第n阶段的最优 指标函数(k=1,2,..,n)
多阶段决策过程关于目标函数的总效应是各阶段的阶段 效应累积形成的。常见的全过程目标函数有以下两种形式： ◼ （1）全过程的目标函数等于各阶段目标函数的和，即： R=r1 (x1 , u1 ) +r2 (x2 , u2 ) +…+rn (xn , un ) ◼ （2）全过程的目标函数等于各阶段目标函数的积，即： R=r1 (x1 , u1 ) ×r2 (x2 , u2 ) ×…×rn (xn , un ) 指标函数的最优值，称为最优函数值。一般，f1（x1）表 示从第1阶段x1状态出发至第n阶段（最后阶段）的最优指标 函数， fk（xk）表示从第k阶段xk状态出发至第n阶段的最优 指标函数(k=1，2，…，n）
