数学建模动态规划PPT课件

1、动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R. E. Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了Dynamic Programming一书，是动态规划领域中的第一本著作。第1页/共69页 动态规划问题及实动态规划问题及实例例动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问

2、题、排序问题及生产过程的最优控制等。动态规划模型的分类：以“时间”角度可分成：离散型和连续型。从信息确定与否可分成：确定型和随机型。从目标函数的个数可分成：单目标型和多目标型。第2页/共69页一、多阶段决策过程 多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。 二、多阶段决策问题的特点 过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。第3页/共69页三、具体

3、实例 1、最短路线问题给定一个线路网络，要从A向F铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？第4页/共69页2、生产与存储问题：某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。第5页/共69页 动态规划的基本概念与原理动态规划的基本概念与原理动态规划的基本概念阶段；状态；决策和策略；状态转移方程；指标函数。第6页/共69页一、基本概念阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应

4、的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号，常用顺序编号。状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量 表示，状态变量取值的集合成为状态集合，用表示。kskS例如，案例1中，.,2121BBSAS第7页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第8页/共69页决策：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为决策变量，用 表示。 表示第k阶

5、段当状态处于sk时的决策变量。)(kksu例如： 表示走到C阶段,当处于C2 路口时，下一步奔D1.123)(DCu 时的允许决策集合记为 ，例如：)(kksD,)(32112CCCBD决策变量允许的取值范围称为允许决策集合，第k阶段状态为 )(kksuks第9页/共69页状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用 ),(1kkkkusTs表示。策略：一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列 称为k子过程策略。简称子策略，记为 。即当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为：在实际问题中，可供选择的策略有一定

6、的范围，此范围称为允许策略集合，用P表示。第10页/共69页指标函数：阶段指标函数和过程指标函数。阶段指标函数是指第k阶段从状态 出发，采取决策 时的效益，用ksku),(kkkusv表示。而过程指标函数是从第k阶段的某状态出发，采取子策略效益之和：最优指标函数：表示从第k阶段状态为 时采用最佳策略ks到过程终止时的最佳效益。记为时所得到的阶段第11页/共69页其中 opt 可根据具体情况取max 或min。基本方程：此为逐段递推求和的依据，一般为：式中opt 可根据题意取 max 或 min.例如，案例1的基本方程为：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfk

7、sfusdsfkkkkkukkk第12页/共69页最优性原理：最优策略的子策略必为最优。不管过去的状态和决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。求得最优解以后，可得所有子问题的最优解。动态规划的缺点：“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。状态变量维数不能太高，一般要求小于6。第13页/共69页动态规划应用举例例1 最短路线问题基本思想：如果起点A经过B1,C1,D1,E1而到终点F，则由C1出发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以，寻找最短路线，应该从最

8、后一段开始找，然后往前递推。第14页/共69页状态变量 ：各路线的位置决策变量 ：第k阶段当状态处于 时，决定下一个状态的位置状态转移方程 ：上一阶段到下一阶段的转移规则指标函数 ：从状态出发，采取决策时的路程距离最优指标函数 ：第k阶段状态为时且采用最佳走线策略，使从k位置及以后的路线最短。ksks)(kksu)(kksu第15页/共69页逆序递推方程：0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkukkk（1）k=5 时，状态,215EES它们到F 点的距离即为最短路。, 4)(15Ef; 3)(25Ef,)(1*5FEu.)(2*5FE

9、uAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第16页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态,3214DDDS它们到F 点需经过中途点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路有两种选择：经过 E1, E2, 比较最短。.)(2*5FEu,)(1*5FEu第17页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEf

10、EDdDf. 735 , 43min这说明由 D1 到F 的最短距离为7，其路径为.11FED相应的决策为：.)(11*4EDu.)(2*5FEu,)(1*5FEu第18页/共69页)(),(),(),(min)(252241512424EfEDdEfEDdDf. 532 , 46min这说明由 D2 到F 的最短距离为5，其路径为.22FED相应的决策为：.)(22*4EDuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu第19页/共69页AB1B2C1C2C3C4D1D2D3E1E2F4

11、52368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf. 533, 41min即 D3 到F 的最短距离为5，其路径为.13FED相应的决策为：.)(13*4EDu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu第20页/共69页（3）k=3 时，状态,43214CCCCS )(),(),(),(min)(242131411313DfDCdDfDCdCf.1258, 75min这说明由 C1 到F 的最短距离为12，相应的决策为.)(11*3DCuAB1B2C1C2C3C4D1D2D3E1E2F

12、452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14Df5)(34Df第21页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf.1055 , 74min即由 C2 到F 的最短距离为10，相应的决策为.)(22*3DCu)(),(),(),(min)(343332423333DfDCdDfDCdCf. 854 , 53min.)(2*5FEu,

13、)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu7)(14Df5)(24Df5)(34Df第22页/共69页即由 C3 到F 的最短距离为8，相应的决策为.)(23*3DCu)(),(),(),(min)(343432424343DfDCdDfDCdCf. 954 , 58min即由 C4 到F 的最短距离为9，相应的决策为.)(34*3DCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3

14、DCu.)(22*3DCu5)(24Df5)(34Df第23页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（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*3DCu1

15、2)(13Cf10)(23Cf8)(33Cf第24页/共69页)(),(),(),(),(),(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*2CBu9)(43Cf10)(23Cf8

16、)(33Cf第25页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1 时，只有一个状态点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*2CBu13)(12Bf15)(22Bf第26页/共69页,)

