高等运筹第六讲刘巍大连海事大学

1、高等运筹学高等运筹学大连海事大学大连海事大学刘巍刘巍第二篇 运筹学中的数学规划 第四章第四章 线性规划线性规划 第五章第五章 非线性规划非线性规划 第六章第六章 锥规划、矩阵规划及变分不等式锥规划、矩阵规划及变分不等式 第七章第七章 整数规划整数规划 第八章第八章 动态规划动态规划 第九章第九章 向量优化（多目标优化）向量优化（多目标优化）第八章 动态规划 当系统模型具备马尔科夫性，同时目标函数当系统模型具备马尔科夫性，同时目标函数可分且嵌套单调时，基于贝尔曼提出的最优可分且嵌套单调时，基于贝尔曼提出的最优性原理，运用动态规划可将求解多阶段全局性原理，运用动态规划可将求解多阶段全局最优决策问题

2、分解为一系列在各个时间段上最优决策问题分解为一系列在各个时间段上的局部优化问题。相比其它解法，特别是在的局部优化问题。相比其它解法，特别是在有扰动或在随机情况下，动态规划总是能有有扰动或在随机情况下，动态规划总是能有效地提供一个在当前信息集下的最优反馈控效地提供一个在当前信息集下的最优反馈控制策略。制策略。马尔科夫性 在某些随机系统中，有一类具有在某些随机系统中，有一类具有“无后效性性质无后效性性质”，即当随机过程在某一时刻，即当随机过程在某一时刻to所处的状态已知所处的状态已知的条件下，过程在时刻的条件下，过程在时刻tto时所处的状态只和时所处的状态只和to时刻有关，而与时刻有关，而与to以

3、前的状态无关。这种在已知以前的状态无关。这种在已知“现在现在”的条件下，的条件下，“未来未来”与与“过去过去”彼此独彼此独立的特性就被称为马尔科夫性，具有这种性质的立的特性就被称为马尔科夫性，具有这种性质的随机过程就叫做马尔科夫过程，其最原始的模型随机过程就叫做马尔科夫过程，其最原始的模型就是马尔科夫链。就是马尔科夫链。贝尔曼“最优性原理” 这个原理归结为用一组基本的递推关系这个原理归结为用一组基本的递推关系式使过程连续的最优转移，它可以求这式使过程连续的最优转移，它可以求这样的最优解，这些最优解是以计算每个样的最优解，这些最优解是以计算每个决策的后果并对今后的决策制定最优决决策的后果并对今后

4、的决策制定最优决策为基础的，但在求最优解时要按倒过策为基础的，但在求最优解时要按倒过来的顺序进行，即从最终状态开始到初来的顺序进行，即从最终状态开始到初始状态为止。始状态为止。最优化原理： 作为整个过程的最优策略具有这样的性作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优是说，一个最优策略的子策略也是最优的。的。 7 动态规划动态规划(dynamic programming

5、) 动态规划的基本概念和思想动态规划的基本概念和思想 最短路径问题最短路径问题 投资分配问题投资分配问题 背包问题背包问题 排序问题排序问题8动态规划是运筹学的一个分支，是求解多阶段决策过动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。学习动态规划，我们首先要了解多阶段决策问题。9最短路径问题最短路径问题：给定一个交通网络图

6、如下，其中两点之：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从间的数字表示距离（或运费），试求从a a点到点到g g点的最短距点的最短距离（总运输费用最小）。离（总运输费用最小）。1 12 23 34 45 56 6ab1b2c1c2c3c4d1d2d3e1e2e3f1f2g53136876368533842221333525664310背包问题背包问题 有一个徒步旅行者，其可携带物品重量的限度有一个徒步旅行者，其可携带物品重量的限度为为a a 公斤，设有公斤，设有n n 种物品可供他选择装入包中。已知每种种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），

7、问此人应如何选择携带物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。11 生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季

