第七章动态规划

1、 第七章 动 态 规 划 第一讲 概念及最短路问题动态规划（Dynamic Programming）是20世纪50年代由美国数学家贝尔曼（Richard Bellman）及他的学生们一同建立和发展起来的一种解多阶段决策问题的优化方法。所谓多阶段决策问题是指一类活动过程。它可按时间或空间把问题分为若干个相互联系的阶段。在每一阶段都要作出选择（决策），这个决策不仅仅决定这一阶段的效益，而且决定下一阶段的初始状态，从而决定整个过程的走向（从而称为动态规划）。每当一阶段的决策一一确定之后，就得到一个决策序列，称为策略。所谓多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。先声明：下面研究的解

2、决多阶段的决策问题的最优化的称之为动态规划的数学方法，仅仅是一种解决问题的思路，而不是一种算法。这一点与线性规划不同。线性规划是一种算法。下面从一典型的例子去说明动态规划的基本思想与原理：某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？5C128D1 433B154E1C26456E2C4C3FA 3D2 3285 147 3B2D3 87 4 第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 图7-1先引入几个符号与概念：（1） 阶段与阶段变量：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶段用阶段变量k来描述，k=1,表示第一阶段，

3、k=2表示第二阶段，（2） 状态与状态变量：每一阶段的左端点（初始条件）集合称为本阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状态S3 =C1 ,C2，C3，C4, 第四阶段有三个状态 S4=D1, D2 , D3, 描述过程状态的变量称为状态变量：用小写s1 ,s2 ,s3 表示第一，第二，第三阶段的状态变量。当处在状态C2时，我们可记 s3= C2正像离散型R.V“X=2”代表一事件一样。(3) 决策与决策变量：如当处于C2状态时，下一步怎么走？如何选择路线？即如何决策。是走向D1，还是走向D2？当过程处于某一阶段的某一状态时，可以作出不同的决策（或选择），从而确定下一阶

4、段的状态，这种决定（或选择）叫决策。如选择D2，记u3（C2）= D2说，当处于C2状态时，下一步的决策为D2。其中表示第k阶段当状态处于时的决策变量。一般地，用表示第k阶段从状态出发的允许决策集合。如=D1 ，D2显然，。 （4）策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列： ，称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。（5）状态转移方程：是描述由第k阶段到第k+1阶段状态转移规律的关系式。 =上例中状态转移方程为： = （6）指标函数与最优指标函数：用于衡量所选定策略优

5、劣的数量指标称为指标函数。相当于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态出发，采用决策时的效益，用表示。最优指标函数是指从第k阶段状态采用最优策略到过程终止时的最佳效益值，用表示。例如：d（C2, D1）是指由C2出发，下一阶段的决策是D1的两点间的距离。即d（C2, D1）=4。表示从B1到F的最短距离。整个问题即为=？1 逆序递推法：倒退着从F向A走，每倒退一步，思想上问自己：“从现在出发，退向何处？到F的距离最短？”我们分5步来解决问题：（1） k=5时下求=？此时状态集S5=E1，E2，故分情况讨论，先说=

6、？若最佳路径从A出发通过E1的话，由 E1到终点F的最短距离为=5同理，=3。 （只有唯一的选择）故最优决策为：=F，=F（2） k=2时 下求 =？由于S4=D1, D2 , D3，下分四种情况进行讨论：=min = min =7, = E1.=min = min =5, = E2.=min = min =5, = E1.(3) k=3时 S3 =C1 ,C2，C3，C4,=min = min =12, = D1.同理，=10， = D2. =8， = D2. =9， = D3.（4）k=4时 S2=B1, B2=min = min =13, = C2.同理，=15， = C3.（5）k=1

7、时， S1=A=min = min =17, = B1.再按计算顺序的反推可得最优策略：= B1. = C2. = D2. = E2. = F.从而得最优路径：AB1 C2 D2E2 F最短距离为 =17。由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：这种递推关系称为动态规划的基本方程。（7.3b）式称为边界条件。2 逆向标号法每退到一站，看终点F，找最短路径及最短路径的距离，标号。画路径。（12）（7）C125（13）（10）8D1 3（4）B14C24E153（17）（5）（8）5646E2C4C3FA 23D2 （15）1（3）385 （5）47 （9）3B2

8、D3 87 4 图 7-2此时的（？）？=最优指标函数值f.得最优路径： AB1 C2 D2E2 F总距离为 17.3 顺序递推法：此法类似于逆序递推法。从起点A向终点F倒退。（1） k=1时，=0，此为初始条件。退向允许决策集S1=B1, B2 此时退向B1时看起点A，最短距离为=4，此时路径（或最优决策）是唯一的：=A；记，同理，（2） k=2时，直接用递推式：（3） k=3时。类似的， 同理， ， 最后 逆推最优策略：AB1 C2 D2E2 F。 与前相同。全部计算情况如图7-3（11）C152（6）（4）（7）8D1 3（14）B1C2E14435（12）（10）（17）5646E2C

