第6章_动态规划

1、n状态状态1决策决策2决策决策决策决策状态状态状态状态状态状态状态状态AB23B1C1C2C3C4D1D2D3E1E2E3F1F2G531368 76683533842221335526643图2)(1ugg )(2uhh )()(kkkksDsx )(,(1kkkkksxsTs 0)()()(,()(1111)(nnkkkkkksDxkksfsfsxsvoptsfkkk)(,(1kkkkksxsTs 阶阶段段f2(s2)X2*0123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+01

2、1+411+0051014162101221，22x2s2P2(x2)+f3(s2-x2) 阶阶段段f1(s1)x1*01234550+113+16 7+14 9+1012+513+0210，2P1(x1)+f2(5-x1)x1s1解：第一步，划分阶段。每一年为一个阶段，解：第一步，划分阶段。每一年为一个阶段，5年分为年分为5个阶段，个阶段，k=1，2，3，4，5。第二步，确定状态变量：状态变量第二步，确定状态变量：状态变量sk为第为第k年年年年初拥有的完好设备数，且初拥有的完好设备数，且1251 s5 , 4 , 3 , 21250 ksk 第三步，确定决策变量。决策变量第三步，确定决策变量

3、。决策变量xk为第为第k阶段安排阶段安排在高负荷下工作的设备数，且在高负荷下工作的设备数，且kksx 0则第则第k阶段安排在低负荷下工作的设备数为：阶段安排在低负荷下工作的设备数为：kkxs 第四步，状态转移方程。由于在两种负荷下工作的设第四步，状态转移方程。由于在两种负荷下工作的设备损坏率分别为备损坏率分别为1/2和和1/5，则第，则第k+1年年初拥有的年年初拥有的完好设备数为：完好设备数为：kkkkkkxsxsxs10354)(511()211(1 第五步，指标函数。第第五步，指标函数。第k阶段的指标函数为第阶段的指标函数为第k年可年可得的利润：得的利润：kkkkkkkksxxsxxsv6

4、4)(610),( 第六步，函数基本方程第六步，函数基本方程 5 , 10)()10354(64max)(),(max)(661011 ksfxsfsxsfxsvsfkkkkksxkkkkkxkkkkkK=5时时)64(max)(5505555sxsfsx 因因f5是线性单调增函数，故得最优解是线性单调增函数，故得最优解x5*=s5，相，相应的有应的有f5(s5)=10s5K=4时时)14(max)10354(1064max)1064(max)(64max)(440444405440554404444444444xsxssxssxsfsxsfsxsxsxsx 因因f4是是x4线性单调增函数，故

5、得最优解线性单调增函数，故得最优解x4*=s4，相应的有，相应的有f4(s4)=15s4K=3时时)2118(max)10354(1564max)1564(max)(64max)(330333304330443303333333333xsxssxssxsfsxsfsxsxsxsx 因因f3是是x3线性单调下降函数，故得最优解线性单调下降函数，故得最优解x3*=0，相应的有，相应的有f3(s3)=18s3K=2时时 因因f2是是x2线性单调下降函数，故得最优解线性单调下降函数，故得最优解x2*=0，相应的有，相应的有f2(s2)=20.4s2)575220(max)10354(1864max)1

6、864(max)(64max)(220222203220332202222222222xsxssxssxsfsxsfsxsxsxsx K=1时时 因因f1是是x1线性单调下降函数，故得最优解线性单调下降函数，故得最优解x1*=0，相应的有，相应的有)5010625558(max)10354(522064max)522064(max)(64max)(110111102110221101111111111xsxssxssxsfsxsfsxsxsxsx 11125822)(ssf （台台）10054103541112 sxss（台台）8054103542223 sxss（台台）64541035433

7、34 sxss（台台）32105103544445 sxss（台台）16105103545556 sxss 例例1：今有三种货物需要装船，各种货物的重量与运：今有三种货物需要装船，各种货物的重量与运输利润关系如表输利润关系如表1所示。船的最大装载能力为所示。船的最大装载能力为w=6(t)，问应如何装载才能使总利润最大？问应如何装载才能使总利润最大？货物种类（货物种类（i）货物重量（货物重量（wi）（t）利润（利润（vi）（千）（千元）元）12323481318解：第一步，划分阶段。每装一种货物为一个阶段，解：第一步，划分阶段。每装一种货物为一个阶段，第二步，确定状态变量。状态变量第二步，确定状

8、态变量。状态变量 为可用于装载第为可用于装载第k种至第种至第n种货物的装载量。且种货物的装载量。且第三步，确定决策变量。决策变量第三步，确定决策变量。决策变量 为第为第k种货物的种货物的装载件数。且装载件数。且其中，其中， 为不大于为不大于 的最大整数。的最大整数。3 , 2 , 1 kks3 , 26 , 5 , 4 , 3 , 2 , 1 , 061ksskkx3 , 2 , 1, 1 , 0)( kwssDxkkkkk kkwskkws第四步，状态转移方程第四步，状态转移方程 即第即第k+1阶段船的可装载量等于第阶段船的可装载量等于第k阶段船的可装载阶段船的可装载量与装载量之差。量与装载

9、量之差。第五步，指标函数。阶段指标即为第第五步，指标函数。阶段指标即为第k阶段装载阶段装载xk件件货物时所创的利润货物时所创的利润vkxk。第六步，函数基本方程。第六步，函数基本方程。kkkkxwss 10)(3 , 2 , 1)(max)(44116, 1 , 0)(sfksfxvsfkkkkssDxkkkkkkk=3时时18, 433 vw 6 , 1 , 03 s 1 , 04, 1 , 033 sx )18(max)(36, 1 ,01 ,03333xsfsx 计算结果见表。计算结果见表。阶段阶段 0 1012345600000 180 180 18000018181800001110

10、123012k=2时时 13, 322 vw 6 , 1 , 02 s 2 , 1 , 03, 1 , 022 sx )3(13max)(22326, 1 ,02, 1 ,02222xsfxsfsx 阶阶段段 0 1 2k=201234560+00+00+00+0 13+00+18 13+0 0+18 13+0 0+18 13+0 26+00001318182600010020120450k=1时时 8, 211 vw 61 s 3 , 2 , 1 , 02, 1 , 011 sx )2(8max)(112163,2, 1 ,01111xsfxsfsx 阶阶段段 0 1 2 3k=16 0+2

11、6 8+18 16+0 24+0260,16,4至此，得最大利润为至此，得最大利润为f1(s1)=26。有两个最优方案：。有两个最优方案： 0*, 2*, 0*321 xxx1*, 0*, 1*321 xxx例例1：某船厂根据合同，从当年起连续：某船厂根据合同，从当年起连续4年年末要为客户提供规格年年末要为客户提供规格型号相同的大型客货船，每年的交船数及生产每艘船的生产费用型号相同的大型客货船，每年的交船数及生产每艘船的生产费用如表如表1所示。该厂的生产能力为每年所示。该厂的生产能力为每年6 6艘船。在进行生产的年度，艘船。在进行生产的年度，船厂还要支出经常费船厂还要支出经常费6060万元。若

12、造出的船当年不交货，则每艘船万元。若造出的船当年不交货，则每艘船每积压一年造成的积压损失费为每积压一年造成的积压损失费为4040万元。假定开始时及第四年年万元。假定开始时及第四年年末交货后均无积压船只，问船厂应如何安排这四年的生产计划，末交货后均无积压船只，问船厂应如何安排这四年的生产计划，使所花的总费用为最低？使所花的总费用为最低？ 年度年度每艘船的生产费用（百万每艘船的生产费用（百万元）元）每年需交付的船数每年需交付的船数（艘）（艘）12346.06.06.36.51322解：第一步，划分阶段。每一年度为一个阶段，解：第一步，划分阶段。每一年度为一个阶段，4年分为年分为4个阶段，个阶段，第

13、二步，确定状态变量。状态变量第二步，确定状态变量。状态变量 为第为第k k阶段初贮存阶段初贮存（积压）的船数。且（积压）的船数。且 必须满足以下条件：必须满足以下条件：（1）不能超过本年度及以后各年度交船数的总和）不能超过本年度及以后各年度交船数的总和（2）为保证按时交船，每年年初的存船数加上本年度的）为保证按时交船，每年年初的存船数加上本年度的最大可能生产量不应小于本年度的交船数最大可能生产量不应小于本年度的交船数（3）此外，还有）此外，还有 。4 , 3 , 2 , 1 kksks 40kiikdskkds 6051 ss第三步，确定决策变量。决策变量第三步，确定决策变量。决策变量 为第为

14、第k k阶阶段生产的船数。且段生产的船数。且 必须满足以下条件：必须满足以下条件：（1）不能超过每年的库存能力：）不能超过每年的库存能力：（2）某年所拥有的存船数，不应超过本年度及以）某年所拥有的存船数，不应超过本年度及以后各年交船数的总和：后各年交船数的总和：（3）某年所拥有的存船数，不应少于本年度的交）某年所拥有的存船数，不应少于本年度的交船数：船数：kxkx最大库存量最大库存量 kkkdsx 4kiikkdsxkkkdsx 第四步，状态转移方程第四步，状态转移方程 即第即第k k年的存船数加上第年的存船数加上第k k年生产的船只数，再减去年生产的船只数，再减去第第k k年交付的船数，就等

15、于第年交付的船数，就等于第k+1k+1年初的存船数。年初的存船数。第五步，指标函数。第第五步，指标函数。第k k阶段的指标函数阶段的指标函数v vk k就是第就是第k k年度的生产成本（包括生产费用与存贮费用两部年度的生产成本（包括生产费用与存贮费用两部分）。分）。第六步，函数基本方程。第六步，函数基本方程。4 , 3 , 2 , 11 kdxsskkkk 0)(4 , 3 , 2 , 1)(),(min)(551160sfksfxsvsfkkkkkxkkk04 . 004 . 06 . 0kkkkkkkxsxsxcv若若k=4时，时，d4=2，故，故 2 , 1 , 04 s 0 , 1 ,

16、 24 x 04 . 004 . 05 . 66 . 0444444xsxsxv若若若若期初存期初存船（船（s4）可能的可能的生产量生产量（x4）本期费本期费用（用（v4）期末期末存船存船（s5）401221013.67.50.800000013.67.50.8k=3时，时，d3=2，故，故 4 , 3 , 2 , 1 , 03 s 04 . 004 . 03 . 66 . 0333333xsxsxv若若若若期初存期初存船（船（s3）可能的生可能的生产量（产量（x3）本期费本期费用（用（v3）期末存期末存船（船（s4）3023413.219.525.801213.67.50.826.827.0

17、26.6*11237.313.619.901213.67.50.820.921.120.7*20120.87.714.001213.67.50.814.4*15.214.83011.28.1127.50.88.7*8.9401.620.82.4*k=2时，时，d2=3，故，故 5 , 4 , 3 , 2 , 1 , 02 s 04 . 004 . 00 . 66 . 0222222xsxsxv若若若若期初存船期初存船（s2）可能的生产量可能的生产量（x2）本期费用本期费用（v2）期末存船（期末存船（s3）20345618.624.630.636.6012326.620.714.48.745.2

18、45.345.0*45.312345613.019.025.031.037.00123426.620.714.48.72.439.639.739.4*39.739.4*2123457.413.419.425.431.40123426.620.714.48.72.434.034.133.8*34.133.8*3012341.27.813.819.825.80123426.620.714.48.72.427.8*28.528.228.528.2401231.68.214.220.2123420.714.48.72.422.3*22.622.922.650122.08.614.323414.48.72.416.4*17.317.0k=1时，时，d1=1，故，故01 s 6 , 5 , 4 , 3 , 2