高等运筹第六讲课件

1、高等运筹第六讲课件高等运筹第六讲课件第二篇 运筹学中的数学规划第四章 线性规划第五章 非线性规划第六章 锥规划、矩阵规划及变分不等式第七章 整数规划第八章 动态规划第九章 向量优化（多目标优化） 牛牛文库文档分享第二篇 运筹学中的数学规划第四章 线性规划www.niuw第八章 动态规划当系统模型具备马尔科夫性，同时目标函数可分且嵌套单调时，基于贝尔曼提出的最优性原理，运用动态规划可将求解多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题。相比其它解法，特别是在有扰动或在随机情况下，动态规划总是能有效地提供一个在当前信息集下的最优反馈控制策略。 牛牛文库文档分享第八章 动态规划当系统

2、模型具备马尔科夫性，同时目标函数可分马尔科夫性在某些随机系统中，有一类具有“无后效性性质”，即当随机过程在某一时刻to所处的状态已知的条件下，过程在时刻tto时所处的状态只和to时刻有关，而与to以前的状态无关。这种在已知“现在”的条件下，“未来”与“过去”彼此独立的特性就被称为马尔科夫性，具有这种性质的随机过程就叫做马尔科夫过程，其最原始的模型就是马尔科夫链。 牛牛文库文档分享马尔科夫性在某些随机系统中，有一类具有“无后效性性质”，即当贝尔曼“最优性原理”这个原理归结为用一组基本的递推关系式使过程连续的最优转移，它可以求这样的最优解，这些最优解是以计算每个决策的后果并对今后的决策制定最优决策

3、为基础的，但在求最优解时要按倒过来的顺序进行，即从最终状态开始到初始状态为止。 牛牛文库文档分享贝尔曼“最优性原理”这个原理归结为用一组基本的递推关系式使过最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。 牛牛文库文档分享最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的7 动态规划(Dynamic Programming) 动态规划的基本概念和思想 最短路径问题 投资分配问题 背包问题 排序问题 牛牛文库文档分享9 动态规划(Dynamic Pr

4、ogramming) 8动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。 牛牛文库文档分享10动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问9最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 牛牛文库文档分享11最短路径问题：

5、给定一个交通网络图如下，其中两点之间的数字10背包问题 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件使用价值 c1 c2 cj cn 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 牛牛文库文档分享12背包问题 有一个徒步旅行者，其可携带物品重量的限度为a11 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要

6、在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。 牛牛文库文档分享13 生产决策问题：企业在生产过程中，由于需求是随时间变化的12根据过程的特性可以将过程按空间、时间等标志分为若干个互相联系又互相区别的阶段。在每一

7、个阶段都需要做出决策，从而使整个过程达到最好的效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。多阶段决策过程的特点： 牛牛文库文档分享14根据过程的特性可以将过程按空间、时间等标志分为若干个互相13针对多阶段决策过程的最优化问题，美国数学家Bellman等人在20世纪50年代初提出了著名的最优化原理，把多阶段决策问题转化为一系列单阶段最优化问题，从而逐个求解，创立了解决这类过程优化问题的新方法：动态规划。对最佳路径

8、（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段始点到全过程终点的一切可能路径中的最佳路径（最优决策），这就是Bellman提出的著名的最优化原理。简言之， 一个最优策略的子策略必然也是最优的。Bellman在1957年出版的Dynamic Programming是动态规划领域的第一本著作。 牛牛文库文档分享15针对多阶段决策过程的最优化问题，美国数学家Bellman14例1、从A 地到E 地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？ 二. 最短路径问题AB2B1B3C1C3D1D2E

9、52141126101043121113965810521C2 牛牛文库文档分享16例1、从A 地到E 地要铺设一条煤气管道,其中需经过三级15 解：整个计算过程分四个阶段，从最后一个阶段开始。 第四阶段（D E）： D 有两条路线到终点E 。 显然有AB2B1B3C1C3D1D2E52141126101043121113965810521C2 牛牛文库文档分享17 解：整个计算过程分四个阶段，从最后一个阶段开始。 第16首先考虑经过 的两条路线第三阶段（C D）： C 到D 有 6 条路线。(最短路线为 )AB2B1B3C1C3D1D2E521412610104312111396581052

10、1C2 牛牛文库文档分享18首先考虑经过 的两条路线第三阶段（C D）：17AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为 )考虑经过 的两条路线 牛牛文库文档分享19AB2B1B3C1C3D1D2E52141261010418AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为 )考虑经过 的两条路线 牛牛文库文档分享20AB2B1B3C1C3D1D2E52141261010419AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为