9、4C3FA 23D2 （14）（5）1385 （14）47 （12）3B2D3 87 4 图 7-3递推关系式： 此与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。如习题7.2/P237，终点有三个，用逆序解法较好。7.2/P237 一艘货轮在A港装货后驶往F港，中途须靠港加油、淡水三次，从A港到F港全部可能的航行路线及两港之间距离如图7-7，F港有三个码头 ，实秋最合理的停靠的码头及航线，使总路程最短。3040203050253040605030406030204550C1F2F2F1D2D1

10、C3C2B1B2A F 图7-7解：顺序解法此法类似于逆序递推法。从起点A向终点F倒退。（1） k=1时，=0，此为初始条件。退向允许决策集S1=B1, B2 ，此时退向B1时看起点A，最短距离为=50，此时路径（或最优决策）是唯一的：=A；记，同理，（2） k=2时，直接用递推式：（3） k=3时。类似的。（4） k=4时由此看来，A到F距离最短的是120，故最优路线为A B2 C3 D1F2 §7.2 资源分配问题（离散型）例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？ 表内数据是利

11、润额 投资额(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个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：S5状态s4状态s3状态s2s1=600投资x1(万元)投资x2(万元)投资x4(万元)投资x3(万元)S4= s3-x3S3= s2-x2s2= s1-x1工厂2工厂1工厂3工厂4状态变量：可用于第k, k+1,n个工厂的投资

12、额。决策变量：第k阶段对第k个工厂的投资额。允许决策集：=0，100，状态转移方程：=- k=1,2,3,4 其中=600。阶段指标函数：第i阶段投资元时所产生的利润。（见上表）最优指标函数：第k阶段状态为且对第k个工厂投资为时，第k个工厂以及以后的总利润。 基本递推方程： 初始条件已知：=600，逆序法求解。（1） k=4时，考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为 （注意到此时=0） = （1）自然问：现在还有多少钱？即=？=0，100，200，300，400，500，600都有可能。下分情况讨论： =0时，只能=0。从表上看（4，1）位置是

13、第4个工厂=0时的利润其值为=0，由=0的唯一性知=0。=100，此时=0或100。产生的利润=0或28。 =0，28=28，对应的=100，即此种情况的最优决策=100。其他种情况类似讨论，我们把所有的结果汇总成一个表1。（2）k=3时 到第三个工厂投资时，可利用的资金还有，若向第三个工厂投资（万元），则自此即以后最大利润为： = 表10 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 850284765

14、7480850100200300400500600同样问：=？，即现在还有多少钱？分情况讨论汇总成下表： +0 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

15、00，得所有可能取值为0，100，200，300，此为第三阶段允许决策集。在=0，100，200，300中选取最优的，使最大，即=max,=max0+65,18+47,39+28,61+0=67, 此67对应的是=200时所得，即=200；（3）k=2时 此时，的所有可能取值0，100，200，300，400，500，600，每个定一个值，在的范围内变动，由，求出=？=？=？下面举一个例子来说明。=max,=0+126，25+108，45+89，57+67，65+47，70+28，73+0=max126，133，134，124，112，98，73=134。对应最大值的=200，所以=200。关

16、于的其他取值情况及相应的最有决策列于下表+0 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（5） k=1时，此时=600。=max,=max0+134,20+114,

17、42+92,60+73,75+53,85+28，90+0=max134,134,134,133,128,113,90=134. 0 100 200 300 400 500 600 6000+134 20+114 42+92 60+73 75+53 85+28 90+01340或100或200此时对应最大值134的有三个值：=0，100，200。所对应的最优策略分别为：=0，由= -=600-0=600 对应的 =200， 再由=-=600-200=400对应的=300 再由=-=400-300=100对应的=100从而得一最优策略=0，=200，=300，=100同理还有另外三个最优策略=20

18、0，=100，=200，=100=100，=100，=300，=100=200，=200，=0，=200总的最大利润=134（万元）第三讲：资源分配问题（连续型）设备负荷分配问题。例（何坚勇/P-256）某公司有1000辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？解：这是一个以时间为特征的多阶段决策问题。投x3辆超负车投x2辆超

19、负荷车投x1辆超负荷车状态s3状态s2第1年第2年第3年s1=1000s2=0.9 s1-0.2x1S3= s2-x2投x5辆超负车投x4辆超负车状态s4S5s4=0.9 s3-0.2x3s5=0.9s4-0.2x4第五年第四年阶段：将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5状态变量：第k阶段初完好卡车数量。=1000，=500。决策变量：表示第k阶段用于分配给超负荷运输的卡车数量。 显然，分配给低负荷的卡车数为-。注：这里视，为连续变量。若=0.6表示还有一辆卡车在第k年度有60的时间处于完好状态。=0.7表示有一辆卡车在第k年度有70的时间超负荷运输等等。状态转移方程：

20、=（1-0.3）+（1-0.1）（-）=0.9-0.2 k=1,2,3,4,5 阶段指标函数：表示第k年度利润。 =25+16（-） =16+9 k=1,2,3,4,5 最优指标函数：第k年度初完好车辆数为时，采用最优策略到第5年末所产生的最大利润。 递推式为： 下用逆序递推法求解：1） k=5时 （注意到此时=0）16 = O =16+9=25 =2) k=4时 = = = =38.5+4=42.4。此时，=3） k=3时 = = = =54.25+0.5 =54.75 此时，=4） k=2时 = = =65.275 此时=05） k=1时 = = = =74.7475 =74.7475&#

