第二讲动态规划

1、12 多阶段决策过程的最优化多阶段决策过程的最优化 动态规划的基本概念和基本原理动态规划的基本概念和基本原理 动态规划模型的建立与求解动态规划模型的建立与求解3美国数学家贝尔曼美国数学家贝尔曼(Richard. Bellman)创始时间创始时间上个世纪上个世纪50年代年代创始人创始人4 是运筹学的一个主要分支是运筹学的一个主要分支 是解决是解决多阶段决策过程多阶段决策过程的最优化的一种方法多的最优化的一种方法多阶段决策过程：阶段决策过程：资源分配问题资源分配问题生产计划与库存问题生产计划与库存问题投资问题投资问题装载问题装载问题排序问题排序问题生产过程的最优控制等生产过程的最优控制等多阶段决策

2、过程的多阶段决策过程的最优化的目标最优化的目标：达到整个活动过程的总体效果最优达到整个活动过程的总体效果最优主要用于解决：主要用于解决：最优路径问题最优路径问题5动态规划动态规划模型分类模型分类离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型6多阶段决策问题(Multi-Stage decision process)状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+17 动态规划方法与动态规划方法与“时间时间”关系很密关系很密切，随着时间过程的发展而决定各时段的

3、切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是决策，产生一个决策序列，这就是“动态动态”的意思。然而它也可以处理与时间无关的的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入静态问题，只要在问题中人为地引入“时时段段”因素，就可以将其转化为一个多阶段因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。决策问题。在本章中将介绍这种处理方法。82.多阶段决策问题举例多阶段决策问题举例 属于多阶段决策类的问题很多，例如属于多阶段决策类的问题很多，例如 1)1)工厂生产过程工厂生产过程：由于市场需求是一随着：由于市场需求是一随着时间而变化的因素，

4、因此，为了取得全年时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决逐月或者逐季度地根据库存和需求情况决定生产计划安排。定生产计划安排。9 例例1：某厂与用户签订了如表所示的交货合同，：某厂与用户签订了如表所示的交货合同，表中数字为月底的交货量。该厂的生产能力为每表中数字为月底的交货量。该厂的生产能力为每月月400件，该厂仓库的存货能力为件，该厂仓库的存货能力为300件。已知件。已知每百件货物的生产费用为每百件货物的生产费用为10000元。在进行生产元。在进行生产的月份，工厂还要支付经常费的月份，

5、工厂还要支付经常费4000元。仓库保元。仓库保管费为每百件货物每月管费为每百件货物每月1000元。假设开始时及元。假设开始时及6月底交货后无存货。月底交货后无存货。月份123456交货量（百件）125321102)2)设备更新问题设备更新问题：一般企业用于生产活动的设备，一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用减少，

6、加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最合权衡决定设备的使用年限，使总的经济效益最好。好。例例2 2：下表给出了某单位的预测数据，现决定考虑到：下表给出了某单位的预测数据，现决定考虑到19981998年（年（n=5n=5），试作），试作5 5年内的设备更新计划年内的设备更新计划产品年代机龄收入额维护费新设备购置费旧设备折价1993123451816161414889910502015105219

7、94012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040123)3)连续生产过程的控制问题连续生产过程的控制问题：一般化工生产过程中，常包含一一般化工生产过程中，常包含一系列完成生产过程的设备，前一系列完成生产过程的设备，前一工序设备的输出则是后一工序设工序设备的输出则是后一工序设备的输入，因此，应该如何根据备的输入，因此，应该如何根据各工序的运行工况，控制生产过各工序的运行工况，控制生产过程中各设备的输入和输出，

8、以使程中各设备的输入和输出，以使总产量最大。总产量最大。13 以上所举问题的发展过程都与时间因素有关，以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了与时间因素有关，这就使它具有了“动态动态”的含的含义，所以把处理这类动态问题的方法称为动态规义，所以把处理这类动态问题的方法称为动态规划方法。划方法。 不过，实际中尚有许多不包含时间因素的一不过，实际中尚有许多不包含时间因素的一类类“静态静态”决策问题，就其本

9、质而言是一次决策决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。划方法加以解决。14 4 4）资源分配问题资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题( (后面我们将详细讨论这个问题后面我们

10、将详细讨论这个问题) )。15 例3：某工厂生产A、B、C三种产品，都使用某种原材料，现有原材料4吨。将不同数量的这种原料分配给各种产品时产生的收益如表所示，试确定使总收益最大的分配法。ABC0123010172006171808111116 5 5）运输网络问题运输网络问题：如图如图7-17-1所示的运输网络，所示的运输网络，点间连线上的数字表示两地距离点间连线上的数字表示两地距离( (也可是运也可是运费、时间等费、时间等) )，要求从，要求从A A至至F F的最短路线。的最短路线。 这种运输网络问题也是静态决策问题。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分但是

11、，按照网络中点的分布，可以把它分为为5 5个阶段，而作为多阶段决策问题来研究。个阶段，而作为多阶段决策问题来研究。1718 多阶段决策过程的最优化多阶段决策过程的最优化 动态规划的基本概念和基本原理动态规划的基本概念和基本原理 动态规划模型的建立与求解动态规划模型的建立与求解191、阶段：、阶段：p把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按，以便于按一定的次序去求解。一定的次序去求解。p描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分，一般是根据时间和空。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于