8、度地生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。机器负荷分配问题机器负荷分配问题：某种机器可以在高低两种不同的负荷：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在下进行生产。要求制定一个五年计划，在每年开始时，决每年开始时，决定如何重新分配定如何重新分配完好的完好的机器在两种不同的负荷下生产的数机器在两种不同的负荷下生产的数量量，使在五年内产品的总产量达到最高。，使在五年内产品的总产量达到最高。航天飞机飞行控制问题航天飞机飞行控制问题：由于航天飞机的运动的环境是不：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境

9、中的情断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。之能最省燃料和完成飞行任务（如软着陆）。12根据过程的特性可以将过程按空间、时间等标志分为根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。若干个互相联系又互相区别的阶段。在每一个阶段都需要做出决策，从而使整个过程达到在每一个阶段都需要做出决策，从而使整个过程达到最好的效果。最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前各个阶段决策的选取不是任意确定的，它依赖于

10、当前面临的状态，又影响以后的发展。面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。决策问题。多阶段决策过程的特点：多阶段决策过程的特点：13针对多阶段决策过程的最优化问题，美国数学家针对多阶段决策过程的最优化问题，美国数学家bellmanbellman等人在等人在2020世纪世纪5050年代初提出了著名的最优化原理，年代初提出了著

11、名的最优化原理，把多阶把多阶段决策问题转化为一系列单阶段最优化问题段决策问题转化为一系列单阶段最优化问题，从而逐个求解，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划。创立了解决这类过程优化问题的新方法：动态规划。对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是bellman提出的著名的最优化原理。简言之， 一个最优策略的子策略必然也是最优的。bellmanbellman在在19571957年出版的年出版的dynamic programmingdynamic programmi

12、ng是动是动态规划领域的第一本著作。态规划领域的第一本著作。14例1、从从a a 地到地到e e 地要铺设一条煤气管道地要铺设一条煤气管道, ,其中需经过三其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？问应该选择什么路线，使总距离最短？ 二. 最短路径问题a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e52141126101043121113965810521c c2 215 解：解：整个计算过程分四个整个计算过程分四个阶段阶段，从最后一个阶段

