数学建模(动态规划).pdf

动态规划 教学内容： ?动态规划问题实例 ?动态规划的基本概念与原理?动态规划的基本概念与原理 ?动态规划应用举例 引 言 动态规划是解决多阶段决策过程最优化的一种方法。 该方法是由美国数学家贝尔曼（R. E. Bellman)等人在20世该方法是由美国数学家贝尔曼（ .e)等人在 0世 纪50年代初提出的。他们针对多阶段决策问题的特点，提出 了解决这类问题的“最优化原理”，并成功地解决了生产管 理、工程技术等方面的许多问题，从而建立了运筹学的一个 新的分支，即动态规划。 Bellman在1957年出版了Dynamic Programming一书， 是动态规划领域中的第一本著作。 动态规划问题及实例 动态规划是解决多阶段决策问题的一种方法，是现代企 业管理中的一种重要决策方法，可用于最优路径问题、资源 分配问题生产计划和库存问题投资问题装载问题排分配问题、生产计划和库存问题、投资问题、装载问题、排 序问题及生产过程的最优控制等。 动态规划模型的分类动态规划模型的分类： 以“时间”角度可分成：离散型和连续型。 从信息确定与否可分成：确定型和随机型。 从目标函数的个数可分成单目标型和多目标型从目标函数的个数可分成：单目标型和多目标型。 动态规划问题及实例动态规划问题及实例 一、多阶段决策过程 多阶段决策过程是指这样一类特殊的活动过程，他们可以 按时间顺序分解成若干相互联系的阶段，在每个阶段都要做 出决策，全部过程的决策是一个决策序列，所以多阶段决策 过程也称为序贯决策过程。这种问题就称为多阶段决策问题。 二、多阶段决策问题的特点 过程可分为若干个相互联系的阶段；每一阶段都对应过程可分为若干个相互联系的阶段；每阶段都对应 着一组可供选择的决策；每一决策的选定即依赖于当前 面临的状态，又影响以后总体的效果。 动态规划问题及实例 三具体实例三、具体实例 1、最短路线问题 给定一个线路网络，要从A向F铺设一条输油管道，各点间连 线上的数字表示距离问应选择什么路线可使总距离最短？线上的数字表示距离，问应选择什么路线，可使总距离最短？ 动态规划问题及实例 2生产与存储问题：2、生产与存储问题： 某工厂每月需供应市场一定数量的产品。供应需求所某厂每月需供应市场定数量的产品供应需求所 剩余产品应存入仓库，一般地说，某月适当增加产量可 降低生产成本但超产部分存入仓库会增加库存费用降低生产成本，但超产部分存入仓库会增加库存费用， 要确定一个每月的生产计划，在满足需求条件下，使一 年的生产与存储费用之和最小。 动态规划的基本概念与原理 动态规划的基本概念动态规划的基本概念 阶段；阶段； 状态；状态； 决策和策略；决策和策略； 状态转移方程；状态转移方程； 指标数指标数指标指标函函数数。 动态规划的基本概念与原理动态规划的基本概念与原理 一基本概念。基本概念 阶段：是指问题需要做出决策的步数。阶段总数常记为n，相 应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段 变量，k=1 2nk即可以是顺序编号也可以是逆序编号，变量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号， 常用顺序编号。 状态：各阶段开始时的客观条件，第k阶段的状态常用状态 变量表示，状态变量取值的集合成为状态集合，用 k s k S 变量表示，状态变量取值的集合成为状态集合，用 表示。 k k 例如案例1中BBSAS例如，案例1中，., 2121 BBSAS= 状状 状状 状状状 态 状 态 状 态 状 态 状 态 状 态 C1 2 5 B1 C2 D1 E1 4 2 3 6 8 4 5 3 5 6 4 A B2 C3 D2 D E2 F 5 8 7 3 4 8 6 2 1 3 B2 C4 D3 7 4 3 第1阶段第2阶段第3阶段第4阶段第5阶段 决策是指从某阶段的某个状态出发在若干个不同方案中决策：是指从某阶段的某个状态出发，在若干个不同方案中 做出的选择。表示决策的变量，称为决策变量，用表示。)( kk su 表示第k阶段当状态处于sk时的决策变量。 kk )( kk su 例如：表示走到C阶段,当处于C2 路口时，下一 步到D 123 )(DCu= 步到D1. 决策变量允许的取值范围称为允许决策集合，第k阶段状态为 时的允许决策集合记为，例如： )( kk sD,)( 32112 CCCBD= k s 策略：一个按顺序排列的决策组成的集合。由每段的决策 按顺序排列组成的决策函数序列 称为k子过程策略。简称子策略，记为。即 当k=1时，此决策函数序列成为全过程的一个策略，简称 策略记为策略，记为： 在实际问题中，可供选择的策略有一定的范围，此范围称 状态转移方程：是从上一阶段的某一状态值转变为下一阶段 为允许策略集合，用P表示。 某一状态值的转移规律，用 )(usTs= 表示 ),( 1kkkk usTs= +表示。 指标函数：分阶段指标函数和过程指标函数。阶段指标函数指标函数：分阶段指标函数和过程指标函数。阶段指标函数 是指第k阶段从状态出发，采取决策时的效益，用 k s k u ),( kkk usv 表示。而过程指标函数是从第k阶段的某状态出发， 采取子策略采取子策略 效益之和 时所得到的阶段 效益之和： 最优指标函数：表示从第k阶段状态为时采用最佳策略 k s 到过程终止时的最佳效益记为到过程终止时的最佳效益。记为 其中 opt 可根据具体情况取max 或min其中 opt 可根据具体情况取max 或min。 基本方程：此为逐段递推求和的依据，一般为： 1 () ( )opt ( ,( )( ),1,2,1 ()0 kkk kkkkkkkkk uDs f sv s u sfu skn n f + =+= ? 式中opt 可根据题意取 max 或 min. 11 ()0 nn fs + = p 例如，案例1的基本方程为： 1 () ()min (,()()5,4,3,2,1 kkk kkkkkkkkk uDs fsds usfusk + =+= 66 ()0fs = 最优性原理：最优策略的子策略必为最优不管过去的状态最优性原理：最优策略的子策略必为最优。不管过去的状态 和决策如何，从眼下直到最后的诸决策必构成最优子策略。 动态规划的优点： 可把一个N维优化问题化成N个一维优化问题求解。 函数方程中附加某些约束条件，可使求解更加容易。函数方程中附加某些约束条件，可使求解更加容易 求得最优解以后，可得所有子问题的最优解。 动态规划的缺点动态规划的缺点： “一个”问题，“一个”模型，“一个”求解方法。且 求解技巧要求比较高，没有统一处理方法。 动态规划动态规划应用举例应用举例动态规划动态规划应用举例应用举例 例最短路线问题例1 最短路线问题 基本思想如果起点 经过而到终点则由出基本思想：如果起点A经过B1,C1,D1,E1而到终点F，则由C1出 发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以， 寻找最短路线应该从最后一段开始找然后往前递推寻找最短路线，应该从最后段开始找，然后往前递推。 状态变量状态变量：各路线的位置各路线的位置s状态变量状态变量：各路线的位置各路线的位置 决策变量决策变量：第第k阶段当状态处于阶段当状态处于时时，决定下决定下一一个个 k s k s )( kk su 决策变量决策变量：第第k阶段当状态处于阶段当状态处于时时，决定下个决定下个 状态的位置状态的位置 状态转移方程状态转移方程上一阶段到下一阶段的转移规则上一阶段到下一阶段的转移规则 k kk )(su 状态转移方程状态转移方程：上一阶段到下一阶段的转移规则上一阶段到下一阶段的转移规则 指标函数指标函数：从状态出发从状态出发，采取决策时的路程距采取决策时的路程距 )( kk su 指标函数指标函数：从状态出发从状态出发，采取决策时的路程距采取决策时的路程距 离离 最优指标函数最优指标函数：第第k阶段状态阶段状态为为时时且采用最且采用最s最优指标函数最优指标函数：第第k阶段状态阶段状态为为时时且采用最且采用最 佳走线策略，使从佳走线策略，使从k位置及以后的路线最短。位置及以后的路线最短。 k s C1 2 5 8 A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 逆序递推方程： C4 37 4 3 1 () ()min (,()()5,4,3,2,1 ()0 kkk kkkkkkkkk uDs fsds usfusk fs + =+= = （1）k=5 时，状态 , 215 EES= 它们到F 点的距离即为 66 ()0fs= 最短路。 , 4)( 15 =Ef; 3)( 25 =Ef ,)( 1 * 5 FEu=.)( 2 * 5 FEu= C1 2 5 8 ,)( 1 * 5 FEu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 C4 37 4 3 （2）k=4 时，状态 , 3214 DDDS=它们到F 点需经过中途 点E，需一一分析从D 到 F的最短路：先说从D1到F 的最短路 有两种选择：经过 E1, E2, 比较最短。 C1 2 5 8 ,)( 1 * 5 FEu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 C4 37 4 3 )(),(),(),(min)( 252141511414 EfEDdEfEDdDf+= 73543i . 735 , 43min=+= 这说明由 D1到F 的最短距离为7，其路径为. 11 FED这说明由 D1 到F 的最短距离为7，其路径为 11 相应的决策为：.)( 11 * 4 EDu= C1 2 5 8 ,)( 1 * 5 FEu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= C4 37 4 3 .)( 114 EDu= )(),(),(),(min)( 252241512424 EfEDdEfEDdDf+= 53246min+. 532 , 46min=+= 这说明由 D2到F 的最短距离为5，其路径为. 22 FED这说明由 D2 到F 的最短距离为5，其路径为 22 相应的决策为：)( * EDu=相应的决策为：.)( 224 EDu= C1 2 5 8 ,)( 1 * 5 FEu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= )(),(),(),(min)( 252341513434 EfEDdEfEDdDf+= . 533, 41min=+= 即 D 到F 的最短距离为5其路径为FED即 D3 到F 的最短距离为5，其路径为. 13 FED 相应的决策为：.)( 13 * 4 EDu=相应的决策为)( 134 C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu= 7)(=Df A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= 7)( 14 =Df A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= 5)( 24 =Df C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= 5)( 24 Df 5)( 34 =Df （3）k=3 时，状态 , 43214 CCCCS = )()()()(min)(DfDCdDfDCdCf+)(),(),(),(min)( 242131411313 DfDCdDfDCdCf+= .1258, 75min=+=, 这说明由 C1 到F 的最短距离为12，相应的决策为 .)( 11 * 3 DCu= C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu= .)( 11 * 3 DCu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 113 DCu 7)( 14 =Df A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= 5)( 24 =Df C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= 5)( 34 =Df )(),(),(),(min)( 242231412323 DfDCdDfDCdCf+= .1055 , 74min=+=., 7 即由 C2 到F 的最短距离为10，相应的决策为.)( 22 * 3 DCu= )(),(),(),(min)( 343332423333 DfDCdDfDCdCf+= . 854 , 53min=+= C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu=.)( 11 * 3 DCu= * A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 22 * 3 DCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= 5)(=Df C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= 5)( 24 =Df 5)( 34 =Df 即由 C3 到F 的最短距离为8，相应的决策为.)( 23 * 3 DCu= )(),(),(),(min)( 343432424343 DfDCdDfDCdCf+= 95458min=+=. 954 , 58min=+= 即由 C4 到F 的最短距离为9，相应的决策为 .)( 34 * 3 DCu= C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu=.)( 11 * 3 DCu= * A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 22 * 3 DCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= .)( 23 * 3 DCu= C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= .)( 34 * 3 DCu= 12)( 13 =Cf10)( 23 =Cf8)( 33 =Cf （4）k=2时，状态 , 212 BBS= 3333 ),(),(),(),(min)( 232121311212 CfCBdCfCBdBf+= )(),( 33312 CfCBd+.1386 ,103 ,122min=+= 这说明由 B1 到F 的最短距离为13，相应的决策为.)( 21 * 2 CBu= C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu=.)( 11 * 3 DCu= * A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 22 * 3 DCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= .)( 23 * 3 DCu= C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= .)( 34 * 3 DCu= 9)(=Cf10)(=Cf8)(=Cf .)( 21 * 2 CBu= 9)( 43 =Cf10)( 23 =Cf8)( 33 =Cf ),(),(),(),(min)( 333222322222 CfCBdCfCBdBf+= )(),( 43422 CfCBd+.1597 , 87 ,108min=+= 即由 B2到F 的最短距离为15，相应的决策为.)( 32 * 2 CBu= C1 2 5 8 ,)( 1 * 5 FEu=.)( 13 * 4 EDu=.)( 11 * 3 DCu= * A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 22 * 3 DCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= .)( 23 * 3 DCu= C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= .)( 34 * 3 DCu= * .)( 21 * 2 CBu= 13)(=Bf15)(=Bf （1）k=1 时只有一个状态点A则 .)( 32 * 2 CBu= 13)( 12 =Bf15)( 22 =Bf （1）k=1 时，只有个状态点A, 则 )(),(),(),(min)( 222112111 BfBAdBfBAdAf+= .17155 ,134min=+= )( * BA 即由 A到F 的最短距离为17，相应的决策为 .)( 1 * 1 BAu= C1 2 5 8 ,)( 1 * 5 FEu=.)( 11 * 3 DCu= * A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 .)( 2 * 5 FEu= .)( 22 * 3 DCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 )( * EDu= .)( 23 * 3 DCu= C4 37 4 3 .)( 114 EDu= .)( 22 * 4 EDu= * .)( 34 * 3 DCu= .)( 32 * 2 CBu= .)( 21 * 2 CBu= .)( 13 * 4 EDu= )( 322 再按计算顺序反推可得最优决策序列： ,)( 21 * 2 CBu=,)( 22 * 3 DCu=,)( 1 * 1 BAu= ,)( 22 * 4 EDu=.)( 2 * 5 FEu= 所以最优路线为 FEDCBA 所以最优路线为： FEDCBA 2221 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 C1 2 5 8 B1 D1 E 4 3 6 8 4 3 5 A C2 D E1 F 4 6 5 5 6 4 A C D2 E2 F 5 8 7 32 3 B2 C3 D3 2 7 7 4 8 3 1 C4 3 4 8 顺序递推方程：顺序递推方程： 111 ()min(,)()1,2,3,4,5 k kkkkkkk u fsdsufsk + =+= 01 ( )0 k u fs = 边界条件 B1 C1 D1 2 3 5 8 4 3 例1： A 1 C2 C3 D2 E1 F 4 5 6 8 7 4 5 3 5 6 2 4 3 B2 C3 C4 D3 E2 7 7 4 8 4 3 1 3 1阶段2阶段3阶段4阶段5阶段 C1 2 5 8 A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 C4 37 4 3 k=1 时 111101 ()(, )( )f Bd B Afs=+ 121201 ()(, )( )f Bd BAfs=+ 注意到： 0)()( 010 =Afsf 所以ABu)( * 4)(=Bf5)(=BfABu=)( * 所以ABu=)( 11 , 4)( 11 =Bf, 5)( 21 =BfABu=)( 21 C1 2 5 8 ABu=)( 2 * 1 A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 ABu=)( 1 * 1 A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 k=2 时 C4 37 4 3 2121111 ()(,)()246f Cd C Bf B=+=+= 11 * 2 )(BCu= 222211122212 ()min(,)(),(,)()f Cd C Bf Bd C Bf B=+ 758 , 43min=+= 12 * 2 )(BCu= ()i ()()()()f Cd C Bf Bd C Bf B+ 232311123212 ()min(,)(),(,)()f Cd C Bf Bd C Bf B=+ C1 2 5 8 ABu=)( 2 * 1 AB )( * 6)( 12 =Cf A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 ABu=)( 11 11 * 2 )(BCu= 7)( 22 =Cf A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 12 * 2 )(BCu= * )(BC C4 37 4 3 105746i + 132 )(BCu= 2424212 ()(,)()7512,f Cd C Bf B=+=+ = 24 * 2 )(BCu= ,1057 , 46min=+= 2424212 ()(,)(),ff+ 242 )( k=3 时 31 ()fD k 3 时 31 3112121222 () min(,)(),(,)() f d D Cf CdD Cf C=+ 117465i +1174 , 65min=+= C1 2 5 8 ABu=)( 2 * 1 6)( 12 =Cf A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 ABu=)( 1 * 1 11 * 2 )(BCu= 7)( 22 =Cf A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 12 * 2 )(BCu= 10)( 32 =Cf C4 37 4 3 13 * 2 )(BCu= 24 * 2 )(BCu= 12)( 42 =Cf )( 32 f 242 )(BCu ,)( 11 * 3 CDu= 21 * 3 )(CDu=或 113213 )( 类似地，可算出： 12)( 23 =Df 22 * 3 )(CDu= * )(C14)( 33 =Df 33 * 3 )(CDu= C1 2 5 8 ABu=)( 2 * 1 * 22 * 3 )(CDu= 33 * 3 )(CDu= A B1 C2 D1 D E1 4 3 6 8 4 5 3 5 6 4 ABu=)( 1 * 1 11 * 2 )(BCu= A B2 C3 D2 D3 E2 F 5 8 7 7 3 4 8 2 3 1 3 112 12 * 2 )(BCu= C4 37 4 3 13 * 2 )(BCu= 24 * 2 )(BCu= ,)( 11 * 3 CDu=或 21 * 3 )(CDu= 14)( 14 =Ef 11 * 4 )(DEu= * 242 )( 12)(=Df 11)( 13 =Df 14)( 24 =Ef 22 * 4 )(DEu= 17)(Ff * )(EF 12)( 23 =Df 14)( 33 =Df 17)( 5 =Ff 25 )(EFu= 最优策略： 2 * 5 )(EFu= 22 * 4 )(DEu= 22 * 3 )(CDu= 12 * 2 )(BCu=ABu=)( 1 * 1 最短路径：FEDCBA最短路径：FEDCBA 2221 最短路长： 17)( 5 =Ff 最短路长： 17)( 5 Ff 注：顺序解法与逆序解法无本质区别，一般来说，当初始状 态给定时用逆序解法，当终止状态给定时用顺序解法。若问 题给定了个初始状态与个终止状态则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使 用。 例2资源分配问题（离散型）例2 资源分配问题（离散型） 例：例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利 润增长额同投资额的大小有关，见下表。问应如何确定对这 四个工厂的投资额使总利润增长额最大？四个工厂的投资额，使总利润增长额最大？ 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57 65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 解解：把对四个工厂的投资依次看成4个阶段的决策过程，解解：把对四个工厂的投资依次看成4个阶段的决策过程， 确定对第k个工厂的投资额看成第k个阶段的决策， k=1,2,3,4。图示如下： 投资x1投资x2投资x3投资x4 3 s 4 s 112 xss= 工厂1工厂2工厂3工厂4 600 1 =s 投资 1 投资 2 投资 3 投资 4 状态2 s 223 xss= 334 xss= 5 s 状态状态 )(xg)(xg)(xg )( 22 xg 状态变量：可用于第k, k+1,n个工厂的投资额。 k s )( 44 xg)( 33 xg)( 11 xg )( 22 g 决策变量：第 k 阶段对第 k 个工厂的投资额。 k x 允许决策集： k D ,100, 0 kk sD?= 状态转移方程： kkk xss=4321=k 其中 600=s 状态转移方程： , 1kkk xss= + . 4 , 3 , 2 , 1=k 其中 600 1 =s 阶段指标函数：第 k 阶段投资元时所产生的利)( kk xg k x 润。（见上表） 最优指标函数：第 k 阶段状态为且采取最佳投资 策略，从第 k 个工厂以及以后的最大总利润。 )( kk sf k s 策略从第个厂以及以后的最大利润 逆序法基本递推方程： =+= + 0)( 1 , 2 , 3 , 4)()(max)( 11 0 f ksfxgsf kkkk sx kk kk = 0)( 55 sf 投资x1投资x2投资x3投资x4 工厂1工厂2工厂3工厂4 600 1 =s 状态2 s 112 xss= 223 xss= 334 xss= 3 s 4 s 5 s 状态状态 )( 44 xg)( 33 xg)( 11 xg )( 22 xg )( 44 xg)( 33 xg)( 11 xg 投资额 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 40 28476574808540 28 47 65 74 80 85 解（1）k 4时解：（1）k=4时 考虑：若到最后一个第4个工厂投资时还有资金 4 s 考虑：若到最后个，第4个工厂投资时，还有资金， 若投资于第4个工厂的资金为，则最大利润为 4 s 4 x 投资x1投资x2投资x3投资x4 工厂1工厂2工厂3工厂4 600 1 =s 状态2 s 112 xss= 223 xss= 334 xss= 3 s 4 s 5 s 状态状态 )( 44 xg)( 33 xg)( 11 xg )( 22 xg )( 44 xg)( 33 xg)( 11 xg 投资额 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 40 28476574808540 28 47 65 74 80 85 )()(max)(sfxgsf+= （注意到此时0） )(sf)()(max)( 5544 0 44 44 sfxgsf sx += （注意到此时=0） )( 55 sf )(max 44 xg=)(max 44 0 44 xg sx = 投资x1投资x2投资x3投资x4 工厂1工厂2工厂3工厂4 600 1 =s 状态2 s 112 xss= 223 xss= 334 xss= 3 s 4 s 5 s 状态状态 )( 44 xg)( 33 xg)( 11 xg )( 22 xg )( 44 xg)( 33 xg)( 11 xg 投资额 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 40 28476574808540 28 47 65 74 80 85 自然问：现在还有多少钱？即=？ 4 s 0100200300400500600都有可能 s =0，100，200，300，400，500，600都有可能。 4 s 下面分情况讨论下面分情况讨论： 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 0 4 =s 时， )()(f)()( 40 28 47 65 74 80 85 )(max)( 44 0 44 44 xgsf sx =)(max 44 00 4 xg x =)(max 44 0 4 xg x = = 000 . 00max= 100 4 =s 时， 0 4 = x 4 时， )(max)( 44 0 44 44 xgsf sx =)(max 44 1000 4 xg x = )(max 44 100, 0 4 xg x = = 0 44 sx 1000 4 x .2828, 0max= 100 4 = x 其他种情况类似讨论，我们把所有的结果汇总成一个表2。 )(xg 表2 k=4 时决策表 4 x 4 s )( 44 xg )( 44 sf 4 x 0 100 200 300 400 500 600 0000 100 200 300 400 0 28 0 28 47 0 28 47 65 0 284765 74 28 47 65 74 100 200 300 400400 500 600 0 28 47 65 74 0 28 47 65 74 80 0 28 47 65 74 80 85 74 80 85 400 500 600 投资额 表1 利润增长额 )( ji xg （百元） (j) 工厂(i) 0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57 65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 （2）k=3时到第三个工厂投资时可利用的资金还有s 30 18 39 61 78 90 95 （2）k=3时到第三个工厂投资时，可利用的资金还有， 3 s 若向第三个工厂投资（万元），则自此即以后最大利润为： 3 x 若向第三个工厂投资（万元），则自此即以后最大利润为： 3 )()(max)( 4433 0 33 sfxgsf sx += 0 33 sx )()(max 33433 0 33 xsfxg sx += , 1kkk xss= + 同样问：=？，即现在还有多少钱？它是允许决策集上界。 3 s 600,500,400,300,200,100, 0 33 = Ss 同理 投资额 表1 利润增长额 )( ji xg （百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 30 183961789095 300 3 =s 仅举一例： 30 18 39 61 78 90 95 3 仅举例 )300()(max)300( 3433 3000 3 3 xfxgf x += 3 )300()(max 3433 300,200,100, 0 3 xfxg x += = )300300()300(),200300()200( ),100300()100(),0300()0(max 4343 4343 + += fgfg fgfg )()(),()( 4343 fgfg ),200()100(),300()0(max 4343 fgfg+= )0()300(),100()200( 4343 fgfg+ x )( 44 xg )(f 表2 k=4 时决策表 4 x 4 s )( 44 g )( 44 sf 4 x 0 100 200 300 400 500 600 0000 100 200 300 400 0 28 0 28 47 0 28 47 65 0 284765 74 28 47 65 74 100 200 300 400400 500 600 0 28 47 65 74 0 28 47 65 74 80 0 28 47 65 74 80 85 74 80 85 400 500 600 表1利润增长额)(xg（百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 表1 利润增长额)( ji xg（百元） )200()100()300()0()300(fff 工厂(i) 30 18 39 61 78 90 95 )0()300(),100()200( ),200()100(),300()0(max)300( 4343 43433 fgfg fgfgf + += 67061,2839,4718,650max=+=200 3 = x 有情结所有情况讨论结果汇总成下表： 表3 k=3 时决策表 3 x )()( 3343 xsfxg+ 表3 k=3 时决策表 3 s )()( 3343 3 fg )( 33 sf 3 x 0 100 200 300 400 500 600 00+0000 100 200 300 0+0 0+28 18+0 0+47 18+28 39+0 0+65 18+47 39+28 61+0 0 28 47 67 0 0 0 200 400 500 600 0+74 18+65 39+47 61+28 78+0 0+80 18+74 39+65 61+74 78+28 90+0 0+85 18+80 39+74 61+65 78+47 90+28 95+0 89 108 126 300 300 300 （3）k=2 时)()(max)(xsfxgsf+=（3）k=2 时)()(max)( 22322 0 22 22 xsfxgsf sx += 6005004003002001000= Ss600,500,400,300,200,100, 0 22 = Ss 仅举一例：600 2 =s )600()(max)600( 2322 6000 2 2 xfxgf x += 仅举例 2 )600()(max 2322 600,500,400,300,200,100, 0 2 xfxg x += = )300600()300()200600()200( ),100600()100(),0600()0(max 3232 + += fgfg fgfg )600600()600( )500600()500(),400600()400( ),300600()300(),200600()200( 3232 3232 + + f fgfg fgfg )600600()600( 32 + fg 投资额 表1 利润增长额)( ji xg（百元） 投资额 (j) 工厂(i) 0 100 200 300 400 500 600 20 25 45 57 65 70 73 ),500()100(),600()0(max)600( 32322 fgfgf+= )100()500(),200()400( ),300()300(),400()200( )()()()()( 3232 3232 32322 fgfg fgfg fgfgf + + )0()600( )100()500(),200()400( 32 3232 fg fgfg + + ),300(57),400(45 ),500(25),600(0max 33 33 ff ff + += )0(73 ),100(70),200(65 ),(),( 33 33 f ff ff + + )0(73 3 f+ x 表3 k=3 时决策表 3 x 3 s )()( 3343 3 xsfxg+ )( 33 sf 3 x 0 100 200 300 400 500 600 0 100 200 0+0 0+28 18+0 0+47 18+28 39+0 0 28 47 0 0 0 300 400 500 600 0+65 18+47 39+28 61+0 0+74 18+65 39+47 61+28 78+0 0+80 18+74 39+65 61+74 78+28 90+0 0+85 18+80 39+74 61+65 78+47 90+28 95+0 67 89 108 126 200 300 300 300 )300(57)400(45)500(25)600(0max)600(fffff+ 6000+85 18+80 39+74 61+65 78+47 90+28 95+0 126300 )0(73),100(70),200(65 ),300(57),400(45),500(25),600(0max)600( 333 33332 fff fffff + += 13489450732870 ,4765,6757,8945,10825,1260max =+=+ += .1348945073,2870+ 200 2 = x 关于的其它取值情况及相应的最优决策列于下表 s 关于的其它取值情况及相应的最优决策列于下表2 s 表4 k=2 时决策表 2 x 2 s )()( 22322 xsfxg+ )( 22 sf 2 x 0 100 200 300 400 500 600 2 s 0 100 0+0 0+28 25+0 0 28 0 0 200 300 400 0+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 53 73 92 100 200 100或或200 500 600 0+108 25+89 45+67 57+47 65+28 70+0 0+126 25+108 45+89 57+67 65+47 70+28 73+0 114 134 100 200 （4）k=1 时此时 600 1 =s （4）k=1 时 ，此时 ,600 1 s )()(max)600()( 11211 0 111 xsfxgfsf sx += 0 11 sx )600()(max 1211 xfxg+=)600()(max 1211 6000 1 xfxg x + )600()(max 1211 xfxg+=)600()(max 1211 600,500,400,300,200,100, 0 1 xfxg x + = )100600()100()0600()0(max+=f