(精品)动态规划(2).ppt

《(精品)动态规划(2).ppt》由会员分享，可在线阅读，更多相关《(精品)动态规划(2).ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7-7-2 2 动态规划应用举例动态规划应用举例例例7-7-6 6 一家著名的快餐店计划在一家著名的快餐店计划在某城市建立某城市建立5 5个分店，这个城市分个分店，这个城市分成三个区，分别用成三个区，分别用1 1，2 2，3 3表示。表示。由于每个区的地理位置、交通状况由于每个区的地理位置、交通状况及居民的构成等诸多因素的差异，及居民的构成等诸多因素的差异，将对各分店的经营状况产生直接的将对各分店的经营状况产生直接的影响。经营者通过市场调查及咨询影响。经营者通过市场调查及咨询后，建立了下表。后，建立了下表。该表表明了各个区建立不同数目该表表明了各个区建立不同数目的分店时的利润估计，确定各区的分

2、店时的利润估计，确定各区建店数目使总利润最大。建店数目使总利润最大。解：解：阶段：阶段：每个区，共三个阶段。每个区，共三个阶段。状态：状态：S Sk k为第为第k k阶段开始时，可供阶段开始时，可供分配的店数。分配的店数。决策：决策：d dk k为分配给区为分配给区k k的店数。的店数。状态转移方程：状态转移方程：S Sk+1k+1=S Sk k-d dk k效益：效益：r rk k(d dk k)为分配给区为分配给区k,k,d dk k个店个店时的利润。时的利润。f fk k(S Sk k)为当第为当第k k阶段初始状态为阶段初始状态为S Sk k时时，从第，从第k k阶段到最后阶段所得最阶

3、段到最后阶段所得最大利润。大利润。fk(Sk)=Max rk(dk)+fk+1(Sk+1)d dk k (S Sk k)k=1，2，3f4(S4)=0k=3 时，时，计算如下：计算如下：k=2k=2 时，时，计算如下：计算如下：S3=S2-d2k=1 k=1 时，时，计算如下：计算如下：最优解：最优解：d*d*1 1=3=3，d*d*2 2=2=2，d*d*3 3=0=0即：在区即：在区1 1建建3 3个分店，在区个分店，在区2 2建建2 2个分店，而不在区个分店，而不在区3 3建立分店。最建立分店。最大总利润大总利润=22=22。d1*=3,s2=s1-d1*=5-3=2,d2*=2s3=s

4、2-d2*=2-2=0,d3*=0建立动态规划模型的要点：建立动态规划模型的要点：分析题意，识别问题的多阶段性，分析题意，识别问题的多阶段性，按时间或空间的先后顺序适当地按时间或空间的先后顺序适当地划分满足递推关系的若干阶段，划分满足递推关系的若干阶段，对非时序的静态问题要人为地赋对非时序的静态问题要人为地赋予予“时段时段”的概念。的概念。建立动态规划模型的要点：建立动态规划模型的要点：正确地选择状态变量，使其具备两正确地选择状态变量，使其具备两个必要特征：个必要特征：（1 1）可知性：即过去演变过程的各）可知性：即过去演变过程的各阶段状态变量的取值，能直接或间阶段状态变量的取值，能直接或间接

5、地确定。接地确定。（2 2）能够确切地描述过程的演变且）能够确切地描述过程的演变且满足无后效性。满足无后效性。建立动态规划模型的要点：建立动态规划模型的要点：根据状态变量与决策变量的含义，根据状态变量与决策变量的含义，正确写出状态转移方程或转移规则。正确写出状态转移方程或转移规则。根据题意明确指标函数，最优指标根据题意明确指标函数，最优指标函数以及一段效益即阶段指标的含义。函数以及一段效益即阶段指标的含义。并正确列出最优指标函数的递推关系并正确列出最优指标函数的递推关系及边界条件（即及边界条件（即 DPDP基本方程）。基本方程）。例例7-7-7 7（投资问题）（投资问题）现有资金现有资金5 5

6、百万百万元，可对三个项目进行投资，投资元，可对三个项目进行投资，投资额均为整数（单位为百万元），其额均为整数（单位为百万元），其中中2#2#项目的投资不得超过项目的投资不得超过3 3百万元，百万元，1#1#和和3#3#项目的投资均不得超过项目的投资均不得超过4 4百万百万元，元，3#3#项目至少要投资项目至少要投资1 1百万元，百万元，每个项目投资每个项目投资5 5年后，预计可获得收年后，预计可获得收益由下表给出，问如何投资可望获益由下表给出，问如何投资可望获得最大收益。得最大收益。解：解：这个投资问题可以分成三个阶段，这个投资问题可以分成三个阶段，在第在第k k阶段确定阶段确定k k#的投资