21、215;1000 =74747.5（万元） 此时=0下用倒推法求出最优策略。=0， =0.9-0.2=0.9×1000-0.2×0=900辆=0 =0.9-0.2=0.9×900-0.2×0=810辆=810 =0.9-0.2=0.9×810-0.2×810=567辆=567 =0.9-0.2=0.7×567=396.9辆=396.9 =0.9 -0.2=0.7×396.9=277.83辆答：第一年初：1000辆车全部用于低负荷运输。第二年初：还有900辆完好的车，也全部用于低负荷运输。第三年初：还有810辆完好的

22、车，全部用于超负荷运输。第四年初：还有567辆完好的车，全部用于超负荷运输。第五年初：还有396.9辆完好的车，全部用于超负荷运输。到第五年末，即第六年初，还剩余277.83辆完好的车。所创最大利润=74747.5万元某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量为h=8u，其中u为投入生产的机器数量，年终机器的完好率为a=0.7；在低负荷下生产的产量函数为=5v,其中v为投入生产的机器数量，年终机器的完好率为b=0.9。假定开始生产时完好的机器数量为=1000台，试问企业每年年初应如何安排机器在高、低两种负荷下的生产，使在第5年年末完好的机器数量=500台，并且5年内生

23、产的产品总产量最高。第1年第2年第3年第四年投x1辆超负荷车投x2辆超负荷车投x3辆超负车投x4辆超负车s1=1000状态s2s2=0.9 s1-0.2x1S3= s2-x2状态s4状态s3S5第五年投x5辆超负车s5=0.9s4-0.2x4=500s4=0.9 s3-0.2x3解：阶段指标函数：第k年的产量 =8+5（-）=5+3 k=1,2,3,4,5 下用逆序递推法求解：1） k=5时=0.9-0.2=500可得 =4.5-2500=3（4.5-2500）+5=18.5-75002） k=4时 = = = =21.65-7500 此时=03） k=3时 = = =24.48-7500 此

24、时=04） k=2时 = = =27.0365-7500 此时=05） k=1时 = = =29.33285-7500 =29.33285×1000-7500 =21832.85 此时=0最优策略为：=0， =0.9-0.2 =0.9×100=900辆=0， =0.9-0.2=0.9×900-0.2×0=810辆=0， =0.9-0.2=0.9×810-0.2×0=729辆=0， =0.9-0.2=0.9×729=656.1辆=4.5-2500=4.5×0.94-2500=452.45 =0.9 -0.2=0.9&

25、#215;656.1-0.2×452.45=500辆其中=0.9=0.9×0.9=0.9×0.9×0.9×0.9=656.1答：第一年初：1000辆车全部用于低负荷运输。第二年初：还有900辆完好的车，也全部用于低负荷运输。第三年初：还有810辆完好的车，全部用于低负荷运输。第四年初：还有729辆完好的车，全部用于低负荷运输。第五年初：还有656.1辆完好的车，其中452台用于高负荷运输，204台在低负荷下运输。到第五年末，即第六年初，还剩余500辆完好的车。所创最大利润=21833万元第四讲 资源分配问题（一维连续）例5 某公司有资金10万元

26、，若投资于项目i (i=1,2,3)的投资额为时，其收益分别为。其中=4，=9，=2，问应如何分配资金额才能使总收益最大？解： = s.t (一) 逆序解=-=4=2=9=-项目1=10-项目1=10项目1 状态转移方程： k=1,2,3基本方程：对这种初始状态=10（万元）已知的资金分配问题，我们采用逆序法。K=3时 =2； 此时，=K=2时O = =问 = 0，当=？时，最大。且最大值=？ （0，）时。 =9+4（-）（-1）=0， =-9/4且 =4>0。 故在=-9/4处取得极小值。=2=9 依题意在0，上有极大值，故极大值只能在端点处取得，为此考察：=9 =2； =9现在问：谁

