最优化理论-动态规划讲解课件.ppt

1、动态规划v动态规划问题实例v动态规划的基本概念与原理v动态规划应用举例引 言动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R. E. Bellman)等人在20世纪50年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了Dynamic Programming一书，是动态规划领域中的第一本著作。1 动态规划问题实例例1 给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从A向F铺设一条输油管道，各点间连线上的数字表示

2、距离，问应选择什么路线，可使总距离最短？动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。2 动态规划的基本概念与原理一。基本概念阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变

3、量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号，常用顺序编号。状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量 表示，状态变量取值的集合成为状态集合，用表示。kskS例如，例1中，.,2121BBSASAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6决策：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为决策变量，用 表示)(kksu例如： 表示走到C阶段,当处于C2 路口时，下一步奔D1.123)(DCu 时的允许决策集

4、合记为 ，例如：ks)(kksD,)(32112CCCBD状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用 ),(1kkkkusTs表示。决策变量允许的取值范围称为允许决策集合，第k阶段状态为 v策略(Strategy) 由过程的第一阶段开始到最后一阶段为止称为问题的全过程，由各阶段的决策构成的策略序列称为全过程策略，记为P1n。111122( )( ),(),()nnnPsx sx sx sAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643k=1k=2k=3k=4k=5k=611123456(

5、)( ),( 2),( 3),(2),( 2),( 1)nPsx A x Bx Cx Dx Ex F策策略略状状态态指标函数：分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段从状态 出发，采取决策 时的效益，用ksku),(kkkusv表示。而过程指标函数从第k阶段的某状态出发，采取子策略,1nkkknuuup时所得到的阶段效益之和：nkjjjjknkknusvpsV),(),(最优指标函数：表示从第k阶段状态为 时采用最佳策略ks*knp到过程终止时的最佳效益。记为),(),()()(*knkknsDpknkknkkpsVoptpsVsfkknkn其中 opt 可根据具体情况取max

6、或min。基本方程：此为逐段递推求和的依据，一般为：0)(1 , 1,)(),()(1111)(nnkkkkksDukksfnnksfusvoptsfkkk式中opt 可根据题意取 max 或 min.例如，例1的基本方程为：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk动态规划最优化原理：动态规划最优化原理：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略。即即最优策略的任意后部子策略也是最优的。最优策略的任意后部子策略也是最优的。ABC11,11,()(,),()()knknkkknkkkk

7、nnxxkkkkkxxx sxsfsopt Fsopt dxxsfsI.将多阶段的决策过程划分为不同阶段，恰当地选取状态变量、决策变量并定义最优指标函数，正确写出基本的递推关系和恰当的边界条件。II.求解时从边界条件开始，逆过程进行方向逐段递推寻优，在对每一个子问题进行求解时，都要使用前面已求出的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解。III.动态规划方法每一阶段最优决策选取是从全局考虑的，与该阶段的最优决策一般是不同的。动态规划应用举例例1 最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143逆序递推方程：0)(1

8、 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk（1）k=5 时，状态,215EES它们到F 点的距离即为最短路。, 4)(15Ef; 3)(25Ef,)(1*5FEu.)(2*5FEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态,3214DDDS它们到F 点需经过中途点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路有两种选择：经过 E1, E2, 比较最短。.)