7、额的投资额令令 S Sk k对对1 1#，2 2#.（k-1k-1）#项项目投资后剩余的资金额。目投资后剩余的资金额。X Xk k对对k k项目的投资额。项目的投资额。r rk k (X Xk k)对对k k#项目投资项目投资X Xk k的收益的收益.f fk k(S Sk k)应用剩余的资金应用剩余的资金S Sk k 对对k k#,(,(k+1)k+1)#.N.N#投资可获得的最大收益。投资可获得的最大收益。状态转移方程为：状态转移方程为：S Sk+1k+1=S Sk k-X Xk k为了获得最大收益，必须将为了获得最大收益，必须将5 5百万百万元全部用于投资，故假想有第元全部用于投资，故假

8、想有第4 4阶阶段存在时，必有段存在时，必有S S4 4=0=0，于是得递推于是得递推方程：方程：fk(Sk)=Max rk(Xk)+fk+1(Sk+1)dkdk(SkSk)k=3,2,1f4(S4)=0当当k=3k=3时，（时，（3#3#至多投资至多投资4 4百万元，百万元，至少投资至少投资1 1百万元）百万元）f f3 3(1(1）=4=4，f f3 3(2(2）=8=8，f f3 3(3(3）=11=11，f f3 3(4(4）=15=15当当k=2k=2时，（时，（2#2#投资不超过投资不超过3 3百万元）百万元）f f2 2(1(1）=r=r2 2(0)+f(0)+f3 3(1(1）

