运筹学-第3版-课件-第5章动态规划

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外Dynamic ProgrammingDynamic Programming第第5 5章章 动态规划动态规划第第2页页综综 述述 动态规划是运筹学的一个分支，是解决多阶段决策问题的一动态规划是运筹学的一个分支，是解决多阶段决策问题的一种最优化方法。与线性规划不同的是，动态规划没有统一的数学种最优化方法。与线性规划不同的是，动态规划没有统一的数学模型和算法，它要求对具体问题进行具体分析，因而动态规划更模型和算法，它要求对具体问题进行具体分析，因而动态规划更多地是求解多阶段决策问题的一种定量分析方法和途径。多地是求解多阶

2、段决策问题的一种定量分析方法和途径。 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以分为若指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。达到最优。第第3页页综综 述述 自

3、从自从2020世纪世纪5050年代，美国数学家贝尔曼提出动态规划年代，美国数学家贝尔曼提出动态规划的最优性原理以来，动态规划方法已获得广泛应用，的最优性原理以来，动态规划方法已获得广泛应用，它也成为现代企业管理中的一种重要的决策方法。应它也成为现代企业管理中的一种重要的决策方法。应用动态规划可以解决诸如最优路径问题、资源分配问用动态规划可以解决诸如最优路径问题、资源分配问题、生产调度问题、库存问题、设备更新问题以及最题、生产调度问题、库存问题、设备更新问题以及最优控制问题等。优控制问题等。 本章讨论多阶段决策问题以及动态规划的基本本章讨论多阶段决策问题以及动态规划的基本概念、原理和方法，并通过

4、若干典型实例来说明动概念、原理和方法，并通过若干典型实例来说明动态规划在实践中的一些应用。态规划在实践中的一些应用。第第4页页n5.1 多阶段决策问题多阶段决策问题n5.2 最优化原理最优化原理n5.3 确定性的定期多阶段决策问题确定性的定期多阶段决策问题n5.4 确定性的不定期多阶段决策问题确定性的不定期多阶段决策问题 第第5 5章章 动态规划动态规划第第5页页5.1 多阶段决策问题多阶段决策问题 例例1 最短路问题最短路问题 例例2 资源分配问题资源分配问题 例例3 生产和库存问题生产和库存问题 例例4 机金矿问题机金矿问题 例例5 多阶段决策问题多阶段决策问题例1、最短线路问题 最短路问

5、题就是从某地出发，途经若干中间点最后到达目的地，要求找出路程或费用最小的路线。一般的最短路问题将在下一章讨论，这里只讨论分层的最短路问题。下面的管道设计问题(例5.1.1)就是其中之一。ED3D1D2C1C3C2AB3B2B1542634656122233234n从A点到E点要铺设一条天然气管道，n 中间必须经过三个中间站，n第一站可在B1、B2、B3中选择，n第二站可在C1、C2、C3中选择，n第三站可在D1、D2、D3中选择，n要求选择一条由A 到E的铺管路线，使总长度最短。n其中两点连线上的数字表示两点间管线的长度。ED3D1D2C1C3C2AB3B2B15426346561222332

6、34从A点到E点铺设管道，可以按其地理特点自然地分成四个阶段：（如下图所示）从A到B是第一阶段，从B到C是第二阶段，从C到D是第三阶段，从D到E是第四阶段，ABCDE阶段1阶段2阶段3阶段4ED3D1D2C1C3C2AB3B2B1542634656122233234在阶段2，从B3点出发，只有C1、C3两种可选择的点，如选C1,则C1就是阶段2在B3点的决策结果；C1点既是阶段2铺设管道的终点，又是阶段3铺设管道的起点；ED3D1D2C1C3C2AB3B2B1542634656122233234同样的理由，可以递推得其余阶段的铺设路线，如阶段3在C1点的决策是D1，阶段4在D1点的决策只有E点