11、 )第二阶段（B C）： B 到C 有 9 条路线。首先考虑经过 的3条路线 牛牛文库文档分享21AB2B1B3C1C3D1D2E52141261010420AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为 )考虑经过 的3条路线 牛牛文库文档分享22AB2B1B3C1C3D1D2E52141261010421AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路线为 )考虑经过 的3条路线 牛牛文库文档分享23AB2B1B3C1C3D1D2E52141261010422AB2B1B3C1C3

12、D1D2E5214126101043121113965810521C2(最短路线为 )第一阶段（A B）： A 到B 有 3 条路线。 （最短距离为19） 牛牛文库文档分享24AB2B1B3C1C3D1D2E52141261010423 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。即在系统发展的不同时刻（或阶段）根据系统所

13、处的状态，不断地做出决策；动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。 牛牛文库文档分享25 动态规划是用来解决多阶段决策过程最优化的24 动态规划方法的关键：在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。 要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。 即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解

14、。 牛牛文库文档分享26 动态规划方法的关键：在于正确地写出基本的25 2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的. 最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。

15、 牛牛文库文档分享27 2、在多阶段决策过程中，动态规划方法是既把当前26动态规划求解的多阶段问题的特点：每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。具有这种性质的状态称为无后效性（即马尔科夫性）状态。动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。 牛牛文库文档分享28动态规划求解的多阶段问题的特点：www.niuwk.co27 现有数量为a（

16、万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 据此，有下式：三. 投资分配问题 牛牛文库文档分享29 现有数量为a（万元）的资金，计划分配给n 个工28 令：fk(x) 表示 以数量为 x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1kn 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0y

17、 x ），此时还剩 x y（万元）的资金需要分配给前 k1 个工厂,如果采取最优策略，则得到的最大利润为fk1(xy) ,因此总的利润为： gk(y) fk1(xy) 牛牛文库文档分享30 令：fk(x) 表示 以数量为 x 的资金分配给前29 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，x。上式可变为：所以，根据动态规划的最优化原理，有下式： 牛牛文库文档分享31 如果a 是以万元为资金分配单位，则式中的30 例2：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资利润0102030405060g1(

18、x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依据题意，是要求 f4(60) 。 牛牛文库文档分享32 例2：设国家拨给60万元投资，供四个工厂扩建使用，31按顺序解法计算。第一阶段：求 f1(x)。显然有 f1(x) g1(x)，得到下表 投资利润0102030405060f1(x) g1(x)0205065808585最优策略0102030405060第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 牛牛文库文档分享33按顺序解法计算。 投资32最

19、优策略为（40，20），此时最大利润为120万元。同理可求得其它 f2(x) 的值。 牛牛文库文档分享34最优策略为（40，20），此时最大利润为120万元。同理33最优策略为（30，20），此时最大利润为105万元。 牛牛文库文档分享35最优策略为（30，20），此时最大利润为105万元。ww34最优策略为（20，20），此时最大利润为90万元。最优策略为（20，10），此时最大利润为70万元。 牛牛文库文档分享36最优策略为（20，20），此时最大利润为90万元。最优策35最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。 f2(0) 0。最优策略为（0，0），最大利

20、润为0万元。 得到下表最优策略为（20，0），此时最大利润为50万元。 牛牛文库文档分享37最优策略为（10，0）或（ 0 ， 10 ） ，此时最大36 投资利润0102030405060f2(x)020507090105120最优策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 牛牛文库文档分享38 投资010203037最优策略为（20，10，30），最大利润为155万元。同理可求得其它 f3(x) 的值。得到下表 牛牛文库文档分享39最

21、优策略为（20，10，30），最大利润为155万元。同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)。即问题的最优策略。 牛牛文库文档分享40 投资0102030405060f3(x)02539最优策略为（20，0，30，10），最大利润为160万元。 牛牛文库文档分享41最优策略为（20，0，30，10），最大利润为160万元40 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择

22、装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。四、背包问题 牛牛文库文档分享42 有一个徒步旅行者，其可携带物品重量的限度为a 公斤41设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下：用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, ,

23、 n 。所以问题就是求 fn(a) 牛牛文库文档分享43设 xj 为第 j 种物品的装件数（非负整数）则问题的数42其递推关系式为：当 k=1 时，有： 牛牛文库文档分享44其递推关系式为：当 k=1 时，有：www.niuwk.43例3：求下面背包问题的最优解物品(xi ) x1 x2 x3重量（ai） 3 2 5使用价值 8 5 12解：a5 ，问题是求 f3(5) 牛牛文库文档分享45例3：求下面背包问题的最优解物品(xi ) x1 44物品(xi ) x1 x2 x3重量（ai） 3 2 5使用价值 8 5 12 牛牛文库文档分享46物品(xi ) x1 x2 x45物品(xi ) x