13、开始。，从最后一个阶段开始。 第四阶段（第四阶段（d d e e）：）： d d 有两条路线到终点有两条路线到终点e e 。 显然有显然有a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e52141126101043121113965810521c c2 22)(; 5)(2414 dfdf16首先考虑经过首先考虑经过 的两条路线的两条路线第三阶段（第三阶段（c c d d）：）： c c 到到d d 有有 6 6 条路线。条路线。( (最短路线为最短路线为 ) )a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d

14、2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 282953min)(),()(),(min)(2421141113 dfdcddfdcdcfedc111c17a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 272556min)(),()(),(min)(2422141223 dfdcddfdc

15、dcf( (最短路线为最短路线为 ) )edc22考虑经过考虑经过 的两条路线的两条路线2c18a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 21221058min)(),()(),(min)(2423141333 dfdcddfdcdcf( (最短路线为最短路线为 ) )edc23考虑经过考虑经过 的两条路线的两条路线3c19a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1

16、 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 2201210714812min)(),()(),()(),(min)(33312321131112 cfcbdcfcbdcfcbdbf( (最短路线最短路线为为 ) )edcb111第二阶段（第二阶段（b b c c）：）： b b 到到c c 有有 9 9 条路线。条路线。首先考虑经过首先考虑经过 的的3 3条路线条路线1b20a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5

17、 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 21412471086min)(),()(),()(),(min)(34322422141222 cfcbdcfcbdcfcbdbf( (最短路线为最短路线为 ) )edcb112考虑经过考虑经过 的的3 3条路线条路线2b21a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21

18、 1c c2 2191211712813min)(),()(),()(),(min)(33332323131332 cfcbdcfcbdcfcbdbf( (最短路线为最短路线为 ) )edcb223考虑经过考虑经过 的的3 3条路线条路线3b22a ab b2 2b b1 1b b3 3c c1 1c c3 3d d1 1d d2 2e e5 52 2141412126 6101010104 43 31212111113139 96 65 58 810105 52 21 1c c2 219191145202min)(),()(),()(),(min)(3232221211 bfbadbfbad

19、bfbadaf( (最短路线为最短路线为 ) )edcba112第一阶段（第一阶段（a a b b）：）： a a 到到b b 有有 3 3 条路线。条路线。 （最短距离为（最短距离为1919）23 动态规划是用来解决多阶段决策过程最优化的一种动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，数量方法。其特点在于，它可以把一个它可以把一个n n 维决策问题变换为维决策问题变换为几个一维最优化问题几个一维最优化问题，从而一个一个地去解决。，从而一个一个地去解决。 需指出：需指出：动态规划是求解某类问题的一种方法，是动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种

20、算法考察问题的一种途径，而不是一种算法。必须对具体问题进。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。然后再用动态规划方法去求解。即在系统发展的不同时刻（或阶段）根据系统所处的即在系统发展的不同时刻（或阶段）根据系统所处的状态，状态，不断地做出决策不断地做出决策；动态决策问题的特点：动态决策问题的特点：系统所处的系统所处的状态和时刻状态和时刻是进行决策的重要因素；是进行决策的重要因素；找到找到不同时刻不同时刻的最优决策以及的最优决策以及整个过程的最优策略整个过程的最优策略。24 动态规划

21、方法的关键：在于正确地写出动态规划方法的关键：在于正确地写出基本的递基本的递推关系式推关系式和和恰当的边界条件恰当的边界条件（简称（简称基本方程基本方程）。）。 要做到这一点，就必须将问题的过程分成几个相要做到这一点，就必须将问题的过程分成几个相互联系的互联系的阶段阶段，恰当的选取，恰当的选取状态变量状态变量和和决策变量决策变量及定义及定义最最优值函数优值函数，从而把一个大问题转化成一组同类型的子问题，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。然后逐个求解。 即从边界条件开始，逐段递推寻优，在每一个子即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的

22、最优化结果，问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。的最优解。25 2 2、在多阶段决策过程中，动态规划方法是既把当前、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段一段和未来一段分开分开，又把当前效益和未来效益，又把当前效益和未来效益结合结合起来起来考虑的一种最优化方法。因此，每段决策的选取是从全局考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的来考虑的，与该段的最优选择答案一般是不同的. . 最优化原理：作为整个过程的

23、最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。26动态规划求解的多阶段问题的特点：动态规划求解的多阶段问题的特点： 每个阶段的最优决策过程只与本阶段的初始状态有关每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之

24、，本阶段之状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系系统过程的历史只能通过系统现阶段的状态去影响系统的未来。统的未来。 具有这种性质的状态称为无后效性（即马尔科夫性）具有这种性质的状态称为无后效性（即马尔科夫性）状态。状态。 动态规划方法只适用于求解具有无后效性状态的多阶动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。段决策问题。27 现有数量为a（万元

25、）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 nixaxxgziniiniii.2.1 0)( max11据此，有下式：三. 投资分配问题28 令：令：f fk k( (x x) ) 表示表示 以数量为以数量为 x x 的资金分配给的资金分配给前前k k 个个工工厂，所得到的最大利润值。厂，所得到的最大利润值。 用动态规划求解，就是用动态规划求解，就是求求 f fn n( (a a) ) 的问题的问题。 当当 k k=1 =1

26、时，时， f f1 1( (x x) = ) = g g1 1( (x x) ) （因为只给一（因为只给一个工厂）个工厂） 当当1 1k kn n 时，其递推关系如下：时，其递推关系如下： 设：设：y y 为分给第为分给第k k 个工厂的资金（其中个工厂的资金（其中 00y y x x ），），此时还剩此时还剩 x x y y（万元）的资金需要分配给前（万元）的资金需要分配给前 k k1 1 个工个工厂厂, ,如果采取最优策略，则得到的最大利润为如果采取最优策略，则得到的最大利润为f fk k1 1( (x xy y) ,) ,因此总的利润为：因此总的利润为： g gk k( (y y) )

27、f fk k1 1( (x xy y) ) 29 nkyxfygxfkkxyk.)()(max)(3210 其中 如果如果a a 是以万元为资金分配单位，则式中的是以万元为资金分配单位，则式中的y y 只取只取非负整数非负整数0 0，1 1，2 2，x x。上式可变为：。上式可变为： )()(max)(,yxfygxfkkxyk 1210所以，根据动态规划的最优化原理，有下式：所以，根据动态规划的最优化原理，有下式：30 例2：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资利润0102030405060g1(x)02050

28、65808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求 f4(60) 。31按顺序解法计算。按顺序解法计算。第一阶段：求第一阶段：求 f f1 1( (x x) )。显然有。显然有 f f1 1( (x x) ) g g1 1( (x x) )，得到，得到下表下表 投资投资利润利润0102030405060f1(x) g1(x)0205065808585最优策略最优策略0102030405060第二阶段：求第二阶段：求 f f2 2( (x x) )。此时需考虑第一、第二个工厂如何进。此时需考虑第一

29、、第二个工厂如何进行投资分配，以取得最大的总利润。行投资分配，以取得最大的总利润。 )60()(max)60(1260,10,02yfygfy 3212006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最优策略为（最优策略为（4040，2020），此时最大利润为），此时最大利润为120120万元。万元。同理可求得其它同理可求得其它 f f2 2( (x x) ) 的值。的值。 )60()(max)60(1260,10

30、,02yfygfy 33 105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(max)50(1212121212121250,10,02 fgfgfgfgfgfgyfygfy最优策略为（最优策略为（3030，2020），此时最大利润为），此时最大利润为105105万元。万元。34 90 )40()(max)40(1240,10,02 yfygfy最优策略为（最优策略为（2020，2020），此时最大利润为），此时最大利润为9090万元。万元。 70 )30()(max)30(1230,20,10,02 yfygfy最优策略为（最优策略

31、为（2020，1010），此时最大利润为），此时最大利润为7070万元。万元。35 50 )20()(max)20(1220,10,02 yfygfy 20 )10()(max)10(12,10,02 yfygfy最优策略为（最优策略为（1010，0 0）或（）或（ 0 0 ， 10 10 ） ，此时最大利，此时最大利润为润为2020万元。万元。 f f2 2(0) (0) 0 0。最优策略为（最优策略为（0 0，0 0），最大利润为），最大利润为0 0万万元。元。 得到下表得到下表最优策略为（最优策略为（2020，0 0），此时最大利润为），此时最大利润为5050万元。万元。36 投资投资利

32、润利润0102030405060f2(x)020507090105120最优策略最优策略(0,0)(10,0)(0,10)(20,0) (20,10) (20,20) (30,20) (40,20)第三阶段：求第三阶段：求 f f3 3( (x x) )。此时需考虑第一、第二及第三个。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。工厂如何进行投资分配，以取得最大的总利润。 )60()(max)60(2360,10,03yfygfy 371550115201105010070859060105251200max)0()60()10()50()20()40()30()30(

33、)40()20()50()10()60()0(max23232323232323 fgfgfgfgfgfgfg最优策略为（最优策略为（2020，1010，3030），最大利润为），最大利润为155155万元。万元。同理可求得其它同理可求得其它 f f3 3( (x x) ) 的值。得到下表的值。得到下表38 投资投资利润利润0102030405060f3(x)0256085110135155最优最优策略策略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四阶段：求 f4(60)。即问题的最优策略。)60()(m

34、ax)60(3460,10,04yfygfy3916007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最优策略为（20，0，30，10），最大利润为160万元。40 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件）

35、a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。四、背包问题41设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下： ).(maxnjxaxaxczjnijjjnjjj21 01且为整数用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a) 42其递推关系式为： nkxayfxcyfkkkkkayxkkk 2 10其中)(max)(当 k=1 时，

36、有：的最大整数表示不超过其中1111111 ayayayxaycyf ,)(43例3：求下面背包问题的最优解 且且为为整整数数0,55231258max321321321xxxxxxxxxz物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12解：a5 ，问题是求 f3(5) )55(12max)5(323503333xfxfxax 整整数数44 )( max)( 32350355125333xfxfxax 整数 )( max 323550551233xfxxx 整数 )( max 3231055123xfxx ， )( )()( ),(max 1

37、0223301250 xxff物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 1245 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整数整数整数整数物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12 )()()()(max)(1022333012505x xf, ff46 )0( )0(0max )20(5 max )2