7、；由于到E点是整个铺设管道的终点，至此，决策过程完成，铺设一条A点到E点的管道是由四个阶段的管道组成的，如A-B3-C1-D1-E，它也称为一个策略。ED3D1D2C1C3C2AB3B2B1542634656122233234 可以看出，各个阶段的决策不同，铺设的管道也不同，并且当某个阶段的 始点给定后，它直接影响着后面各阶段的行进路线和管道的长短，而后面各阶段的路线 的选取不受这点以前各阶段路线的影响。 因此，最短路线问题可简化为四个阶段决策问题，使由这四个阶段决策组成决策序列，也 称为策略所决定的一条路线的总长度最短。ED3D1D2C1C3C2AB3B2B15426346561222332

8、34第第12页页例例2 2 多阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为x的某种资源，将它投入两种的某种资源，将它投入两种生产方式生产方式A和和B中：以数量中：以数量y投入生产方式投入生产方式A，剩下的量投入生产方式剩下的量投入生产方式B，则可得到收入，则可得到收入g(y)+h(x-y)，其中，其中g(y)和和h(y)是已知函数，并且是已知函数，并且g(0)=h(0)=0；同时假设以；同时假设以y与与x-y分别投入两种分别投入两种生产方式生产方式A，B后可以回收再生产，回收率分后可以回收再生产，回收率分别为别为a与与b。试求进行。试求进行n个阶段后的最大总收入。个阶段后的最大总收

9、入。 第第13页页例例2 2 多阶段资源分配问题多阶段资源分配问题- -续续(1)(1) 若以若以y与与x-y分别投入生产方式分别投入生产方式A与与B，在第一，在第一阶段生产后回收的总资源为阶段生产后回收的总资源为x1=ay+b(x-y)，再将，再将x1投入生产方式投入生产方式A和和B，则可得到收入，则可得到收入g(y1)+h(x1-y1)，继续回收资源继续回收资源x2=ay1+b(x1-y1)， 若上面的过程进行若上面的过程进行n个阶段，我们希望选择个阶段，我们希望选择n个变量个变量y,y1,y2,yn-1，使这，使这n个阶段的总收入最大。个阶段的总收入最大。 第第14页页 因此，我们的问题

10、就变成：求因此，我们的问题就变成：求y,y1,y2,yn-1，以，以使使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 达到最大，且满足条件达到最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi与与xi均非负均非负,i=1,2, ,n-1 例例2 2 多阶段资源分配问题多阶段资源分配问题- -续续(2)(2)第第15页页例例3 3 生产和库存问题生产和库存问题 某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生

11、产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508第第16页页 假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足

12、夜班时，每一生产周期能生产的商品也是夜班时，每一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问

13、应该如何作生产和存储计划，才能使品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和存储费用最小？例例3 3 生产和生产和库存库存问题问题- -续续(1)(1)第第17页页 设第设第i个周期的生产量为个周期的生产量为xi，周期末的存储量为，周期末的存储量为ui，那，那么这个问题用式子写出来就是：求么这个问题用式子写出来就是：求x1,x2,x6，满足条件：，满足条件： x1=5+u1， x2+u1=5+u2， x3+u2=10+u3 x4+u3=30+u4 ， x5+u4=50+u5， x6+u5=8 0 xi 30, 0 uj, i=1,2,6; j=1,2, ,