24、1 x2 x3重量（ai） 3 2 5使用价值 8 5 12 牛牛文库文档分享47物品(xi ) x1 x2 x46物品(xi ) x1 x2 x3重量（ai） 3 2 5使用价值 8 5 12 牛牛文库文档分享48物品(xi ) x1 x2 x47 牛牛文库文档分享49 牛牛文库文档分享48所以，最优解为 X（1 . 1 . 0），最优值为 Z = 13。总结：解动态规划的一般方法:从终点逐段向始点方向寻找最小(大)的方法。 牛牛文库文档分享50所以，最优解为 X（1 . 1 . 0），最优值为49 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n 1 排

25、序问题 即n 种零件经过1 种设备进行加工，如何安排？14682023交货日期（d）45173加工时间（t）零件代号例5.1 五、排序问题 牛牛文库文档分享51 排序问题指n 种零件经过不同设备加工是的顺序问50 （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）零件加工顺序 工序时间13457 实际通过时间1481320 交货时间82314620 平均通过时间延迟时间 = 13 6 = 7 牛牛文库文档分享52 （1）平均通过设备的时间最小 按零件加工时51 （2）按时交货排列顺序零件加工顺序 工序时间13457 实际通过时间56101

26、720 交货时间82314620 平均通过时间延迟时间 = 0 牛牛文库文档分享53 （2）按时交货排列顺序零件加工顺序 52 （3）既满足交货时间，又使平均通过时间最小零件加工顺序 工序时间13457 实际通过时间1691320 交货时间82314620延迟时间 = 0 平均通过时间 牛牛文库文档分享54 （3）既满足交货时间，又使平均通过时间最小零件加53 2、n 2 排序问题 即n 种零件经过2 种设备进行加工，如何安排？例5.249523B53786A 零件设备ABT 牛牛文库文档分享55 2、n 2 排序问题例5.249523B554经变换为49523B53786A 零件设备加工顺序

27、图如下：ABT3756895432+2+2-5 加工周期 T = 3+7+5+6+8+2 = 31 牛牛文库文档分享56经变换为49523B53786A 55 3、n 3 排序问题 即n 种零件经过 3 种设备进行加工，如何安排？例5.33468564683579310CBAABCT 牛牛文库文档分享57 3、n 3 排序问题例5.3346856456ABCT变换4+36+45+86+56+48+65+37+53+910+3B + CA+B 牛牛文库文档分享58ABCT变换4+36+45+86+56+48+65+3757排序4+36+45+86+56+48+65+37+53+910+3B +

28、CA+B复原3468564683579310CBA 牛牛文库文档分享59排序4+36+45+86+56+48+65+37+53+58计算T = 6+10+8+7+6+4+3 = 44计算依据： 牛牛文库文档分享60计算T = 6+10+8+7+6+4+3 = 44计算依 牛牛文库文档分享 牛牛文库文档分享60六、系统可靠性问题 例6.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表： 问如何分派科学家才能使三个小组都失败的概率（即科研项目最终

29、失败的概率）最小？ 高级科学家小组12300.400.600.8010.200.400.500 牛牛文库文档分享62六、系统可靠性问题高级科学家小组12300.400.6061 解：用逆序算法。设 阶段：每个研究小组为一个阶段，且阶段123小组123 牛牛文库文档分享63 解：用逆序算法。设阶段123小组123www.62计算 当n=3时，当n=2时， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162