38、0(5 max )20(5 max)0(1 )0( 12120212 200212 0022222222ffxfxxfxxfxfxxxxxax 整数整数整数整数物品物品( (xi ) x1 x2 x3重量（重量（ai） 3 2 5使用价值使用价值 8 5 12 )1()0(22333)0(12)5(0max)5(x xf, ff47)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(111222

39、2 xxffffxxx )( 48 )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 x x（1 . 1 . 01 . 1 . 0），），最优值为最优值为 z z = = 1313。总结：总结：解动态规划的一般方法解动态规划的一般方法: :从终点逐段向始点方向寻从终点逐段向始点方向寻找找最小最小( (大大) )的方法。的方法。49 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n 1 排序问

40、题 即n 种零件经过1 种设备进行加工，如何安排？14146 68 820202323交货日期（交货日期（d d）4 45 51 17 73 3加工时间（加工时间（t t）零件代号零件代号2j1j3j4j5j例5.1 五、排序问题50 （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）1j2j3j4j5j零件加工顺序零件加工顺序 工序工序时间时间1 13 34 45 57 7 实际通过时间实际通过时间1 14 48 813132020 交货交货时间时间8 8232314146 62020 平均通过时间2 . 9)1481320(51 x延

41、迟时间 = 13 6 = 751 （2）按时交货排列顺序1j2j3j4j5j零件加工顺序零件加工顺序 工序工序时间时间1 13 34 45 57 7 实际通过时间实际通过时间5 56 6101017172020 交货交货时间时间8 8232314146 62020 平均通过时间6 .11)56101720(51 x延迟时间 = 052 （3）既满足交货时间，又使平均通过时间最小1j2j3j4j5j零件加工顺序零件加工顺序 工序工序时间时间1 13 34 45 57 7 实际通过时间实际通过时间1 16 69 913132020 交货交货时间时间8 8232314146 62020延迟时间 =

42、0 平均通过时间8 .9)1691320(51 x53 2 2、n n 2 2 排序问题排序问题 即即n n 种零件经过种零件经过2 2 种设备进行加工，如何安种设备进行加工，如何安排？排？例5.24 49 95 52 23 3b b5 53 37 78 86 6a a 零件零件2j1j3j4j5j设备设备a ab bt t54经变换为4 49 95 52 23 3b b5 53 37 78 86 6a a 零件零件2j1j3j4j5j设备设备加工顺序图如下：加工顺序图如下：a ab bt t3j1j2j4j5j3 37 75 56 68 89 95 54 43 32 2+2+2+2+2-5-

43、5 加工周期加工周期 t = 3+7+5+6+8+2 = 31t = 3+7+5+6+8+2 = 31小小即即batti 55 3 3、n n 3 3 排序问题排序问题 即即n n 种零件经过种零件经过 3 3 种设备进行加工，如何安种设备进行加工，如何安排？排？例5.33 34 46 68 85 56 64 46 68 83 35 57 79 93 31010c cb ba a1j2j3j4j5ja ab bc ct t56a ab bc ct t变换4+34+36+46+45+85+86+56+56+46+48+68+65+35+37+57+53+93+910+310+3b + b + c

44、 ca+ba+b1j2j3j4j5j57排序4+34+36+46+45+85+86+56+56+46+48+68+65+35+37+57+53+93+910+310+3b + b + c ca+ba+b1j2j3j4j5j复原3 34 46 68 85 56 64 46 68 83 35 57 79 93 31010c cb ba a1j2j3j4j5j58计算t = 6+10+8+7+6+4+3 = 44t = 6+10+8+7+6+4+3 = 44计算依据：abccbabcbattttttttttiiiiii 或即可按下式计算或maxminmaxmin60 六、系统可靠性问题 例例6.某科

45、研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表： 问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？ 高级科学家小组12300.400.600.8010.200.400.5020.150.200.3061 解：用逆序算法。设 阶段：每个研究小组为一个阶段，且阶段123小组12362计算 当n=3时，当n=2时， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=p2(x2) f3*

46、(s2-x2) f2*(s2) x2*01200480480103003203002018020016016263当n=1时， 最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。 x1s1f1(s1,x1)=p1(x1) f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 164连续连续确定性动态规划确定性动态规划对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。65动态规划的应用动态规划的应用机器负荷分配问题机器负荷分配问题 例例1 一种机器能在高低两种不同的负荷状态下

47、工作。设机器在高负荷下生产时，产量函数为p1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为p2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。66解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然

48、sk-xk为分配给低负荷状态下生产的机器数目。 状态转移方程为 sk+1=0.7xk+0.9(sk-xk) 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 ，其中k=1,2,3,4,5。 f6(s6)=0。)()58max)(11kkkkkkksfxsxsf（kksx 067第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5，于是有f5(s5)=8s5。第4阶段： )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxs

49、xsxsxsfxsxsfsxsxsxsx 68 同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ，f4(s4)=13.6s4。 对前几个阶段依次类推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。0*1x0*2x3*3sx 4*4sx 5*5sx 69 下一步工作是确定每年初的状态，按照从

50、前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs70 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而

51、不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得500)(9 . 07 . 05556xsxs25005 . 455sx71 显然，由于固定了终点的状态，x5的取值受到了约束。因此有 类似的， 容易解得 ，f4(s4)=21.7s4-7500。75005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x72 依次类推，得 f3(s3)=24.

52、5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000， 0*1*2*3xxx9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs7297 . 0)(9 . 07 . 03*33*34sxsxs6567 . 0)(9 . 07 . 04*44*45sxsxs73 可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.

53、4s1-750021900。 可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。动态规划进展 在过去的若干年里，动态规划取得了不在过去的若干年里，动态规划取得了不少可喜的进展，特别是它被扩展到多目少可喜的进展，特别是它被扩展到多目标动态规划标动态规划;动态规划应用在本世纪前后动态规划应用在本世纪前后的一个重大突破是其在海量数据（大数的一个重大突破是其在海量数据（大数据）分析中的应用，特别是人类基因组据）分析中的应用，特别是人类基因组计划完成以后，它成为生物信息学的一计划完成以后，它成为生物信息学的一个基本模型和工具。个基本模型和工具。问题与研究方向 应当指出，在克服

54、被贝尔曼称之为应当指出，在克服被贝尔曼称之为“维数灾维数灾”的这一动态规划致命弱点的方面，至今尚的这一动态规划致命弱点的方面，至今尚未取得突破性的进展。所以寻求克服维数灾未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维间题中的应用的有效算法对动态规划在高维间题中的应用具有它的紧迫性。另外，求解不可分优化问具有它的紧迫性。另外，求解不可分优化问题得到的最优策略并不满足最优性原理，或题得到的最优策略并不满足最优性原理，或不具备时间一致性。这牵涉到不可分优化问不具备时间一致性。这牵涉到不可分优化问题模型本身的合理性。因此怎样找出一组可题模型本身的合理性。因此怎样找出一组可分优化间题来

55、逼近一个给定的不可分优化间分优化间题来逼近一个给定的不可分优化间题也对动态规划发展具有显然的重要性。题也对动态规划发展具有显然的重要性。 动态决策问题无处不在。在众多求解序贯决策问题动态决策问题无处不在。在众多求解序贯决策问题方法中，由理查贝尔曼教授率先提出的动态规划方法中，由理查贝尔曼教授率先提出的动态规划方法毫无疑问是最具广泛适用性的。但是任何方法方法毫无疑问是最具广泛适用性的。但是任何方法都有其局限性。动态规划以最优性原理为基础。该都有其局限性。动态规划以最优性原理为基础。该原理要求多阶段决策的最优决策序列必须具备这样原理要求多阶段决策的最优决策序列必须具备这样的性质：不论初始状态和初始

56、决策如何，对于前面的性质：不论初始状态和初始决策如何，对于前面的一系列决策所造成的某一当前状态，其后各阶段的一系列决策所造成的某一当前状态，其后各阶段的决策序列仍需对这一状态构成最优策略。的决策序列仍需对这一状态构成最优策略。 此原理本质上是要求决策者的偏好（风此原理本质上是要求决策者的偏好（风险态度）不随时间和状态发生变化。但险态度）不随时间和状态发生变化。但在现实生活中，人们的偏好常常会随当在现实生活中，人们的偏好常常会随当前所处的时间与状况的改变而不同。前所处的时间与状况的改变而不同。 因此，决策者常常陷入两难境地：应考因此，决策者常常陷入两难境地：应考虑整个时间跨度上的总体目标，还是关

57、虑整个时间跨度上的总体目标，还是关心尾部时间区间上的局部目标。心尾部时间区间上的局部目标。 这进一这进一步导致全局最优决策步导致全局最优决策 遵守承诺的遵守承诺的行为与局部最优决策行为与局部最优决策 受诱惑的受诱惑的行为之间的冲突，造成决策行为的时行为之间的冲突，造成决策行为的时间不一致。此时贝尔曼的最优性原理不间不一致。此时贝尔曼的最优性原理不再满足。再满足。 目前文献中处理这一问题的途径主要有目前文献中处理这一问题的途径主要有两类：完全忽视局部诱惑来求得全局最两类：完全忽视局部诱惑来求得全局最优策略，或完全忽视全局目标从而求得优策略，或完全忽视全局目标从而求得满足时间一致性的策略。其中一个

58、具有满足时间一致性的策略。其中一个具有挑战性的研究课题是怎样平衡（时间不挑战性的研究课题是怎样平衡（时间不一致）动态决策问题中的长期和短期利一致）动态决策问题中的长期和短期利益冲突。益冲突。 李端教授出生于中国上海。他本科毕业于上海复旦大学物理系，其后获上海交通大学自动控制硕士学位与美国凯斯西储大学系统工程博士学位。李教授于一九八七年至一九九四年在美国弗吉尼亚大学任教，任系统工程学系副教授（研究），并任工程系统风险管理中心副主任。他于一九九四年底加入香港中文大学系统工程与工程管理学系，现任系统工程与工程管理学讲座教授，并曾于二零零三年至二零一二年出任该系系主任。 构造了一个带有自我控制的多阶段

59、均值构造了一个带有自我控制的多阶段均值-方差投资博弈模型，其中负责整体投资方差投资博弈模型，其中负责整体投资决策的高层决策者可以通过某种具体的决策的高层决策者可以通过某种具体的惩罚承诺来影响不同时间段上决策执行惩罚承诺来影响不同时间段上决策执行者的偏好，从而建立长期目标和短期目者的偏好，从而建立长期目标和短期目标之间的理性关联。标之间的理性关联。 进一步推导出解析形式的纳什均衡策略进一步推导出解析形式的纳什均衡策略，找到了全局和局部利益之间的最佳平，找到了全局和局部利益之间的最佳平衡点。对于一般的（时间不一致）随机衡点。对于一般的（时间不一致）随机决策问题，进一步扩展了带有自我控制决策问题，进

60、一步扩展了带有自我控制的博弈模型以得到更具一般性的结论。的博弈模型以得到更具一般性的结论。同时论证了该模型与现有经济文献中关同时论证了该模型与现有经济文献中关于自我控制的理论是吻合的。于自我控制的理论是吻合的。动态规划实现中的问题动态规划实现中的问题 应用动态规划解决问题，在有了基本的应用动态规划解决问题，在有了基本的思路之后，一般来说，算法实现是比较思路之后，一般来说，算法实现是比较好考虑的。但有时也会遇到一些问题，好考虑的。但有时也会遇到一些问题，而使算法难以实现。而使算法难以实现。 动态规划思想设计的算法从整体上来看基本都是按照得动态规划思想设计的算法从整体上来看基本都是按照得出的递推关