17、(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu所以最优路线为：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按计算顺序反推可得最优决策序列：,)(1*1BAu第27页/共69页顺序递推方程：初始条件0)(5 , 4 , 3 , 2 , 1)(),(min)(10111sfksfusd

18、sfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1阶段2阶段3阶段4阶段5阶段行走方向第28页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时)(),()()(10111121sfABdBfsf注意到：0)()(010Afsf所以ABu)(1*1)(),()()(10212121sfABdBfsf, 4)(11Bf, 5)(21BfABu)(2*1第29页/共69页K=2 时642)(),()()(111121232BfBCdCfsf11*2)(BCu

19、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfsf758 , 43min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfsf第30页/共69页13*2)(BCu,1257)(),()()(212424232BfBCdCfsf24*2)(BCuK=3 时)(),(),(),(min)()(22212121131343CfCDdCfCDdDfsf1174 , 65minAB

20、1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1,1057 , 46min11*2)(BCu12*2)(BCu6)(12Cf7)(22Cf第31页/共69页AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(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)(42Cf

21、10)(32Cf第32页/共69页14)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)(5Ff2*5)(EFu最优策略：2*5)(EFu22*4)(DEuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*111*2)(BCu12*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu或21*3)(CDu22*3)(CDu33*3)(CDu12)(23Df14)(33Df11)(13Df第33页/共69页22*3)(CDu12*2)(BCuABu)(1*1最短路径：FEDCBA2221

22、最短路长：17)(5Ff注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。第34页/共69页例2 资源分配问题（离散型） 例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？ 投资额 (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 6

23、5 74 80 85 表1 利润增长额 )(jixg（百元）第35页/共69页解：把对四个工厂的投资依次看成4个阶段的决策过程， 确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：状态变量 ：可用于第k, k+1,n个工厂的投资额。ks决策变量 ：第 k 阶段对第 k 个工厂的投资额。kx允许决策集 ：kD,100, 0kksD3s4s112xss工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s223xss334xss5s状态状态)(44xg)(33xg)(11xg)(22xg第36页/共69页状态转移方程：,1kkkxss. 4 , 3 ,

24、 2 , 1k其中6001s阶段指标函数 ：第 k 阶段投资 元时所产生的利润。（见上表）)(kkxgkx最优指标函数 ：第 k 阶段状态为 且采取最佳投资策略，从第 k 个工厂以及以后的最大总利润。)(kksfks 逆序法基本递推方程： 0)(1 , 2 , 3 , 4)()(max)(55110sfksfxgsfkkkksxkkkk第37页/共69页工厂1工厂2工厂3工厂46001s投资x1投资x2投资x3投资x4状态2s112xss223xss334xss3s4s5s状态状态)(44xg)(33xg)(11xg)(22xg 投资额 (j)工厂(i)0 100 200 300 400 50

25、0 600 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）解：（1）k=4时考虑：若到最后一个，第4个工厂投资时，还有资金 ，若投资于第4个工厂的资金为 ，则最大利润为4s4x第38页/共69页工厂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（百元）)()(max)(554404444

26、sfxgsfsx（注意到此时 =0） )(55sf)(max44044xgsx 第39页/共69页自然问：现在还有多少钱？即 =？ 4s =0，100，200，300，400，500，600都有可能。 4s下面分情况讨论：工厂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（百元）第40页/共69页04s时，)(max)(

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

28、 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 65 70 73 30 18 39 61 78 90 95 40 28 47 65 74 80 85 表1 利润增长额 )(jixg（百元）第42页/共69页（2）k=3时 到第三个工厂投资时，可利用

29、的资金还有 ， 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,500,400,300,200,100, 033 Ss同理第43页/共69页3003s仅举一例：)300()(max)300(3433300033xfxgfx)300()(max3433

30、300,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 利润增长额 )(jixg（百元）第44页/共69页4x4s)(44xg)(44sf4x0 100 200 300 400 500 600 0 100 200 300 400 50

31、0 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 100 200 300 400 500 600 30 18 39 61 78 90 95 表1 利润增长额 )(jixg（百元）第45页/共69

32、页所有情况讨论结果汇总成下表： 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+28 95+0 028476789108126000200300300300 表3 k=3 时决策表第46页/共69页)600(

33、)(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,300,200,100, 022 Ss仅举一例：6002s第47页/共69页 投资额 (j)工厂(i)0 100

34、 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第48页/共69页)0(73),100(70),200(65),300(57),400(45),500(25),600(0

35、max)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 028476789108126000200300300300 表3 k=3 时决策表.13489

36、45073,2870,4765,6757,8945,10825,1260max2002x第49页/共69页关于 的其它取值情况及相应的最优决策列于下表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 25+108 45+89 57+67 65+47 70+

37、28 73+0 02853739211413400100200100或或200100200 表4 k=2 时决策表第50页/共69页（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(max21212121212121fg

38、fgfgfgfgfgfg第51页/共69页 投资额 (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(21212121212

39、1211fgfgfgfgfgfgfgf第52页/共69页2x2s)()(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

40、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第53页/共69页汇一表格：1x1s)()(11211xsfxg)(11sf1x0 100 200 300 400 500 600 600134 134 134 133 138 113 90 1340或或100或或200 表5 k=1 时决策表此时对

41、应最大值134 的有三个值： 200,100, 01x所对应的最优策略分别为： 01x时，由状态转移方程112xss知：6000600112xss所对应的?2x第54页/共69页2x2s)()(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+

42、67 65+47 70+28 73+0 02853739211413400100200100或或200100200 表4 k=2 时决策表 对应的 2002x 再由状态转移方程400200600223xss 对应的 ?3x第55页/共69页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

43、+28 90+00+85 18+80 39+74 61+65 78+47 90+28 95+0 028476789108126000200300300300 表3 k=3 时决策表 所对应的 3003x 再由状态转移方程100300400334xss 对应的 ?4x第56页/共69页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 8502847657480850100

44、200300400500600 表2 k=4 时决策表 对应的 1004x从而得一最优策略, 01x,2002x,3003x1004x第57页/共69页同理还有另外三个最优策略:,2001x,1002x,2003x1004x,1001x,1002x,3003x1004x,2001x,2002x, 03x2004x所有解总利润最大增长额为134)(11sf（百元）加上刚才一组,2002x,3003x1004x, 01x第58页/共69页资源分配问题（连续型）：设备负荷分配问题。例3:某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损

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

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