30、牛牛文库文档分享64计算 当n=3时， 63当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 1 牛牛文库文档分享65当n=1时， x1f1(s1,x164连续确定性动态规划对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。 牛牛文库文档分享66连续确定性动态规划对于状态变量和决策变量只取连续值，过程65动态规划的应用机器负荷分配问题 例1 一种机器能在高低两种不

31、同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。 牛牛文库文档分享67动态规划的应用机器负荷分配问题www.niuwk.co66解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。

32、 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然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。 牛牛文库文档分享68解 建立动态规划模型： 牛67第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5，于是有f5(s5)=8s5。第4阶段： 牛牛文库文档分享69 牛牛文库文档分享68 同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ，f4(s4)

33、=13.6s4。 对前几个阶段依次类推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。 牛牛文库文档分享70 同样的，f4(s4)是x4的线性单调增函数，69 下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有: 牛牛文库文档分享

34、71 牛牛文库文档分享70 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得 牛牛文库文档分享72 上面所讨论的最优策略过程，初始端状71 显然，由于固定了终点的状态，x5的取值受到了约束。因此有 类似的， 容易解得 ，f4(s4)=21.7s4-7500。 牛牛文库文档分享73 显然，由于固定了终点的状态，x

35、5的取值受72 依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000， 牛牛文库文档分享74 依次类推，得 牛牛文库73 可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.4s1-750021900。 可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。 牛牛文库文档分享75 可见，为了使终点完好的机器数量增加到动态规划进展在

36、过去的若干年里，动态规划取得了不少可喜的进展，特别是它被扩展到多目标动态规划;动态规划应用在本世纪前后的一个重大突破是其在海量数据（大数据）分析中的应用，特别是人类基因组计划完成以后，它成为生物信息学的一个基本模型和工具。 牛牛文库文档分享动态规划进展在过去的若干年里，动态规划取得了不少可喜的进展，问题与研究方向应当指出，在克服被贝尔曼称之为“维数灾”的这一动态规划致命弱点的方面，至今尚未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维间题中的应用具有它的紧迫性。另外，求解不可分优化问题得到的最优策略并不满足最优性原理，或不具备时间一致性。这牵涉到不可分优化问题模型本身的合理性。

37、因此怎样找出一组可分优化间题来逼近一个给定的不可分优化间题也对动态规划发展具有显然的重要性。 牛牛文库文档分享问题与研究方向应当指出，在克服被贝尔曼称之为“维数灾”的这一动态决策问题无处不在。在众多求解序贯决策问题方法中，由理查贝尔曼教授率先提出的动态规划方法毫无疑问是最具广泛适用性的。但是任何方法都有其局限性。动态规划以最优性原理为基础。该原理要求多阶段决策的最优决策序列必须具备这样的性质：不论初始状态和初始决策如何，对于前面的一系列决策所造成的某一当前状态，其后各阶段的决策序列仍需对这一状态构成最优策略。 牛牛文库文档分享动态决策问题无处不在。在众多求解序贯决策问题方法中，由理查此原理本质

38、上是要求决策者的偏好（风险态度）不随时间和状态发生变化。但在现实生活中，人们的偏好常常会随当前所处的时间与状况的改变而不同。 牛牛文库文档分享此原理本质上是要求决策者的偏好（风险态度）不随时间和状态发生因此，决策者常常陷入两难境地：应考虑整个时间跨度上的总体目标，还是关心尾部时间区间上的局部目标。 这进一步导致全局最优决策 遵守承诺的行为与局部最优决策 受诱惑的行为之间的冲突，造成决策行为的时间不一致。此时贝尔曼的最优性原理不再满足。 牛牛文库文档分享因此，决策者常常陷入两难境地：应考虑整个时间跨度上的总体目标目前文献中处理这一问题的途径主要有两类：完全忽视局部诱惑来求得全局最优策略，或完全忽

39、视全局目标从而求得满足时间一致性的策略。其中一个具有挑战性的研究课题是怎样平衡（时间不一致）动态决策问题中的长期和短期利益冲突。 牛牛文库文档分享目前文献中处理这一问题的途径主要有两类：完全忽视局部诱惑来求李端教授出生于中国上海。他本科毕业于上海复旦大学物理系，其后获上海交通大学自动控制硕士学位与美国凯斯西储大学系统工程博士学位。李教授于一九八七年至一九九四年在美国弗吉尼亚大学任教，任系统工程学系副教授（研究），并任工程系统风险管理中心副主任。他于一九九四年底加入香港中文大学系统工程与工程管理学系，现任系统工程与工程管理学讲座教授，并曾于二零零三年至二零一二年出任该系系主任。 牛牛文库文档分享

40、李端教授出生于中国上海。他本科毕业于上海复旦大学物理系，其后构造了一个带有自我控制的多阶段均值-方差投资博弈模型，其中负责整体投资决策的高层决策者可以通过某种具体的惩罚承诺来影响不同时间段上决策执行者的偏好，从而建立长期目标和短期目标之间的理性关联。 牛牛文库文档分享构造了一个带有自我控制的多阶段均值-方差投资博弈模型，其中负进一步推导出解析形式的纳什均衡策略，找到了全局和局部利益之间的最佳平衡点。对于一般的（时间不一致）随机决策问题，进一步扩展了带有自我控制的博弈模型以得到更具一般性的结论。同时论证了该模型与现有经济文献中关于自我控制的理论是吻合的。 牛牛文库文档分享进一步推导出解析形式的纳

41、什均衡策略，找到了全局和局部利益之间动态规划实现中的问题应用动态规划解决问题，在有了基本的思路之后，一般来说，算法实现是比较好考虑的。但有时也会遇到一些问题，而使算法难以实现。 牛牛文库文档分享动态规划实现中的问题应用动态规划解决问题，在有了基本的思路之动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共享一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。 牛牛文库文档分享动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