14、5 使使S= = 为最小，其中为最小，其中例例3 3 生产和生产和库存库存问题问题- -续续(2)(2) tjjiiuxf16116)()1852345(16)(5432161xxxxxxfii3015,300120150 ,100)(iiiiixxxxxf第第18页页例4.机金矿问题 两个金矿两个金矿A,B分别有存储量分别有存储量x，y，现有一部开矿机，现有一部开矿机器，如果开采金矿器，如果开采金矿A，则以概率，则以概率p1得储量得储量x的的r1倍（倍（0 r11），并且机器没有损坏，可以继续再去开采金矿），并且机器没有损坏，可以继续再去开采金矿A或或B。同时又以概率。同时又以概率1- p1

15、宣告失败，机器报废，也宣告失败，机器报废，也得不到金子；如果把这部开矿机器用以开采金矿得不到金子；如果把这部开矿机器用以开采金矿B，则以概率则以概率p2得到储量得到储量y的的r2倍（倍（0r21），并且机器没），并且机器没有损坏，可以继续再去开采金矿有损坏，可以继续再去开采金矿A或或B，同时又以概，同时又以概率率1- p2宣告失败，机器报废，也得不到金子。宣告失败，机器报废，也得不到金子。 把机器用于开采金矿把机器用于开采金矿A或者或者B，如果机器没有损坏，如果机器没有损坏，将继续把机器用于开采金矿，将继续把机器用于开采金矿A或者或者B，直到机器损，直到机器损坏，问应该如何选择开矿的序列使获得

16、金子的期望值坏，问应该如何选择开矿的序列使获得金子的期望值最大。最大。第第19页页例例5 多阶段决策问题多阶段决策问题 有一个系统，可以分成若干个阶段，任意一有一个系统，可以分成若干个阶段，任意一个阶段个阶段k，系统的状态可以用，系统的状态可以用xk表示（可以是数量、表示（可以是数量、向量、集合等）。在每一阶段向量、集合等）。在每一阶段k的每一状态都有一的每一状态都有一个决策集合个决策集合Qk(xk)，在，在Qk(xk)中选定一个决策中选定一个决策qkQk(xk)，状态，状态xk就转移到新的状态就转移到新的状态xk+1=Tk(xk,qk)，并且得到效益并且得到效益Rk(xk,qk)。我们的目的

17、就是在每一。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。有阶段的总效益达到最大。 这样的多阶段决策问题称为这样的多阶段决策问题称为动态规划动态规划。第第20页页多阶段决策问题的基本要素：阶段数、状态变量、多阶段决策问题的基本要素：阶段数、状态变量、决策变量、状态转移方程和目标函数。决策变量、状态转移方程和目标函数。例例5 多阶段决策问题多阶段决策问题 多阶段决策问题的分类多阶段决策问题的分类阶段数：有限阶段决策问题和无限阶段决策问题；阶段数：有限阶段决策问题和无限阶段决策问题；状态变量：连续多阶段决策问题和离散

18、多有限阶段决状态变量：连续多阶段决策问题和离散多有限阶段决策问题；策问题；阶段个数是否明确：定期多阶段决策问题和不定期多阶段个数是否明确：定期多阶段决策问题和不定期多阶段决策问题；阶段决策问题；参数取值情况：确定多阶段决策问题和不确定多阶段参数取值情况：确定多阶段决策问题和不确定多阶段决策问题。决策问题。第第21页页5.35.3 最优化原理最优化原理动态规划最优化原理动态规划最优化原理：一个过程的最优策：一个过程的最优策略具有这样的性质，即无论其初始状态及略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而

19、言，个决策所形成的状态作为初始状态而言，必须构成最优策略。必须构成最优策略。动态规划的理论基础是最优性原理，它是贝尔动态规划的理论基础是最优性原理，它是贝尔曼于曼于2020世纪世纪5050年代依据一类多阶段决策问题提年代依据一类多阶段决策问题提出的。出的。第第22页页最优化原理的性质：最优化原理的性质：对于多阶段决策问题对于多阶段决策问题的最优策略，如果用它的前步策略产生的的最优策略，如果用它的前步策略产生的情况（加上原有的约束条件）来形成一个情况（加上原有的约束条件）来形成一个前步问题，那么所给最优策略的前阶段的前步问题，那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。策略构成这

20、前步问题的一个最优策略。 5.35.3 最优化原理最优化原理动态规划的最优化定理的数学表述 设一个 n 阶段决策问题，阶段变量 k=1，2，n ，初始状态 已知，则允许策略 是最优策略的充要条件是:对任意一个 k ，1kn 成立。 其中 ，opt是 max 或 min ，运算符 “ * ” 表示加法或乘法。1s),(*),(),(, 11, 1, 11, 1, 11, 1, 1, 1nkknkpkkpnnpsvoptpsvoptpsvnkk)(),(1, 1, 1, 1kkknkknsusppp 下面以下图所示的网络中确定AE最短路(例1)为例，来说明应用动态规划最优化定理解决问题的步骤。2E

21、D3D1D2C1C3C2AB3B2B154263465612233234 由最优化定理可知，一条 A-E 最短路的后部子路也是最短的。即如果找到一条 A-E 最短路 A-B3-C1-D1-E，则 C1-D1-E 也是一条连接 C1 与 E 的最短路。利用最短路的这一特性，寻找 A-E 最短路的方法，就是从最后一段，即 D-E 段开始，用由后向前逐步逆推的方法，求出各点到 E 的最短路线，最后求出从 A 点到 E 点的最短路。 当 k=4 时，取定一个状态 D1 ，从 D1 到 E 只有一条路线，故 ； 同理， , 。 2)(14Df3)(24Df4)(34Df332 , 21min)(),()