9、(2*5FEu,)(1*5FEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf. 735 , 43min这说明由 D1 到F 的最短距离为7，其路径为.11FED相应的决策为：.)(11*4EDu.)(2*5FEu,)(1*5FEu)(),(),(),(min)(252241512424EfEDdEfEDdDf. 532 , 46min这说明由 D2 到F 的最短距离为5，其路径为.22FED相应的决策为：.)(22*4EDuAB1B2C1C2C3C4D1D2D3E

10、1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf. 533, 41min即 D3 到F 的最短距离为5，其路径为.22FED相应的决策为：.)(13*4EDu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu（3）k=3 时，状态)(),(),(),(min)(242131411313DfDCdDfDCdCf.1258, 75min

11、这说明由 C1 到F 的最短距离为12，相应的决策为.)(11*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu,43213CCCCS AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf.1055 , 74min即由 C2 到F 的最短距离为10，相应的决策为.)(22*3DCu)(),(),(),(min)(34333

12、2423333DfDCdDfDCdCf. 854 , 53min.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu即由 C3 到F 的最短距离为8，相应的决策为.)(23*3DCu)(),(),(),(min)(343432424343DfDCdDfDCdCf. 954 , 58min即由 C4 到F 的最短距离为9，相应的决策为.)(34*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13

13、*4EDu.)(11*3DCu.)(22*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态,212BBS)(),(),(),(),(),(min)(33312232121311212CfCBdCfCBdCfCBdBf.1386 ,103 ,122min这说明由 B1 到F 的最短距离为13，相应的决策为.)(21*2CBu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu)(),(),(),()