9、=0+4=0+4f2(2）=Max r2(1)+f3(1)r2(0)+f3(2）=Max 5+4，0+8 =9当当k=2k=2时，（时，（2#2#投资不超过投资不超过3 3百万元）百万元）f2(3）=Max r2(2)+f3(1)r2(1)+f3(2）r2(0)+f3(3）=Max 10+4，5+8，0+11 =14f2(4）=Max r2(3)+f3(1）r2(2)+f3(2)r2(1)+f3(3）r2(0)+f3(4）=Max 12+4，10+8，5+11，0+15 =18当当k=2k=2时，（时，（2#2#投资不超过投资不超过3 3百万元）百万元）f2(5）=Max r2(3)+f3(2

10、）r2(2)+f3(3)r2(1)+f3(4）=Max 12+8，10+11，5+15 =21注意：注意：3#3#至多投资至多投资4 4百万元百万元当当k=1k=1时，时，S S1 1=5=5（最初有最初有5 5百万元，百万元，3#3#至少投资至少投资1 1百万元）百万元）f1(5）=Max r1(0)+f2(5）r1(1)+f2(4)r1(2)+f2(3）r1(3)+f2(2）r1(4)+f2(1）=Max 0+21，3+18，6+14 10+9，12+4 =21解：解：应用顺序反推可知，最优投资应用顺序反推可知，最优投资方案：方案：方案方案1 1：X X*1 1=0=0，X X*2 2=2

11、=2，X X*3 3=3=3方案方案2 2：X X*1 1=1=1，X X*2 2=2=2，X X*3 3=2=2最大收益均为最大收益均为2121百万元。百万元。一维一维“背包背包”问题问题例例7-87-8：有一辆有一辆最大货运量最大货运量为为1010吨的吨的卡车卡车，用于装载用于装载三种三种货物货物，每种，每种货货物物的的单位重量单位重量及及相应单位价值如下相应单位价值如下，应应如何装载如何装载可使总可使总价值最大价值最大？解：解：设第设第i i种种货物装载货物装载的件数为的件数为xi(i=1,2,3)则则问题问题可可表示表示为为：max Z=4x1+5x2+6x3 3x1+4x2+5x3

12、10 xi 0且为整数且为整数(i=1,2,3)方法一：方法一：由于决策变量取整由于决策变量取整数，数，所以所以可以可以用用列表列表法求解。法求解。当当k=1时时,f1(s)=max 4x1 0 3x1 s x x1 1为整数为整数为整数为整数或或 f1(s)=max 4x1=4 s/3 0 x x1 1 s/3 x x1 1为整数为整数为整数为整数计算计算结果见下表：结果见下表：当当k=2时时,f2(s)=max 5x2+f1(s-4x2)0 x2 s/4 x x2 2为整数为整数为整数为整数计算计算结果见下表：结果见下表：当当k=3k=3时时f3(10)=max 6x3+f2(10-5x3

13、)0 x3 2 x x3 3为整数为整数为整数为整数 =max 6x3+f2(10-5x3)x x3 3=0,1,2=0,1,2 =max f2(10),6+f2(5),12+f2(0)=max13,6+5,12+0 =13 此时此时x x3 3*=0*=0，可推得可推得全部全部策略为：策略为：x x1 1*=2*=2，x x2 2*=1*=1，x x3 3*=0*=0，最大价值最大价值为为1313。方法二：方法二：问题问题最终最终要求要求f f3 3(10)(10)。而而f3(10)=max 4x1+5x2+6x3 3x1+4x2+5x3 10 xi为整数为整数I=1,2,3 =max 4x

14、1+5x2+6x3 3x1+4x2 10-5x3 xi为整数为整数I=1,2,3 =max 6x3+max 4x1+5x2 10-5x3 0 3x1+4x2 10-5x3 x3 0为整数为整数 xi 0为整数为整数I=1,2=max 6x3+f2(10-5x3)x3=0,1,2=max 0+f2(10),6+f2(5),12+f2(0)由此由此看到看到要要计算计算f f3 3(10)(10)须先须先计算计算f f2 2(10)(10)，f f2 2(5)(5)，f f2 2(0)(0)而而f f2 2(10)=max 4x(10)=max 4x1 1+5x+5x2 2 3x 3x1 1+4x+

15、4x2 2 10 x 10 x1 1，x x2 2 0 0整数整数 =max 4x=max 4x1 1+5x+5x2 2 3x3x1 1 10-4x 10-4x2 2 x x1 1，x x2 2 0 0整数整数 =max 5x2+max 4x1 10-4x2 0 3x1 10-4x2 x2 0整数整数 x1 0整数整数=max 5x2+f1(10-4x2 x2=0，1，2=max f1(10),5+f1(6),10+f1(2)同理，同理，f2(5)=max 4x1+5x2 3x1+4x2 5 x1，x2 0整数整数 =max 5x2+f1(5-4x2)x2=0，1 =max f1(5),5+f

16、1(1)f2(0)=max 4x1+5x2 3x1+4x2 0 x1，x2 0整数整数 =max 5x2+f1(0-4x2)x2=0 =f1(0)为了计算为了计算f2(10）f2(5)f2(0)需要需要先先计算计算f1(10)f1(6)f1(5)f1(2)f1(1)f1(0)。由于由于 f1(s)=max 4x1=4s/3 0 x1 s/3 x1为整数为整数f1(10)=12（x1=3），），f1(6)=8（x1=2），），f1(5)=4（x1=1），），f1(2)=0 （x1=0），），f1(1)=0（x1=0），），f1(0)=0 （x1=0）。）。从而从而f2(10)=max f1(10

17、),5+f1(6),10+f1(2)=max12，5+8，10+0 =13 （x1=2，x2=1）f2(5)=max f1(5),5+f1(1)=max4，5+0 =5 （x1=0，x2=1）f2(0)=f1(0)=0（x1=0，x2=0）最后最后有有f3(10)=max f2(10),6+f2(5),12+f2(0)=max13,6+5,12+0 =13 （x1=2，x2=1，x3=0）二维二维“背包背包”问题问题例例7-97-9：有一辆有一辆最大货运量最大货运量为为1212吨，吨，最大容量最大容量1010立方米的某种立方米的某种类型卡车类型卡车，用于装载两种货物用于装载两种货物A A、B

18、B，每种每种货物货物的单件的单件重量分别重量分别3 3吨、吨、4 4吨，吨，体积体积为为1 1立方米、立方米、5 5立方米，立方米，价值价值为为2 2、3 3，求求合理装载合理装载的的最大最大效益？效益？解：解：设设A A、B B货物装载货物装载的件数为的件数为 x xi i(i=1,2)(i=1,2)则则问题问题可可表示表示为：为：max Z=2xmax Z=2x1 1+3x+3x2 2 3x3x1 1+4x+4x2 2 12 12 x x1 1+5x+5x2 2 10 10 x xi i 0 0整数整数 (i=1,2)i=1,2)并解出并解出f2(12，10)=max 2x1+3x2 3x

19、1+4x2 12 x1+5x2 10 xi 0整数整数(i=1,2)=max 2x1+3x2 3x1 12-4x2 x1 10-5x2 xi 0整数整数(i=1,2)=max 3x2+f1(12-4x2,10-5x2)12-4x2 0 10-5x2 0 xi 0整数整数(i=2)=max 3x2+f1(12-4x2,10-5x2)x2 12/4 x2 10/5 xi 0整数整数(i=2)=max 3x2+f1(12-4 x2,10-5 x2)x2=0,1,2=max f1(12,10),3+f1(8,5),6+f1(4,0)先先 要要计算计算 f1(12,10),f1(8,5),及及 f1(4

20、,0)f1(12,10)=max 2x1=max 2x1 3x1 12 x1=0,1,2,3,4 x1 10 x1 0整数整数 =8 (x1*=4)同理，同理，f1(8,5)=4(x1*=2)f1(4,0)=0 (x1*=0)f2(12，10)=max f1(12,10),3+f1(8,5),6+f1(4,0)=max 8，3+4，6+0=8 (x1*=4 x2*=0)因此因此，最优方案为：，最优方案为：装装A A种种货物货物4 4件，件，不装不装B B种种货物货物，最大价值最大价值为为8 8。连续变量连续变量的的解法解法例例7-107-10：某某公司公司有有资金资金1010万元，可万元，可投

21、投资资于于项目项目i(i=1,2,3)i(i=1,2,3)，若若投资额投资额为为x xi i，其收益其收益分别分别为为g g1 1(x(x1 1)=4x)=4x1 1，g g2 2(x(x2 2)=9x)=9x2 2,g g3 3(x(x3 3)=2x)=2x3 32 2,问问如何分配投资额如何分配投资额，使总收益，使总收益最大最大？解：解：建立建立此此问题问题的的数学模型数学模型求求x xi i使使 max Z=4xmax Z=4x1 1+9x+9x2 2+2x+2x3 32 2 s.t.x s.t.x1 1+x+x2 2+x+x3 3 10 10 x x1 1,x,x2 2,x,x3 3

22、0 0 按按变量个数变量个数分分阶段阶段，可看成三段，可看成三段决决策问题策问题，设状态，设状态变量变量s sk k表示表示：第：第k k阶阶段可以段可以分分配给配给第第k k到第到第3 3个个项目项目的的资资金金额。额。决策变量决策变量x xk k：决定投资决定投资给第给第k k个个项目项目的的资金资金额。额。则有：则有：s s1 1=10=10,s s2 2=s=s1 1-x-x1 1,s,s3 3=s=s2 2-x-x2 2即状态即状态转移转移方程为：方程为：s sk+1k+1=s sk k-x xk k令最优指标令最优指标函数函数f fk k(s sk k)表示表示第第k k个个阶阶段

23、段，初始初始状态为状态为s sk k时，从第时，从第k k个到第个到第3 3个个项目项目所获所获最大最大收益收益,f f1 1(s(s1 1)即为所即为所求的总收益。求的总收益。fk(sk)=maxgk(xk)+fk+1(sk+1)xk k=3,2,1f4(s4)=0k=3 时，时，f3(s3)=max 2x32 0 x3 s3当当x3*=s3 时时,取得最大取得最大值值 2s32即即：f3(s3)=max 2x32 =2s32 0 x3 s3k=2 时，时，f2(s2)=max 9x2+f3(s3)0 x2 s2 =max 9x2+2s32 0 x2 s2 =max 9x2+2(s2-x2)

24、2 0 x2 s2令令 h h2 2(s(s2 2,x,x2 2)=)=9 9x x2 2+2(s2(s2 2-x-x2 2)2 2由由 dhdh2 2/dx/dx2 2=9+4(s=9+4(s2 2-x-x2 2)(-1)=0)(-1)=0解得解得 x x2 2=s=s2 2-9/4 -9/4 而而 d d2 2h h2 2/dx/dx2 22 2=40 =40 所以所以 x x2 2=s=s2 2-9/4 -9/4 是是极小极小点点。极大极大点只点只可能可能在在0 0，s s2 2 端点端点取得取得：f2(0)=2s22 f2(s2)=9s2当当s s2 2 9/2 9/2时时,f f2

25、2(0)(0)f f2 2(s(s2 2),),此时此时x x2 2*=0*=0当当s s2 2 9/2 9/2时时,f f2 2(0)f(0)9/2,与与s20=10所以所以 x x1 1=s=s1 1-1 -1 是是极小极小点，点，比较比较00，1010两个端点，两个端点，x1=0时时,f1(10)=200 x1=10时时,f1(10)=40所以所以 x1*=0再由状态方程得再由状态方程得 s s2 2=s=s1 1-x-x1 1*=10-0=10*=10-0=10由于由于 s s2 2 9/2 9/2，因此因此 x x2 2*=0,*=0,s s3 3=s=s2 2-x-x2 2*=10-0=10*=10-0=10所以所以 x x3 3*=s*=s3 3=10=10最优最优投资投资方案为方案为全部资金投入全部资金投入第第3 3个个项目项目可得可得最大最大收益收益200200万元。万元。