22、,(),(min)(2421141113DfDCdDfDCdCf 当 k=3 时，取定一个状态 C1 ，从 C1 出发，有 D1、D2 两种选择，所以 故相应的决策为 。这说明，从C1到终点 E 的最短路长是3，最短路线是 ：C1-D1-E 。 同理，从状态 C2 出发，有:相应决策为 ；113)(DCu442 , 22min)(),(),(),(min)(3432141223DfDCdDfDCdCf123)(DCu类似地可算出：当 k=2 时当 k=1 时，于是从 A 到 E 的最短路为 。 643 , 33min)(),(),(),(min)(3433242333DfDCdDfDCdCf2

23、1212)(, 7)(CBuBf12222)(, 7)(CBuBf13232)(, 8)(CBuBf10)(1Af 为了找出最短路，按计算的顺序反推之，可求出最优决策序列：因而得到相应的最短路 A-B3-C1-D1-E。 以上计算最短路的过程，可用以下图形标出：EDuDCuCBuBAu)(,)(,)(,)(1411313231543233222165436624ED3D1D2C1C3C2AB3B2B1410877634320 在上图中，每个节点上方的数表示从该点到 E 的最短路长。其中粗线表示一条 A-E 的最短路。这种在图上作业的方法称为标号法。它是先从 E 开始，逆着阶段顺序方向（状态行进

24、方向）进行的，因此，这种方法也称为逆序法。 一般地，给定一个 n 阶段决策问题，阶段变量为 k=1，2，n , 初始状态已知，状态变量为 ，决策变量为 ，决策指标记为 。则直观模型如下图所示：ks)(kksu),(kkkusv 因为初始状态已知，从上图中，状态转移方程为：它说明状态的行进方向是顺着 阶段的自然顺序的。利用最优化定理，该问题的寻优途径是先从最后一个阶段开始逆着状态行进方向进行，称为逆序法。11s1u1vn1nsnsnvnuk1kskskvku。2ss k+1 = u k(s k) (k=1,2,n) 设 表示从第 k阶段的状态 开始到第 n 阶段的终止状态 的过程，采取最优策略所

25、得到的指标函数值。综上分析得出 k 阶段与 k+1 阶段之间的递推关系：边界条件为 。 )(kksfks1ns) 1,.,1,()(*)(,()(11)(nnksfsusvoptsfkkkkkkssukkkkk0)(11nnsf 这种递推关系式称为动态规划逆序法的基本方程，简称基本方程。 通过求解基本方程可以得出问题的一个最优策略。 如果 n 阶段决策问题的终止状态 给定，如何确定它的基本方程呢？假设阶段变量 k 与状态变量 的定义不变。由于终止状态给定，从而决策变量应写为 ，从而状态转移方程为：1nsks)(1kksu)(1kkksus11s1u1vn1nsnsnvnuk1kskskvku。

26、2s 这说明状态的行进方向与阶段的自然顺序相反，因而寻优途径应从第1阶段的初始状态 s 1 开始，沿着与状态的行进方向相反方向，因而顺着阶段的自然顺序进行，称为顺序法。 这可看成处于第 k 阶段的终止状态 作出决策 而得到第 k-1 阶段的终止状态。因而，给问题的直观模型下图所示：1ksku 令 表示从第1阶段的起始状态到第 k 阶段的终止状态 的过程，最优策略的指标函数值。建立递推关系式为 (2)边界条件 其中 表示第 k 阶段的终止状态 的允许决策集合。称（2）式是动态规划顺序法的基本方程，简称基本方程。)(1kksf1ks),.,2 , 1()(*),()(11)(11nksfusvop

27、tsfkkkkksDukkkrkk0)(10sf)(1krksD第第37页页用最优化原理求解例用最优化原理求解例3：生产和库存问题生产和库存问题 如果一开始的存储量如果一开始的存储量u u0 0已经给定，要已经给定，要求最后一个周期结束时有存储量求最后一个周期结束时有存储量u un n，那么最，那么最优生产和存储费用就完全由优生产和存储费用就完全由u u0 0，u un n决定。对决定。对某一个周期某一个周期k k，如果这个周期开始时有库存，如果这个周期开始时有库存量量u uk-1k-1，要求结束时有库存量，要求结束时有库存量u uk k，那么它的，那么它的生产数量生产数量x xk k=s=s

28、k k+u+uk k-u-uk-1k-1，s sk k是这个周期的商是这个周期的商品需求量，所以它的生产和存储费为品需求量，所以它的生产和存储费为f(xf(xk k)+16 u)+16 uk-1k-1，其中，其中3015,300120150 ,100)(xxxxxf第第38页页 用用Fk(u0,uk)表示开始的存储量为表示开始的存储量为u0，第，第k个周期结束个周期结束时存储量为时存储量为uk的满足前的满足前k个周期需要的前个周期需要的前k个周期的最优个周期的最优生产和存储费用，由最优化原理生产和存储费用，由最优化原理 xk=sk+uk-uk-1, k=2,3,6 x1=s1+u1-u0, 让

29、让k=2,3,6，求出，求出F6(u0,u6)，就得到问题的解，就得到问题的解16)(),(min),(1101001kkkkukkuxfuuFuuFk0110116)(),(uxfuuF求解例求解例3：生产和库存问题生产和库存问题-续续 (1)第第39页页5.3 确定性的定期多阶段决策问题确定性的定期多阶段决策问题q旅行售货员问题旅行售货员问题 q多阶段资源分配问题多阶段资源分配问题q用最优化原理解某些非线性规划问题用最优化原理解某些非线性规划问题 q排序排序q最优排序法最优排序法第第40页页旅行售货员问题旅行售货员问题 旅行售货员问题是图论中一个著名问题，就是在网络旅行售货员问题是图论中一

30、个著名问题，就是在网络N N上找一条从上找一条从v v0 0点出发，经过点出发，经过v v1 1,v,v2 2,v,vn n各一次最后返回各一次最后返回v v0 0的最短路线和最短路程。现把它看成一个多阶段决策的最短路线和最短路程。现把它看成一个多阶段决策问题。从问题。从v v0 0出发，经过出发，经过n n个阶段，每个阶段的决策是选择个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用

31、（要再走，所以决策集合与以前选的决策有关。用（v vi i,V,V）表示状态，表示状态，v vi i是所处的点，是所处的点，V V是还没有经过的点集合。在是还没有经过的点集合。在状态（状态（v vi i,V,V）的决策集合中，取决策）的决策集合中，取决策v vj jV V，获得的效益是，获得的效益是v vi i到到v vj j的距离的距离d dijij，转入下一个状态（，转入下一个状态（v vj j,Vv,Vvj j ），现在），现在用最优化原理来找递推公式。用最优化原理来找递推公式。第第41页页旅行售货员问题旅行售货员问题-续续 (1) 用用f fk k(v(vi i,V),V)表示从表示从

32、v vi i点出发，经过点出发，经过V V中的点中的点各一次，最后回到各一次，最后回到v v0 0点的最短路程，点的最短路程，V V是一个是一个顶点集合，顶点集合，|V|=k|V|=k，d dijij是是v vi i到到v vj j的弧长，则的弧长，则001),(, 2 , 1),(min),(iijjkijVvikdvfnkvVvfdVvfj其余内容见书本第166页!第第42页页多阶段资源分配问题多阶段资源分配问题下面讨论有限资源分配问题，它的递推公式是：下面讨论有限资源分配问题，它的递推公式是： 一般情况下，一般情况下，g(y)，g(y)是很复杂的函数时，这个问题的是很复杂的函数时，这个问

33、题的解不容易找。当解不容易找。当g(y)，g(y)为凸函数，且为凸函数，且h(0)=g(0)=0时，可以证明在每个阶段上时，可以证明在每个阶段上y的最优决策总是取其端的最优决策总是取其端点的值。点的值。 )()(max)(2),()()(max)(0110yxhygxfkyxbayfyxhygxfxykxyk第第43页页多阶段资源分配问题多阶段资源分配问题-续续(1)引理引理5.2.1 设设g(x)，g(y)是凸函数，则对任何固定是凸函数，则对任何固定 的的x，F(y)=g(y)+h(x-y)是是y的凸函数。的凸函数。 引理引理5.2.2 设设F1(x),F2(X)是是x的凸函数，则的凸函数，

34、则 F(x)=max F1(x),F2(X) 也是也是x的凸函数。的凸函数。第第44页页多阶段资源分配问题多阶段资源分配问题-续续(2)定理定理5.2.1 设设g(y)g(y)，g(y)g(y)是凸函数，且是凸函数，且h(0)=g(0)=0h(0)=g(0)=0，则则n n阶段资源分配问题的最优策略阶段资源分配问题的最优策略y y在每个阶段在每个阶段总取总取0yx0yx的短点的值，并且的短点的值，并且)(),(max)()()(),()(max)(111xgxhxfaxfxgbxfxhxfkkk第第45页页5.4 确定性的不定期多阶段决策问题确定性的不定期多阶段决策问题 有的多阶段决策过程有的

35、多阶段决策过程, ,给定一个状态集合给定一个状态集合X XT T , ,当状态当状态x xX XT T时时, ,过程停止过程停止, ,这是阶段不确定的多阶这是阶段不确定的多阶段决策过程。如果经过有限阶段段决策过程。如果经过有限阶段, ,状态状态x x一定能进一定能进入入X XT T , ,就是阶段数有限的就是阶段数有限的, ,否则就是阶段数无限否则就是阶段数无限的的. .这类问题通常利用最优化原理得到一个函数这类问题通常利用最优化原理得到一个函数方程来求解方程来求解. . 主要有主要有: : 1: 1:最优线路问题最优线路问题. . 2: 2:有限资源分配问题有限资源分配问题. . 不作详细讲

36、述不作详细讲述. . 第第46页页用最优化原理解某些非线性规划问题用最优化原理解某些非线性规划问题 假设有数量假设有数量x0的物资可用于的物资可用于n种生产，若以种生产，若以xi投入第投入第i种生产时可得收益种生产时可得收益gi(xi)，问应如何选取，问应如何选取xi，使得，使得x0用用于于n种生产时得到的总收益最大。这个问题可以写成种生产时得到的总收益最大。这个问题可以写成数学规划问题：数学规划问题：nixxxxxtsxgxgxgFinnn, 2 , 1, 0. .)()()(max0212211第第47页页续续 (1) 假设每个假设每个gi(xi)在内连续，显然在内连续，显然F的极大值存的极大值存在，这是一个特殊类型的非线性规划问题，由在，这是一个特殊类型的非线性规划问题，由于这类问题的特殊结构，可以把它看成一个多于这类问题的特殊结构，可以把它看成一个多阶段决策问题，并利用动态规划的递推关系求阶段决策问题，并利用动态规划的递推关系求解。解。 把数量为把数量为x0的物资投入的物资投入n种生产方式，可以种生产方式，可以看成是看成是n阶段决策问题每阶段投入一定数量物