《运筹学：第七章动态规划》由会员分享，可在线阅读，更多相关《运筹学：第七章动态规划（118页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章 动态规划动态规划动态规划动态规划 (Dynamic programming)7.1 多阶段决策过程的最优化多阶段决策过程的最优化7.2动态规划的基本概念和基本原理动态规划的基本概念和基本原理7.4 动态规划在经济管理中的应用动态规划在经济管理中的应用7.5 马氏决策规划简介马氏决策规划简介7.3 动态规划模型的建立与求解动态规划模型的建立与求解动动态态规规划划是是解解决决多多阶阶段段最最优优决决策策的的方方法法, , 由由美美国国数数学学家家贝贝尔尔曼曼(R. (R. Bellman) Bellman) 于于 19511951年年首首先先提出提出; ;19571957年年贝贝尔尔
2、曼曼发发表表动动态态规规划划方方面面的的第第一一部部专专著著“动动态态规规划划”, , 标标志志着着运运筹筹学学的的一一 个个新新分分支支的的创立。创立。动动态态规规划划将将复复杂杂的的多多阶阶段段决决策策问问题题分分解解为为一一系系列列简简单单的的、离离散散的的单单阶阶段段决决策策问问题题, 采采用用顺顺序序或或逆逆序序求求解解方方法法, 通通过过解解一一系系列列小问题达到求解整个问题目的小问题达到求解整个问题目的;动动态态规规划划的的各各个个决决策策阶阶段段不不但但要要考考虑虑本本阶阶段段的的决决策策目目标标, 还还要要兼兼顾顾整整个个决决策策过过程程的的整体目标整体目标, 从而实现整体最
3、优决策从而实现整体最优决策.动态规划的分类动态规划的分类:离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型动态规划的特点动态规划的特点: 动态规划是研究动态规划是研究动态规划是研究动态规划是研究多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题的一种运筹学方法。的一种运筹学方法。的一种运筹学方法。的一种运筹学方法。 动态规划与其他规划方法的不同之处在于：动态规划与其他规划方法的不同之处在于：动态规划与其他规划方法的不同之处在于：动态规划与其他规划方法的不同之处在于：动态规划是动态规划是动态规划是动态规划是求解某类问题的一种方法，是考察求解某类问题的一种方法
4、，是考察求解某类问题的一种方法，是考察求解某类问题的一种方法，是考察问题的问题的问题的问题的一种途径，而一种途径，而一种途径，而一种途径，而不是一种特定算法。不是一种特定算法。不是一种特定算法。不是一种特定算法。因而，它不像线性规划有一个标准因而，它不像线性规划有一个标准因而，它不像线性规划有一个标准因而，它不像线性规划有一个标准的数学表达式和明确定义的一组（算法）规则，而必须的数学表达式和明确定义的一组（算法）规则，而必须的数学表达式和明确定义的一组（算法）规则，而必须的数学表达式和明确定义的一组（算法）规则，而必须对具体问题进行具体分析处理。因而学习动态规划时，对具体问题进行具体分析处理。
5、因而学习动态规划时，对具体问题进行具体分析处理。因而学习动态规划时，对具体问题进行具体分析处理。因而学习动态规划时，除了对基本概念和方法正确理解外，还应在一定经验积除了对基本概念和方法正确理解外，还应在一定经验积除了对基本概念和方法正确理解外，还应在一定经验积除了对基本概念和方法正确理解外，还应在一定经验积累基础上，以丰富的想象力去建立模型，用创造性的技累基础上，以丰富的想象力去建立模型，用创造性的技累基础上，以丰富的想象力去建立模型，用创造性的技累基础上，以丰富的想象力去建立模型，用创造性的技巧去求解。巧去求解。巧去求解。巧去求解。 与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互
6、补关系与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互补关系, , 尤其在处理非线性、尤其在处理非线性、尤其在处理非线性、尤其在处理非线性、离散性问题时有其独到的特点。离散性问题时有其独到的特点。离散性问题时有其独到的特点。离散性问题时有其独到的特点。7.17.1多阶段决策过程的最优化多阶段决策过程的最优化每个阶段都要进行每个阶段都要进行决策决策, ,目的是使整个过程的决策达到最优效果。目的是使整个过程的决策达到最优效果。多阶段决策问题：多阶段决策问题：在多阶段决策过程中在多阶段决策过程中, ,系统的动态过程可以按照时间进程分为系统的动态过程可以按照时间进程分为状态状态相互相互联联系
7、系而又相互而又相互区别区别的各个的各个阶段阶段；12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策多阶段决策问题的典型例子：多阶段决策问题的典型例子：1 .时间阶段例子时间阶段例子(机器负荷分配问题机器负荷分配问题)：某种机器可以在高低两种不同的负：某种机器可以在高低两种不同的负荷下进行生产。高负荷年产量荷下进行生产。高负荷年产量8，年完好率，年完好率0.7；低负荷年产量；低负荷年产量5，年完，年完好率好率0.9.现有完好机器现有完好机器1000台，需制定一个台，需制定一个5年计划，以决定每年安排年计划，以决定每年安排多少台机器投入高、低负荷下生产，使多少台机器投入高、低负荷下生产
8、，使5年的总产量最大。年的总产量最大。125S1 1=1000=1000决策决策x1 1S2 2输出输出v1 1决策决策x2 2输出输出v2 2S3 3S5 5决策决策x5输出输出v52 . (空间阶段例子空间阶段例子)最短路问题最短路问题：给定一个交通网络图如下，其中两点之间：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从的数字表示距离（或花费），试求从A点到点到G点的最短距离（总费用最点的最短距离（总费用最小）。小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643多阶段决策问题的其他
9、典型例子：多阶段决策问题的其他典型例子：1 . 生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。2. 航航天天飞飞机机飞飞行行控控制制问问题题：由由于于航航天天飞飞机机的的运运动动的的环环境境是是不不断断变变化化的的，因因此此就就要要根根据据航航天天飞飞机机飞飞行行在在不不同同环环境境中中的的情情况况，不不断断地地决决定定航航天天飞飞机机
10、的的飞飞行行方方向向和和速速度度（状状态态），使使之之能能最最省省燃燃料料和和实实现现目目的的（如如软着落问题）。软着落问题）。 不包含时间因素的静态决策问题（本质上是一次决策问题）也可以不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。解决。3 . 线性规划、非线性规划等静态的规划问题线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。段的概念，应用动态规划方法加以解决。 以上例子代表了这样一种特殊的
11、决策过程，该过程可以分为互相联以上例子代表了这样一种特殊的决策过程，该过程可以分为互相联系的若干阶段，每一阶段都需作出决策，从而形成全过程的决策。系的若干阶段，每一阶段都需作出决策，从而形成全过程的决策。这种把一个问题看作一个前后关联具有链状结构的多阶段过程称为这种把一个问题看作一个前后关联具有链状结构的多阶段过程称为多阶段决策过程，也称序贯决策过程，相应的问题多阶段决策过程，也称序贯决策过程，相应的问题称为多阶段决策称为多阶段决策问题问题。7.2 7.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理1、阶段、阶段2、状态、状态3、决策和策略、决策和策略4、状态转移方程、状态转移方
12、程5、指标函数、指标函数动态规划的基本概念动态规划的基本概念1、阶段：、阶段：p把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按，以便于按一定的次序去求解。一定的次序去求解。p描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分，一般是根据时间和空。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。间的自然特征来进行的，但要便于问题转化为多阶段决策。年、年、月、月、路段路段动态规划的基本概念动态规划的基本概念无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发
13、展不受这个如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；动态规划模型时，要充分注意是否满足无后效性的要求；状态变量要满足无后效性的要求；状态变量要满足无后效性的要求；如果状态变量不能满足无后效如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。性的要求，应适当地改变状态的定义或规定方法。2、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客
14、观条件自然状况或客观条件。通常一个阶段有若。通常一个阶段有若干个状态，描述过程状态的变量干个状态，描述过程状态的变量sk称为称为状态变量状态变量。一个数、一个数、一组数、一组数、一个向量一个向量 状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合状态允许集合Sk。3、决策：、决策：每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选每阶段状态确定后的抉择，即从该状态演变到下阶段某状态的选择，用择，用决策变量决策变量uk(sk) 表示由表示由k阶段阶段sk出发所作的决策。出发所作的决策。在实际问题中决策变量的取值往往在某一范围之内，此
15、范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允允许决策集合，有许决策集合，有 。策略：策略：在在实实际际问问题题中中，可可供供选选择择的的策策略略有有一一定定的的范范围围，称称为为允允许许策策略略集集合合，记记作作 。从允许策略集合中找出达到最优效果的策略称为。从允许策略集合中找出达到最优效果的策略称为最优策略最优策略。 (空间阶段例子空间阶段例子)最短路问题最短路问题：给定一个交通网络图如下，其中两点之间的：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从数字表示距离（或花费），试求从A点到点到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。
16、123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643阶段，状态（及它的无后效性），状态集合，决策，决策集合，策略阶段，状态（及它的无后效性），状态集合，决策，决策集合，策略图示如下：图示如下：状态转移方程是确定过程由一状态转移方程是确定过程由一个状态到另一个状态的演变过个状态到另一个状态的演变过程。如果第程。如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策变量一经的值、该阶段的决策变量一经确定，第确定，第k+1阶段状态变量阶段状态变量sk+1的值也就确定。的值也就确定。其状态转移方程如下（一般形式）其状态转移
17、方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。4、状态转移、状态转移动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下状态具有无后效性的多阶段决策过程的状态转移方程如下 5、指标函数和最优值函数：、指标函数和最优值函数：u 用来衡量所选定策略优劣的一种数量指标，称为用来衡量所选定策略优劣的一种数量指标，称为指标函数指
18、标函数。在。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。成本、产量或资源消耗等。u 分为分为阶段指标函数阶段指标函数和和过程指标函数过程指标函数。u 阶段指标函数：第阶段指标函数：第k阶段，从状段，从状态sk出出发，采取决策，采取决策uk时的效益，的效益，记作作d(sk, uk)u 过程指程指标函数：函数： 表示初始状表示初始状态为s1采用策略采用策略p1,n时原原过程的指程的指标函数函数值; 表示在第表示在第k阶段，状段，状态为sk采用策略采用策略pk,n时，后部子，后部子过程的指程的指标函数函
19、数值。 效益效益最优指标函数最优指标函数: 问题：动态规划的最优解和最优值是什么？问题：动态规划的最优解和最优值是什么？ 最优解：最优策略最优解：最优策略p1,n 最优值：最优指标函数值最优值：最优指标函数值f1(s1)解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列f f1 1( (s s1 1) ) 最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优指标函数值最优指标函数值从从 k k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值(空间阶段例子空间阶段例子)最短路问题最短路问题：给定
20、一个交通网络图如下，其中两点之间的：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从数字表示距离（或花费），试求从A点到点到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643状态转移，阶段指标函数，过程指标函数，最优指标函数状态转移，阶段指标函数，过程指标函数，最优指标函数1、基本原理、基本原理动态规划的基本思想与最优化原理动态规划的基本思想与最优化原理D2E2F1F2G以最短路为例说明以最短路为例说明2、基本方程、基本方程 根据最优性
21、原理，可建立从后向前逆推求解的递推公式根据最优性原理，可建立从后向前逆推求解的递推公式动态规划基本方程。动态规划基本方程。例例 从从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过两级中间站，两点其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？使总距离最短？ AB1B2C1C2C3D24333321114最短路径问题最短路径问题s1s2s3s4 解：解：整个计算过程分三个阶段，从最后一个阶段开始（逆序解法）。整个计算过程分三个阶段，从最后一个阶段开始（逆序解法）。 步
22、骤步骤1：C D： C 有三条路线到终点有三条路线到终点D 。 AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f3(C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4 u3 (C1 ) =D； u3 (C2 ) =D ； u3 (C3 ) =D s1s2s3s4k=1k=2k=3 d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5步骤步骤2：B C： B 到到C 有
23、六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)s1s2s3s4u2 (B1 ) =C1 d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)s1s2s3s4u2 (B2 ) =C1 步骤步骤3： A B： A 到到B 有二条路线。有二条路
24、线。 f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f1 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2Au1 (A ) =B1 AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 61、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的、动态规划方法的关键在
25、于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最中，均利用了它前面的子问题的最优化结果，
26、依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。后一个子问题所得的最优解，就是整个问题的最优解。动态规划的基本思想总结动态规划的基本思想总结2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的一般是不同的. 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段、在求整个问
27、题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。逐段变换得到，从而确定了最优路线。动态规划的优缺点动态规划的优点动态规划的优点动态规划的优点动态规划的优点可以解决线性可以解决线性, 非线性非线性, 整整数规划无法有效求解的复数规划无法有效求解的复杂问题杂问题;容易找到全局最优解容易找到全局最优解;可以得到一组解可以得到一组解;动态规划的缺点：动态规划的缺点：动态规划的缺点：动态规划的缺点：没有标准的模型可供应用没有标准的模型可供应用, 构构模依赖于个人的
28、经验和技巧模依赖于个人的经验和技巧;状态变量需满足无后效性状态变量需满足无后效性, 有有较大的局限性较大的局限性;动态规划的维数灾难限制了动态规划的维数灾难限制了对规模较大问题的求解效率对规模较大问题的求解效率;7.3 7.3 动态规划模型的建立与求解动态规划模型的建立与求解一、建立动态规划模型的步骤一、建立动态规划模型的步骤 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于
29、静静态态问问题题要要人人为为地地赋赋予予“时时间间”概概念念，以便划分阶段。以便划分阶段。2、正确选择状态变量、正确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选选择择是是从从过程演变的特点中寻找。过程演变的特点中寻找。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要要给给出出决决策变量的取值范围，即确定允许决策集合。策变量的取值范围
30、，即确定允许决策集合。4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，状态阶段状态变量，状态转移方程应当具有递推关系。转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是指从第阶段的收益，最优指标函数是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动阶段末所获得收益的最优值，最后写出动态规划基本方程。态规划基本方程。以上五步是建立动态
31、规划数学模型的一般步骤。由于动态规划模型与线以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。 例例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664求从求从A到到G的最短路径（逆序解法）的最短路径（逆序解法）3s1s2s3s4s5s6s7k=5k=5，出发点，出发点
32、E1E1、E2E2、E3E3u5(E1)=F1E1 F1 GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=D
33、1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,= minf1(A)= mind1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1
34、F2G531368763685338422213335256643例例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径（逆序解法）的最短路径（逆序解法）3s1s2s3s4s5s6s7例例AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664求从求从A到到G的最短路径（顺序解法）的最短路径（顺序解法）3s1s2s3s4s5s6s7例例AB1B2C1C2C3C4D1D
35、2D3E1E2E3F1F2G53136876368533842221333525664最优路线为：最优路线为：A B1 C2 D1 E2 F2 G 路长路长18求从求从A到到G的最短路径（顺序解法）的最短路径（顺序解法）3s1s2s3s4s5s6s7二、顺序解法与逆序解法的区别二、顺序解法与逆序解法的区别1、状态转移方式不同、状态转移方式不同12ns1u1s2u2s3snunsn+1V1(s1, u1) V2(s2, u2)Vn(sn, un)12ns1u1s2u2s3snunsn+1V1(s2, u1) V2(s3, u2)Vn(sn+1, un)顺序解法与逆序解法的区别顺序解法与逆序解法的
36、区别2、指标函数的定义不同、指标函数的定义不同顺序解法与逆序解法的区别顺序解法与逆序解法的区别3、基本方程形式不同、基本方程形式不同u 当指标函数为阶段指标和形式当指标函数为阶段指标和形式顺序解法与逆序解法的区别顺序解法与逆序解法的区别3、基本方程形式不同、基本方程形式不同u 当指标函数为阶段指标积形式当指标函数为阶段指标积形式求从求从A到到E的最短路径（顺序法）的最短路径（顺序法）路线为路线为AB2C1 D1 E ，最短路径为，最短路径为19AB2B1B3C1C3D1D2EC252141 12610104312111396581052课堂练习课堂练习1三、基本方程分段求解的几种常用算法三、基
37、本方程分段求解的几种常用算法 1、离散变量的分段穷举算法、离散变量的分段穷举算法状状态态变变量量与与决决策策变变量量只只能能取取离离散散值值，且且取取值值个个数数较较少少时时，可可以以用分段穷举算法，如最短路径问题。用分段穷举算法，如最短路径问题。2、连续变量的解法、连续变量的解法状状态态变变量量与与决决策策变变量量为为连连续续变变量量，可可采采用用经经典典解解析析方方法法、线线性性规划方法、非线性规划方法或其他数值计算方法等。规划方法、非线性规划方法或其他数值计算方法等。例 分配投资问题 问题的一般描述如下：设有某种资源，总数量为a，用于生产n种产品；若分配数量 xi 用于生产第i种产品，其
38、收益为gi(xi)。问应如何分配，使得使总收益最大？ 该类问题可用动态规划进行求解： 问题分n个阶段，即k = 1，2，nsk ：第 k 阶段初拥有的资金总量xk ：项目 k 的投资额，0 xk sk uk= xksk+1 = sk - xk Vk(sk,xk) = gk(xk)最优指标函数 fk(sk)：当可投资金额为时sk ，投资第k-n项所得的最大收益。（逆序）基本方程为：例 （投资决策问题，逆序解法）某公司有资金10万元，拟投资于3个项目，已知对第i个项目投资xi万元，收益为g i (xi)，问应如何分配资金可使总收益最大？其中，解：现人为地给它赋予“时段”的概念，将投资项目排序，首先
39、考虑项目1的投资，然后考虑项目2的投资，问题分为3个阶段，每个阶段只决定一个项目的投资金额。 阶段k=1,2, 3决策变量uk：第k个项目的投资额状态变量sk：在第k阶段时可以用于投资第k到第3个项目的资金数指标函数Vk,n：第k阶段可分配的资金数为sk时，第k至第3个 项目的最大总收益状态转移方程：sk+1 = sk -uk边界条件：资源分配问题的动态规划基本方程：建立递推公式：k=3,2,1：第k阶段可分配的资金数为sk时，第k至第3个 项目的最大总收益用逆序解法解k=3时k=2时令由解得极大值只可能在0,s2端点取得，最优投资方案为全部资金投于第三个项目，可得最大收益200万元。sk+1
40、 = sk -uk例 （投资决策问题，顺序解法）某公司有资金10万元，拟投资于3个项目，已知对第i个项目投资xi万元，收益为g i (xi)，问应如何分配资金可使总收益最大？其中，解：现人为地给它赋予“时段”的概念，将投资项目排序，首先考虑项目1的投资，然后考虑项目2的投资，问题分为3个阶段，每个阶段只决定一个项目的投资金额。 阶段k=1,2, 3决策变量uk：第k个项目的投资额状态变量sk+1：在第k阶段，可用于投资第1到第k个项目的资金数， s4 =10指标函数V1,k：第k阶段可分配的资金数为sk+1时，第1至第k个 项目的最大总收益状态转移方程：sk = sk+1 - xk边界条件：资
41、源分配问题的动态规划基本方程：建立递推公式：k=3,2,1：第k阶段可分配的资金数为sk+1时，第1至第k个 项目的最大总收益用顺序解法解K=1时k=2时k=3时最优投资方案为全部资金投于第三个项目，可得最大收益200万元。sk = sk+1 - xk三、基本方程分段求解的几种常用算法三、基本方程分段求解的几种常用算法 1、离散变量的分段穷举算法、离散变量的分段穷举算法状状态态变变量量与与决决策策变变量量只只能能取取离离散散值值，且且取取值值个个数数较较少少时时，可可以以用分段穷举算法，如最短路径问题。用分段穷举算法，如最短路径问题。2、连续变量的解法、连续变量的解法状状态态变变量量与与决决策
42、策变变量量为为连连续续变变量量，可可采采用用经经典典解解析析方方法法、线线性性规划方法、非线性规划方法或其他数值计算方法等。规划方法、非线性规划方法或其他数值计算方法等。3、连续变量的离散化解法、连续变量的离散化解法 s110x10246810g1+f220013688605040f12000最优投资方案为全部资金投于第三个项目，可得最大收益200万元。三、基本方程分段求解的几种常用算法三、基本方程分段求解的几种常用算法 1、离散变量的分段穷举算法、离散变量的分段穷举算法状状态态变变量量与与决决策策变变量量只只能能取取离离散散值值，且且取取值值个个数数较较少少时时，可可以以用分段穷举算法，如最
43、短路径问题。用分段穷举算法，如最短路径问题。2、连续变量的解法、连续变量的解法状状态态变变量量与与决决策策变变量量为为连连续续变变量量，可可采采用用经经典典解解析析方方法法、线线性性规划方法、非线性规划方法或其他数值计算方法等。规划方法、非线性规划方法或其他数值计算方法等。3、连续变量的离散化解法、连续变量的离散化解法4、高维问题的降维法及疏密格子点法、高维问题的降维法及疏密格子点法 以二维分配问题为例研究高维问题的处理方法。以二维分配问题为例研究高维问题的处理方法。 7.4 7.4 动态规划在经济管理中的应用动态规划在经济管理中的应用有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者
44、，其可携带物品重量的限度为a 公斤，设有公斤，设有n 种物品可种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/件）件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。
45、人造卫星内的物品装载问题等。1、 背包问题背包问题设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学模型如下：种物品的装件数（非负整数）则问题的数学模型如下：用动态规划方法求解用动态规划方法求解 例：例：求下面背包问题的最优解求下面背包问题的最优解(a=5)物品物品 1 2 3重量重量（公斤）（公斤） 3 4 5使用价值使用价值 4 5 6解：解：a5 ，问题是求，问题是求 f3(5)S2012345678910f1(s2)000444888121200011122233例：例：求下面背包问题的最优解求下面背包问题的最优解(a=5)物品物品 1 2 3重量重量（公斤）（公斤） 3 4
46、 5使用价值使用价值 4 5 6S3012345678910x200000 10 10 10 10 1 20 1 20 1 200044 54 58 58 98 9 1012 9 1012 13 100004 5 58 910 12 130000 1 10 12 01对于k=3最大值为13练习：练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运吨，问如何安排运输，使总利润最大？输，使总利润最大？种类种类 1 2 3重量
47、（吨重量（吨/ /公斤）公斤） 2 3 4 单件利润（元）单件利润（元） 80 130 180最优方案：最优方案：X1 =（0,2,0）X2 =（1,0,1）Z=260（1）库存问题）库存问题2、 生产经营问题生产经营问题例 某工厂生产并销售某种产品，已知今后四个月市场需求预测如表7-7，又每月生产j单位产品费用为：每月库存j单位产品的费用为E(j)=0.5j(千元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本
48、月初库存量与产量之和。阶段k状态变量sk决策变量uk状态转移方程阶段指标终端条件月份，k=1,2,3,4；第k个月初（发货以前）的库存量；第k个月的生产量；sk+1=sk+uk-gk；gk(sk ,dk)=ckuk；f8(s8)=0,x8=0；最优指标函数fk(sk)递推方程对于u3 max(0,2-s3)u3min(6,5-s3,6-s3),其中s3的取值范围为0,1,2,3当s3=0时对于K=3u*3(s3)f3( s3)C+E+f4u3(s3)00128811.5121211.5812.51211.581312.51211.513.51312.5122103210432154323210
49、s3对于K=2u*2(s2)f2( s2)C+E+f3u2(s2) 3 4 513.5 15 15.5 1614.51713.5161517.51716.515.51817.5171618.5182104321543265433 2 10s2315.50u*1(s1)f1( s1)C+f2u1(s1)221.52221.52154320s121对于K=1得出最佳生产计划为，第一个月生产2单位，第二个月生产5单位，第三个月不生产，第四个月生产4个单位。总结此类生产存贮问题的基本方程为：若最大库存量为q,每月最大生产能力为p.则状态集合为：允许决策集合为：（2）采购与销售问题）采购与销售问题2、
50、生产经营问题生产经营问题某商店在未来的四个月里，准备利用商店的一个仓库来专门经销某种商品，仓库最大容量为这种商品1000单位。假定商店每月只能卖出仓库现有的货物。当商店在某月购货时，下月初才能到货。预测该商店未来四个月的买卖价格如 下表，假定商店在1月开始经销时，仓库贮有该商品500单位，试问，如何制定这四个月的订购与销售计划，使获利最大（不计库存费）。 1 10 12 2 8 9 3 11 13 4 15 17月份（k）购买单价 （ck）销售单价 （pk）已知：仓库最大容量为1000单位。商店每月只卖出仓库现有的货物。当商店在某月购货时，下月初才能到货。第k月的购买单价ck，销售单价pk，1
51、月开始经销时，仓库贮有该商品500单位，如何制定四个月的订购与销售计划，使获利最大（不计库存费）。解：k=1，2，3，4状态变量skxk第k月卖出的货物数量,0xk sk yk第k月订购的货物数量，0yk 1000-(sk -xk )求f1（500）决策变量：s1=500 ,0sk1000 k=2，3，4第k个月的库存量（含上月的定货）x3 + x1 =s3 - x3 +y3 + x2= 1000-s3 maxZ=-4 x3+6 y3 +17s3 x1,x2,x3, y30 x3 y3 x1 x2-4 6 0 0Z- 17s3 x1 1 0 1 0s3x2-1 1 0 11000-s3x3 y
52、3 x1 x22 0 0 -6Z-6000-11s3 x1 1 0 1 0s3y3-1 1 0 11000-s3x3 y3 x1 x20 0 -2 -6Z-6000-13s3 x3 1 0 1 0s3y3 0 1 1 11000x*3= s3y*3=100 0最优值 Z=6000+13s3x3 s3 - x3 +y3 1000-s3 x3, y30 求maxZ=-4 x3+6 y3 +17s3标准型：最优解：f1（500）=17000x*1= 500，y*1=0f2（s2）=x*2= 011000+8s2，y*2=1000-s2f3（s3）=x*3= s3，y*3=10006000+13s3f
53、4（s4）= 17 s4x*4= s4，y*4= 0xk第k月卖出的货物数量yk第k月订购的货物数量sk+1 = sk + yk -xkfk（sk）=第k月初库存为时sk ，从第k月到第4月末所获得的最大利润 结论：当第1个月初库存为时500时， 4个月能获得的最大利润为17000 四个月的订购与销售计划：第1个月：卖出500个，订购0个第2个月：卖出0个，订购1000个第3个月：卖出1000个，订购1000个第4个月：卖出1000个，订购0个3、设备更新问题、设备更新问题已知一台设备已使用了t年，再使用一年的效益为r(t)，维修费为v(t),若在第t+1年更新，则更新费为c(t)，为折扣因子
54、，表示一年以后的单位收入价值相当于现年的单位。现要做一个n年的设备更新计划：每年年初做出决策，是继续使用旧机器还是更换一台新机器，使n年的总收益最大。建模： 阶段k=1,2, ,n，表示计划使用该设备的年限数决策变量uk状态变量sk=第k年初,机器已使用过的年限状态转移方程：第k年的收益：基本方程：基本方程：当K=5当K=4当K=3当K=2当K=1上述计算递推回去，当u1*(0)=K,知s2=1得u2*=R, u3*=R, u4*=R, u5*=K;4、复合系统工作可靠性问题、复合系统工作可靠性问题该该问问题题为为整整数数非非线线性性规规划划，可可以以用用动动态态规规划划求求解解，设设关关键键
55、器器件件数数n = 3，总总费费用用为为120万万元元。器器件件的的单单价价与与可可靠靠性如下表：性如下表： 1300.1 2150.2 3200.5 器件号i 单价(万元) 失效概率pi建立动态规划模型：建立动态规划模型：建立动态规划模型：建立动态规划模型：k=3k = 2: s3 = s2 c2x2k = 1:s2 = s1 c1 x1因此得到：x1 = 1 ,s2=120-30=90, x2 = 2 ,s3=90-2*15=60 , x3 = 3 即：p=1，2，3 可靠性为0.756例例 (机器负荷分配问题机器负荷分配问题)。某种机器可在高低两种不同的负荷下进行生。某种机器可在高低两种
56、不同的负荷下进行生产。设机器在高负荷下生产的产量函数为产。设机器在高负荷下生产的产量函数为g=8u1，其中，其中u1为投入生产的为投入生产的机器数量，年完好率机器数量，年完好率a=0.7；在低负荷下生产的产量函数为；在低负荷下生产的产量函数为h=5y，其中，其中y为投入生产的机器数量，年完好率为为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机。假定开始生产时完好机器的数量器的数量s1=1000。试问每年如何安排机器在高、低负荷下的生产，使。试问每年如何安排机器在高、低负荷下的生产，使在在5年内生产的产品总产量最高。年内生产的产品总产量最高。解：解：设阶段序数设阶段序数 k 表示
57、年度；状态变量表示年度；状态变量 sk 为第为第 k 年度初拥有的完好机年度初拥有的完好机器数量，同时也是第器数量，同时也是第 k-1 年度末时的完好机器数量。年度末时的完好机器数量。决策变量决策变量 uk 为第为第 k 年度中分配高负荷下生产的机器数量，则该年度中年度中分配高负荷下生产的机器数量，则该年度中分配在低负荷下生产的机器数量为分配在低负荷下生产的机器数量为 sk-uk，这里，这里 sk 和和 uk 均取连续变量。均取连续变量。 状态转移方程为状态转移方程为k 段允许决策集合为段允许决策集合为设设 vk(sk,uk) 为第为第 k 年度的产量，则年度的产量，则指标函数为指标函数为 令
58、最优值函数令最优值函数 fk(sk) 表示由资源量表示由资源量 sk 出发，从第出发，从第 k 年开始到第年开始到第5年结年结束时所生产的产品的总产量最大值，则有逆推关系式束时所生产的产品的总产量最大值，则有逆推关系式采用逆推法，从第采用逆推法，从第5年度开始向前逆推计算。年度开始向前逆推计算。最优策略为最优策略为即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产，这样所得的产量最高，总计为完好机器投入高负荷生产，这样所得的产量最高，总计为23691.2。在得到整个问题的最优指标函数值和最优策略后，
59、还需反过来确定每年在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的机器状态，即从始端向终端递推计算出每年年初完好机器数。已年初的机器状态，即从始端向终端递推计算出每年年初完好机器数。已知知 s1=1000台，则可得台，则可得采用采用LINGO程序程序来进行求解。该问题的静态规划模型为来进行求解。该问题的静态规划模型为 sets: stages/1.6/:s; years/1.5/:u;endsetsdata: a=0.7; b=0.9;enddata max=sum(years(i):8*u(i)+5*(s(i)-u(i); s(1)=1000; for(stages(j)
60、|j #ge# 2:s(j)=0.7*u(j-1)+0.9*(s(j-1)-u(j-1); for(years(i):u(i)=s(i);上面所讨论的最优策略过程，始端状态上面所讨论的最优策略过程，始端状态 s1 是固定的，终端状态是固定的，终端状态 s6 是自是自由的。由此所得出的最优策略称为由的。由此所得出的最优策略称为始端固定终端自由的最优策略始端固定终端自由的最优策略，实，实现的是现的是5年里的产品总产量最高。年里的产品总产量最高。如果在终端也附加一定的约束条件，如规定在第如果在终端也附加一定的约束条件，如规定在第5年度结束时，完好年度结束时，完好的机器数量为的机器数量为500台（上面
61、只有台（上面只有277.83台），问如何安排生产才能在满台），问如何安排生产才能在满足这一终端要求的情况下产量最高？足这一终端要求的情况下产量最高？如果采用如果采用LINGO程序进行求解，则只要在以上的程序清单中增加一程序进行求解，则只要在以上的程序清单中增加一条约束，即增加语句条约束，即增加语句s(6)=500;运算结果如下：运算结果如下： Global optimal solution found. Objective value: 21832.85 Total solver iterations: 2 Variable Value Reduced Cost S( 1) 1000.000
62、0.000000 S( 2) 900.0000 0.000000 S( 3) 810.0000 0.000000 S( 4) 729.0000 0.000000 S( 5) 656.1000 0.000000 S( 6) 500.0000 0.000000 U( 1) 0.000000 2.407300 U( 2) 0.000000 1.897000 U( 3) 0.000000 1.330000 U( 4) 0.000000 0.7000000 U( 5) 452.4500 0.000000即在前即在前4年将完好年将完好机器全部在低负机器全部在低负荷状态下运行，荷状态下运行，第第5年年初将年
63、年初将656.1台完好的机台完好的机器中的器中的452.45台台用于高负荷生产，用于高负荷生产，其他的机器在低其他的机器在低负荷状态下生产，负荷状态下生产，则在第则在第5年末完好年末完好的机器数为的机器数为500台，台，最优的总产量为最优的总产量为21832.85。7.5 7.5 马氏决策规划简介马氏决策规划简介马尔可夫决策规划(Markov decision programming) 马氏决策规划的基本概念于20世纪60年代建立，几十年来，无论是理论上还是应用方面都有很大进展。根据其报酬函数和目标函数的不同，建立了不同类型的优化模型，如有限阶段模型、折扣模型、平均模型、无界报酬模型等。对这些模型的理论研究已取得了较好的成果。 另外，马氏决策规划也被成功地应用于许多实际问题，如机器的最优更换、维修问题、质量控制问题、水库最优调度问题、随机旅行售货点问题、电话网络中的最优线路问题、最优投资与消费问题等等。