27、大谁小？这是以为自变量的两个函数的大小比较问题。O 9/2 从右图上可看出=最后看k=1时现在的问题是=？2200=90O 9/2 10 = = = =200 此时，=0。逆追最优解： =0， =10-=109/2 =0 =-=10 =10且最大利润 =200（万元）=10（二） 顺序解：=-=-=-=2=9=4项目2项目3项目1 状态转移方程： =- k=1,2,3最优指标函数：第k阶段，当投资额为时，从第1到第k阶段所获得的最大收益。 总的收益=？基本方程：k=1时:=4 此时，=k=2时：=9，此时，=k=3时：=令= 0，10下求它的极大值： = 49 令其为0，得 =9/4 且= 4

28、0故此函数在（0，10）内只有一个极小值点。极大值点只能在端点处取的。 考虑：=0时， =9=90=10时， =2=200 所以有 =10此时，200。再用状态转移方程逆推得最优解：=10，=-=10-10=0，=0，=-=0-0=0，=0。此解与逆序相同。（三）连续变量的离散化解法：例6 用连续变量的离散化求解： Max z =4+9+2s.t 解：因为这里的010，k=1，2，3.可在区间0，10内选有限个点，比如分割成0，2，4，6，8，10。将来决策变量、状态变量均取值集合0，2，4，6，8，10中的点。尽管这样做可能出现丢失最优解，但作为近似解求解简单。此时的动态规划基本方程： 当k

29、=3时， =式中的，均取值于0，2，4，6，8，10，计算结果见下表02468100832721282000246810当k=2时，=，计算结果见下表+0 2 4 6 8 10 0 2 4 6 8 100+00+8 18+00+32 18+8 36+0 0+72 18+32 36+8 54+0 0+128 18+72 36+32 54+8 72+0 0+200 18+128 36+72 54+32 72+8 90+00183672128200024000k=1时，计算结果见下表0 2 4 6 8 10 100+200 8+128 16+72 24+36 32+18 40+0 2000计算结果表

30、明，最有决策为： =0，=0，=10。最大收益为=200。与上例完全相同。 第五讲：背包问题一般的提法为：以旅行者携带背包去登山。已知他所能承受的背包重量的极限为a (千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为(千克)其价值（可以是表明本物品对登山者的重要性指标）是携带数量的函数（i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？其数学模型为： max z = s. t (i=1,2,n.且为整数)此模型解决的是运输工具包括卫星的最优装载问题。下面从一个例子来分析动态规划建模。例7 有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应

31、单位价值如表7-4所示。应如何装载可使总价值最大？货物编号i 1 2 3单位重量（t） 3 4 5单位价值ci 4 5 6设第i种货物的件数为（i=1,2,3），则问题可表述为： max z = 456 (i=1,2,n.且为整数)下用动态规划顺序解法建模求解：阶段k: 将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.状态变量：在第k段开始时，背包中允许装入前k种物品的总重量。决策变量：装入第k种物品的件数。状态转移方程： 最优指标函数：在背包中允许装入物品的总重量不超过kg，采取最优策略只装前k种物品时的最大使用价值。由此可得动态规划的顺序递推方程为：

32、534 =-3=-4=-5=10 货物3货物1货物1=5=6=4由于取整数，故，0，1，2，10，下用顺序法求解。K=1时 =计算结果见下表：0 1 2 3 3 4 7 8 9 4×04×0 4×0 4×0 4×1 4×0 4×1 4×24×0 4×1 4×2 4×3000481202400123K=2时 =具体的计算结果见下表0 1 2 1 2 3 4 6 7 8 9 5×00 5×04 5×10 5×012 5×18 5&

33、#215;20 0513011k=3时：= = max 0, 6, 12 = max013,65,120=13 此时，=0下逆推得最优解： =0，=-5=10-0=10 =1 =-4=10-4=6 =2最大装载价值为 =13。故今后解背包问题应先从k=3入手：k=3时：= = max 0, 6, 12下有重点地从k=2中求解三个最优函数值：，。K=2时 = = = max0, 5, 10= = = max0, 5=下从第一阶段有重点地求四个函数：，K=1时 =0， 此时 =0=0 此时 =0= = = max0，4= 4, 此时 =1= = = maxo,4,8,12=12, 此时 =3由此逆推回去：=0， 此时 =0，=0 = max0, 5= max04, 50=5，此时 =0，=1= max0, 5, 10 = max012, 58, 100=13, 此时 =1, =2最后： = max 0, 6, 12 = max013, 65, 120=13, 对应最大值13，=0，且，故对应=2, =1最大运输价值=13。7.9/P-239 用动态规