14、,(),(min)(43422333222322222CfCBdCfCBdCfCBdBf.1597 , 87 ,108min即由 B2到F 的最短距离为15，相应的决策为.)(32*2CBuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(21*2CBuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1 时，只有

15、一个状态点A, 则)(),(),(),(min)(222112111BfBAdBfBAdAf.17155 ,134min即由 A到F 的最短距离为17，相应的决策为.)(1*1BAu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu,)(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu所以最优路线为：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562

16、3143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按计算顺序反推可得最优决策序列：,)(1*1BAu.)(1*1BAu顺序递推方程：初始条件0)(5 , 4 , 3 , 2 , 1)(),(min)(10111sfksfusdsfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1阶段2阶段3阶段4阶段5阶段行走方向AB1B2C1C2C3C4D1D2D

17、3E1E2F452368775845348435623143K=1 时)(),()()(10111121sfABdBfsf注意到：0)()(010Afsf所以ABu)(1*1)(),()()(10212121sfABdBfsf, 4)(11Bf, 5)(21BfABu)(2*1K=2 时642)(),()()(111121232BfBCdCfsf11*2)(BCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfsf758 , 4

18、3min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfsf13*2)(BCu,1257)(),()()(212424232BfBCdCfsf24*2)(BCuK=3 时)(),(),(),(min)()(22212121131343CfCDdCfCDdDfsf1174 , 65minAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1,1057 , 46min11*2)(BCu12*2)(BCu6)(12Cf7)(22CfAB1B2C1C2C3C4D1D2D3

19、E1E2F452368775845348435623143ABu)(2*1ABu)(1*112*2)(BCu11*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu21*3)(CDu或类似地，可算出：12)(23Df22*3)(CDu14)(33Df33*3)(CDu6)(12Cf7)(22Cf12)(42Cf10)(32Cf14)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)(5Ff2*5)(EFu最优策略：2*5)(EFu22*4)(DEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1

20、ABu)(1*111*2)(BCu12*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu或21*3)(CDu22*3)(CDu33*3)(CDu12)(23Df14)(33Df11)(13Df22*3)(CDu12*2)(BCuABu)(1*1最短路径：FEDCBA2221最短路长：17)(5Ff注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。1.分析问题。识别问题的多阶段特征，按照时间或者空间的先后顺序将过程适当地分为满足递推关系的若干阶段，对非时序的静态问题需

21、要人为地赋予“时段”的概念；2.正确选择具有以下两个特征的状态变量状态变量及其取值范围 (1)可知性。过程演变的各阶段状态变量取值能直接或者间接地被确定。 (2)能确切描述过程的演变，且满足无后效性3.确定决策变量及其取值范围4.根据状态变量和决策变量的含义，正确写出状态转移方程sk+1 =T(sk, xk) 5.根据问题，明确指标函数Fkn，最优指标函数fk(sk) 及k阶段指标dk(sk,xk) 的含义，并正确列出最优指标函数的递推关系及边界条件6.检查所建立的动态规划模型是否正确表达了原问题的要求和各种限制条件例2 资源分配问题（离散型） 例：例：设有6百万元资金用于4个工厂的扩建，已知

22、每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？ 投资额 (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 利润增长额 )(jixg（百元）解解：把对四个工厂的投资依次看成4个阶段的决策过程， 确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s112xs

23、s223xss334xss3s4s5s状态状态状态变量 ：可用于第k, k+1,n个工厂的投资额。ks决策变量 ：第 k 阶段对第 k 个工厂的投资额。kx允许决策集 ：kD,100, 0kksD)(44xg)(33xg)(11xg)(22xg状态转移方程：,1kkkxss. 4 , 3 , 2 , 1k其中6001s阶段指标函数 ：第 k 阶段投资 元时所产生的利润。（见上表）)(kkxgkx最优指标函数 ：第 k 阶段状态为 且采取最佳投资策略，从第 k 个工厂以及以后的最大总利润。)(kksfks 逆序法基本递推方程： 0)(1 , 2 , 3 , 4)()(max)(5510sfksf

24、xgsfkkkksxkkkk工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s112xss223xss334xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg 投资额 (j)工厂(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）解：（1）k=4时考虑：若到最后一个，第4个工厂投资时，还有资金 ，若投资于第4个工厂的资金为 ，则最大利润为4s4x工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s112xss223xss334xss3s4s

25、5s状态状态)(44xg)(33xg)(11xg)(22xg 投资额 (j)工厂(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）)()(max)(554404444sfxgsfsx（注意到此时 =0） )(55sf)(max44044xgsx 自然问：现在还有多少钱？即 =？ 4s =0，100，200，300，400，500，600都有可能。 4s下面分情况讨论：工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s112xss223xss334xss3s4s5s状态状态)(44xg

26、)(33xg)(11xg)(22xg 投资额 (j)工厂(i)0 100 200 300 400 500 600 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）04s时，)(max)(4404444xgsfsx )(max44004xgx )(max4404xgx . 00max1004s时，)(max)(4404444xgsfsx )(max4410004xgx )(max44100, 04xgx .2828, 0max其他种情况类似讨论，我们把所有的结果汇总成一个表2。04x1004x 投资额 (j)工厂(i)0 100 200 300 400 500 6

27、00 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 500 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100200300400500600 表2 k=4 时决策表 投资额 (j)工厂(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 20 25 45 57

28、65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）（2）k=3时 到第三个工厂投资时，可利用的资金还有 ， 3s若向第三个工厂投资 （万元），则自此即以后最大利润为：3x)()(max)(443303333sfxgsfsx)()(max33433033xsfxgsx 表1 利润增长额 )(jixg（百元）,1kkkxss 投资额 (j)工厂(i)0 100 200 300 400 500 600 30 18 39 61 78 90 95同样问： =？，即现在还有多少钱？它是允许决策集上界。3s600,50

29、0,400,300,200,100, 033 Ss同理3003s仅举一例：)300()(max)300(3433300033xfxgfx)300()(max3433300,200,100, 03xfxgx)300300()300(),200300()200(),100300()100(),0300()0(max43434343fgfgfgfg)0()300(),100()200(),200()100(),300()0(max43434343fgfgfgfg 投资额 (j)工厂(i)0 100 200 300 400 500 600 30 18 39 61 78 90 95 表1 利润增长额 )

30、(jixg（百元）4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 500 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100200300400500600 表2 k=4 时决策表)0()300(),100()200(),200()100(),300()0(max)300(434343433fgfgfgfgf67061,2839,4718,650max2003x 投资额 (j)工厂(i)0

31、 100 200 300 400 500 600 30 18 39 61 78 90 95 表1 利润增长额 )(jixg（百元）所有情况讨论结果汇总成下表： 3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 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+00+85 18+80 39+74 61+65 78+47 90+

32、28 95+0 028476789108126000200300300300 表3 k=3 时决策表)600()(max)600(2322600022xfxgfx)600()(max2322600,500,400,300,200,100, 02xfxgx)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(max32323232323232fgfgfgfgfgfgfg（3）k=2 时 )()(max)(2232202222xsfxgsfsx600,500,400,3

33、00,200,100, 022 Ss仅举一例：6002s 投资额 (j)工厂(i)0 100 200 300 400 500 600 20 25 45 57 65 70 73 表1 利润增长额 )(jixg（百元）)0()600()100()500(),200()400(),300()300(),400()200(),500()100(),600()0(max)600(323232323232322fgfgfgfgfgfgfgf)0(73),100(70),200(65),300(57),400(45),500(25),600(0max3333333fffffff)0(73),100(70),

34、200(65),300(57),400(45),500(25),600(0max)600(33333332ffffffff3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 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+00+85 18+80 39+74 61+65 78+47 90+28 95+0 02847678910

35、8126000200300300300 表3 k=3 时决策表.1348945073,2870,4765,6757,8945,10825,1260max2002x关于 的其它取值情况及相应的最优决策列于下表2s2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126

36、25+108 45+89 57+67 65+47 70+28 73+0 02853739211413400100200100或或200100200 表4 k=2 时决策表（4）k=1 时 ，此时,6001s)()(max)600()(11211011111xsfxgfsfsx)600()(max121160001xfxgx)600()(max1211600,500,400,300,200,100, 01xfxgx)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(

37、max21212121212121fgfgfgfgfgfgfg 投资额 (j)工厂(i)0 100 200 300 400 500 600 10 20 42 60 75 85 90 表1 利润增长额 )(jixg（百元）)600600(90)500600(85),400600(75),300600(60),200600(42),100600(20),0600(0max2222222fffffff)600600()600()500600()500(),400600()400(),300600()300(),200600()200(),100600()100(),0600()0(max)600(2

38、12121212121211fgfgfgfgfgfgfgf2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126 25+108 45+89 57+67 65+47 70+28 73+0 02853739211413400100200100或或200100200 表4

39、 k=2 时决策表)600600(90),500600(85),400600(75),300600(60),200600(42),100600(20),0600(0max)600(22222221ffffffff.13490,113,128,133,134,134,134max090,2885,5375,7360,9242,11420,1340max汇一表格：1x1s)()(11211xsfxg)(11sf1x0 100 200 300 400 500 600 600134 134 134 133 138 113 90 1340或或100或或200 表5 k=1 时决策表此时对应最大值134

40、的有三个值： 200,100, 01x所对应的最优策略分别为： 01x时，由状态转移方程112xss知：6000600112xss所对应的?2x2x2s)()(22322xsfxg)(22sf2x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 25+00+47 25+28 45+0 0+67 25+47 45+28 57+0 0+89 25+67 45+47 57+28 65+0 0+108 25+89 45+67 57+47 65+28 70+00+126 25+108 45+89 57+67 65+47 70+28 73

41、+0 02853739211413400100200100或或200100200 表4 k=2 时决策表 对应的 2002x 再由状态转移方程400200600223xss 对应的 ?3x3x3s)()(33433xsfxg)(33sf3x0 100 200 300 400 500 600 0 100 200 300 400 500 6000+00+28 18+00+47 18+28 39+0 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+00+85 18+80 39+74 6

42、1+65 78+47 90+28 95+0 028476789108126000200300300300 表3 k=3 时决策表 所对应的 3003x 再由状态转移方程100300400334xss 对应的 ?4x4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 500 60000 280 28 470 28 47 65 0 28 47 65 74 0 28 47 65 74 800 28 47 65 74 80 8502847657480850100200300400500600 表2 k=4 时决策表 对应的 100

43、4x从而得一最优策略, 01x,2002x,3003x1004x同理还有另外三个最优策略:,2001x,1002x,2003x1004x,1001x,1002x,3003x1004x,2001x,2002x, 03x2004x所有解总利润最大增长额为134)(11sf（百元）加上刚才一组,2002x,3003x1004x, 01x资源分配问题资源分配问题（连续型）：设备负荷分配问题设备负荷分配问题。例例（何坚勇/P-256）某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情

44、况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？解：这是一个以时间为特征的多阶段决策问题。第1年第2年第3年第4年5001s投 x1辆 超负荷车状态2s1122 . 09 . 0 xss2232 . 09 . 0 xss3342 . 09 . 0 xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg投 x2辆 超负荷车投 x3辆 超负荷车投 x4辆 超负荷车第5年投 x4辆 超负荷车)(55xg状态状态6s4452 . 09 . 0 xss阶段：将5年运输计划看成5

45、个阶段的决策问题。k=1,2,3,4,5状态变量 ：第k阶段初完好卡车数量 ，其中ks.5001s决策变量 ：表示第k 阶段分配给超负荷运输的卡车数量。kx 显然，分配给低负荷的卡车数为 kkxs )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 0注：注：这里视 ， 为连续变量。若 =0.6表示有一辆卡车在第k年度有60的时间处于完好状态。 =0.7表示有一辆卡车在第k年度有70时间在超负荷运输等等。 kskxkskx状态转移方程： )(1 . 01 ()3 . 01 (1kkkkxsxskkxs2 . 09 . 05 , 4 , 3 , 2 , 1k 阶段指

46、标函数 ：表示第 k 年度利润。)(kkxg5 , 4 , 3 , 2 , 1k)(1625)(kkkkkxsxxgkkxs9165 , 4 , 3 , 2 , 1k最优指标函数 ：第 k 年度初完好车辆数为 时，采用最优策略到第 5 年末所产生的最大利润。 )(kksfks逆序递推式为： 0)(1 , 2 , 3 , 4 , 5)()(max)(66110sfksfxgsfkkkksxkkkk1） k=5时)()(max)(665505555sfxgsfsx（注意到此时 =0） )(66sf)(max55055xgsx 916max55055xssx916max)(5505555xssfsx

47、5f5x5s516so55525916sss5*5sx 此时2） k=4 时)()(max)(554404444sfxgsfsx25916max544044sxssx)2 . 09 . 0(25916max4444044xsxssx45 .38max44044xssx同理，只有当44sx 时，函数4445 .38xs 才能达到极大值。故有4*4sx 4445 .42)(ssf3） k=3 时)()(max)(443303333sfxgsfsx5 .42916max433033sxssx)2 . 09 . 0(5 .42916max3333033xsxssx5 . 025.54max33033x

48、ssx不难得到3*3sx 33375.54)(ssf4） k=2 时)()(max)(332202222sfxgsfsx)2 . 09 . 0(75.54916max2222022xsxssx95. 1275.65max22022xssx2f2x247.33s2275.65so可见，只有当02x时，函数2295. 1275.65xs 才能达到极大值。故有, 0*2x222275.65)(ssf33375.54)(ssf5） k=1 时)()(max)500()(2211011111sfxgfsfsx275.65916max21150001sxsx)2 . 09 . 0(275.65916max

49、111150001xsxsx055. 47475.74max1150001xsx同理，只有当时，函数, 0*1x75.373735007475.747475.74)(111ssf01x11055. 47475.74xs 才能达到极大值。故有（万元）所对应的最优策略分别为： 01x时，由状态转移方程kkkxss2 . 09 . 014505009 . 02 . 09 . 0112xss由, 0*2x且4054509 . 02 . 09 . 0223xss再由3*3sx 且5 .2834052 . 04059 . 02 . 09 . 0334xss4*4sx 45.1985 .2832 . 05

50、.2839 . 02 . 09 . 0445xss5*5sx 15.13845.1982 . 045.1989 . 02 . 09 . 0556xss第一年初：500辆车全部用于低负荷运输。第二年初：还有450辆完好的车，也全部用于低负荷运输。第三年初：还有405辆完好的车，全部用于超负荷运输。第四年初：还有238.5辆完好的车，全部用于超负荷运输。第五年初：还有198.45辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。实现最大利润74. 3)(11sf（亿元）背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限