12、问题转化为多阶段决策。间的自然特征来进行的，但要便于问题转化为多阶段决策。2、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。通常一个阶段有若。通常一个阶段有若干个状态，描述过程状态的变量称为干个状态，描述过程状态的变量称为状态变量状态变量。年、年、月、月、路段路段一个数、一个数、一组数、一组数、一个向量一个向量 状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合状态允许集合。203、决策：、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，表示当过程处于某一阶段的某个状态时，

13、可以作出不同的决定，从而确定下一阶段的状态从而确定下一阶段的状态，这种决定称为这种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态变量的函数。可。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允允许决策集合许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。而且

14、还与系统过去的历史状态和决策有关。4、多阶段决策过程、多阶段决策过程可以在各个阶段进行决策，去控制过程发展的多段过程；可以在各个阶段进行决策，去控制过程发展的多段过程；其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；21),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下：状态转移方程是确定过程由一状态转移方程是确定过程由一个状态到另一个状态的演变过个状态到另一个状态的演变过程。如果第程。如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策变量一经的值、该阶段的决策变量一经确定，第确定，第k+1阶段状态变

15、量阶段状态变量sk+1的值也就确定。的值也就确定。其状态转移方程如下（一般形式）其状态转移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。22),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性

16、无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；动态规划模型时，要充分注意是否满足无后效性的要求；状态变量要满足无后效性的要求；状态变量要满足无后效性的要求；如果状态变量不能满足无后效如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。性的要求，应适当地改变状态的定义或规定方

17、法。23 5、策略：、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为策略有一定的范围，称为允许策略集合允许策略集合。从允许策略集合中找出达。从允许策略集合中找出达到最优效果的策略称为到最优效果的策略称为最优策略最优策略。 6、状态转移方程：、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。移规律。 7、指标函数和最优值函数：、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为用来衡量所实现过程优劣的一

18、种数量指标，为指标函数指标函数。指标函。指标函数的最优值，称为数的最优值，称为最优值函数最优值函数。在不同的问题中，指标函数的含。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数应具有动态规划模型的指标函数应具有可分离性可分离性，并满足，并满足递推递推关系。关系。24),(,111,1nkknkkkksusVus指标函数指标函数: 指标函数形式指标函数形式: 和、和、积积),(111,nkkkknksususV可递推可递推),()(1,susVoptsfnkknkkkuunk 效益

19、效益最优函数最优函数: 25,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列 susvoptsfnkknkkkuunk1, f1(s1) 最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值),(*1*1*,1*,1nnnnususVV从从 k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值261、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程

20、）。边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解

21、。后一个子问题所得的最优解，就是整个问题的最优解。272、在多阶段决策过程中，动态规划方法是既把当前一段和未来一、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的一般是不同的. 最优化原理：作为整个过程的最优策略具有这样的性质：无论过去最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，

22、余下的的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。决策序列必然构成最优子策略。”也就是说，一个最优策略的子策也就是说，一个最优策略的子策略也是最优的。略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。逐段变换得到，从而确定了最优路线。28建立动态规划模型的步骤建立动态规划模型的步骤 1、划分阶段、划分阶段划分阶段是运用动态规划求解

23、多阶段决策问题的第一步，在确划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予相互联系的阶段。对于静态问题要人为地赋予“时间时间”概念，概念，以便划分阶段。以便划分阶段。2、正确选择状态变量、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。过

24、程演变的特点中寻找。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。策变量的取值范围，即确定允许决策集合。294、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，状阶段状态变量，状态转移方程应当具有递推关系。态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第阶段

25、指标函数是指第k 阶段的收益，最优指标函数是指从第阶段的收益，最优指标函数是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动阶段末所获得收益的最优值，最后写出动态规划基本方程。态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧

26、。 2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f522425112141061

27、04131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1A

28、B1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81133312321131112CB20222120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优

29、决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=211233322322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1

30、)=21f2(B2)=142333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2123232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策2511

31、214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21

32、状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D12511214106104131112396581052C1C3D1AB1B3B2D2EC2

33、f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径为19，路线为AB 2C1 D1 E 45 用动态规划方法求最短路46 先从先从F F开始，因为开始，因为F F是终点。再无后继过程，故可以是终点。再无后继过程，故可以接着考虑第接着考虑第5 5阶段上所有可能状态阶段上所有可能状态E E1 1，E E2 2的最优

34、后续的最优后续过程。因为从过程。因为从E E1 1 ,E,E2 2到到F F的路线是唯一的，所以的路线是唯一的，所以E E1 1，E E2 2的最优决策和最优后继过程就是到的最优决策和最优后继过程就是到F F，它们的最，它们的最短距离分别是短距离分别是4 4和和3 3。 接着考虑阶段接着考虑阶段4 4上可能的状态上可能的状态D D1 1，D D2 2，D D3 3 到到F F的的最优决策和最优后继过程在状态最优决策和最优后继过程在状态D D1 1上，到上，到E E1 1是是3 3，到到E E2 2是是5 5，综合考虑后继过程整体最优，取最优决，综合考虑后继过程整体最优，取最优决策是到策是到E E1 1, ,最优后继过程是最优后继过程是D D1 1EE1 1FF ，最短距离是，最短距离是7 7。同理，状态。同理，状态D D2 2的最优决策是至的最优决策是至E E2 2 ；D D3 3的最优决的最优决策是到策是到E E1 1。47 同样，当阶段同样，当阶段4 4上所有可能状态的最优上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段后继过程都已求得后，便可以开始考虑阶段3 3上所有可能状态的最优决策和最优后继过上所有可能状态的最优决策和最优后继过程，如程，如C C1 1的最优决策是到的最优决策是到D D1 1, ,最优路线是最优路线是C C1 1D D1 1