运筹学动态规划应用举例PPT课件

1、第四节 动态规划在经济管理中的应用 连续变量的离散化解法连续变量的离散化解法 先介绍连续变量离散化的概念。如投资分配问题先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：的一般静态模型为： niiixgz1)(max), 2 , 1(01nixaxinii模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量态变量 状态转移方程、基本方程、指标函数、最优指标函数状态转移方程、基本方程、指标函数、最优指标函数第1页/共59页建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：0)(1 ,2,

2、 1,)()(max)(11110nnkkkksxkksfnnksfxgsfkk其状态转移方程为其状态转移方程为: :kkkxss1 由于由于 与与 都是连续变量，当各阶段指标都是连续变量，当各阶段指标 没没有特殊性而较为复杂时，有特殊性而较为复杂时， 要求出要求出 会比较困难，因而求会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把连续变量全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下：离散化的办法求其数值解。具体做法如下： kskx)(kkxg)(kksf第2页/共59页（1 1） 令令 ，把区间把区间 0 0，aa进行分割，进行分

3、割， 的大小可的大小可依据问题所要求的精度以及计算机的容依据问题所要求的精度以及计算机的容量来定。量来定。 amsk,2,0第3页/共59页 (2) (2) 规定状态变量规定状态变量 及决策变量及决策变量 只在离散点只在离散点 上取值，相应的指标上取值，相应的指标函数函数 就被定义在这些离散值上，于是递推方就被定义在这些离散值上，于是递推方程就变为：程就变为： kskxam,2,0)(kksf0)()()(max)(111,2, 1 ,0nnkkkqpkksfpsfpgsf其中 pxsqkk,第4页/共59页 作为离散化例子，在例作为离散化例子，在例5 5中规定状态变量和决中规定状态变量和决策

4、变量只在给出的离散点上取值，见例策变量只在给出的离散点上取值，见例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 递 推 求按 逆 序 方 法 ， 逐 步 递 推 求出出 ，最后求出最，最后求出最优资金分配方案。优资金分配方案。)(,),(11sfsfnn第5页/共59页问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大? ?23332221112)(,9)(,4)(xxgxxgxxg例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为：时，其效益分别

5、为： 第6页/共59页例例6 6 连续变量的离散化解法连续变量的离散化解法)3,2, 1(,010.294max3212321ixxxxtsxxxZi第7页/共59页解解 令令 ，将区间，将区间00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六个点，即状态变量六个点，即状态变量 集合为集合为 2ks10,8,6,4,2,0允许允许决策集合为决策集合为 ， 与与 均在分割点上取值。均在分割点上取值。 kksx0kxks动态规划基本方程为：动态规划基本方程为： 0)(1 ,2, 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk当当k=3k=3时，时，

6、 230332max)(33xsxsf第8页/共59页式中式中 与与 的集合均为：的集合均为： 计算结果见表计算结果见表7-17-1。 3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810当k=3时， 表7-1 230332max)(33xsxsf第9页/共59页当k=2时， )(9max)(223202222xsfxsfsx0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk计算结果见表计算结果见表7-27-2。 2s2x32fg 2f*2x024681000 20 2 40 2 4 60 2 4

7、6 80 2 4 6 8 1008 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 900 18 36 72 128 2000 24 0 0 0表表7-2 7-2 第10页/共59页当k=1时， 0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk计算结果见表计算结果见表7-37-3。 表7-3 )(4max)(1121100111xsfxsfx1s1x21fg 1f*1x 10 101010 10100246810200136886050402000第11页/共59页最大收益为最大收益为 ，与

8、例，与例5 5结论完全相同。结论完全相同。 10,0,0*3*2*1xxx200)10(1f计算结果表明，最优决策为：计算结果表明，最优决策为： 应指出的是：这种方法有可能丢失最优解，应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。一般得到原问题的近似解。 第12页/共59页一、背包问题一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重一位旅行者携带背包去登山，已知他所能承受的背包重量限度为量限度为a kg，现有，现有n种物品可供他选择装入背包，第种物品可供他选择装入背包，第i种种物品的单件重量为物品的单件重量为ai kg，其价值是携带数量，其价值是携带数量xi的函数

9、的函数ci(xi)(i=1,2,n)，问旅行者应如何选择携带各种物品的件，问旅行者应如何选择携带各种物品的件数，以使总价值最大？数，以使总价值最大？ ), 2 , 1(0)(max11nixaxaxcziniiiniii且为整数第13页/共59页例例1 有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载的卡车，用以装载3种货物，种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？使总价值最大？ ) 3 , 2 , 1(010543654max321321ixxxxxxxzi且为整数货物编号i123单位重量(t)3

10、45单位价值ci456逆序解法：逆序解法：阶段阶段k： k=1,2,3状态变量状态变量sk:第第k阶段可以装载第阶段可以装载第k种到第种到第3种货物的重量。种货物的重量。决策变量决策变量xk:决定装载第决定装载第k种货物的数量。种货物的数量。状态转移方程状态转移方程:sk+1=sk-akxk最优指标函数最优指标函数fk(sk):当可装载重量为当可装载重量为sk,装载第装载第k种到第种到第3种货物所获得的种货物所获得的最大价值。最大价值。基本方程：基本方程：0)(1 , 2 , 3)()(max)(4411/ , 1 , 0sfksfxcsfkkkkasxkkkkk第14页/共59页当阶段k=3

11、时，有6max)(35/, 03333xsfsxs3012345678910 x3000000101010101012c3+f40000006060606060612f3000006666612x3*00000111112当阶段k=2时，有)(5max)(3324/, 02222sfxsfsx s2012345678910 x2000001010101012012012c2+f3000005+0656565651065+610125+610f200005666101112x2*000010002102234xss第15页/共59页当阶段k=1时，有)(3max)(2213/10, 0111sf

12、xsfx s110 x10123c1+f3124+68+512f213x1*21123xss第16页/共59页二、生产经营问题 在生产和经营管理中，经常遇到如何合在生产和经营管理中，经常遇到如何合理地安排生产计划、采购计划以及仓库的存理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。货计划和销售计划，使总效益最高的问题。下面通过例子来说明对不同特点问题的不同下面通过例子来说明对不同特点问题的不同处理技巧处理技巧。 第17页/共59页例2 生产与存贮问题 某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月某工厂生产并销售某种产品，已知今后四个月市场需求预测

13、如表，又每月生产生产j单位产品费用为：单位产品费用为： )()6,2, 1(3)0(0)(千元jjjjC 每月库存每月库存j j单位产品的费用为单位产品的费用为 ，该厂最大库存容量为该厂最大库存容量为3 3单单位，每月最大生产能力为位，每月最大生产能力为6 6单位，计划开始和计划期末库存量都是单位，计划开始和计划期末库存量都是零零。试制定试制定四个月四个月的生产计划，在满足用户需求条件下总费用最小。假设第的生产计划，在满足用户需求条件下总费用最小。假设第i+1i+1个月的库个月的库存量是第存量是第i i个月个月可销售量可销售量与该月用户需求量之差；而第与该月用户需求量之差；而第i i个月的可销

14、售量是本个月的可销售量是本月初库存量与产量之和。月初库存量与产量之和。 )(5 . 0)(千元jjE)(月i)(需求ig12342324第18页/共59页用动态规划方法求解时，对有关概念作如下分析：用动态规划方法求解时，对有关概念作如下分析：(1) (1) 阶段：每个月为一个阶段，阶段：每个月为一个阶段，k k1 1，2 2，3 3，4 4。 (2) (2)状态变量：状态变量： 为第为第k k个月初的库存量。个月初的库存量。 ks(3)(3)决策变量：决策变量： 为第为第k k个月的生产量。个月的生产量。 ku(4)(4)状态转移方程：状态转移方程： kkkkguss1(5)(5)最优指标函数

15、：最优指标函数： 表示第表示第k k月状态为月状态为 时，采取时，采取最佳策略生产，从本月到计划结束最佳策略生产，从本月到计划结束( (第第4 4月末月末) )的生产与存贮最的生产与存贮最低费用。低费用。（6 6）基本方程：）基本方程： )(kksfks0)(1 , 2 , 3 , 4)()()(min)(5511sfksfsEuCsfkkkkukkk第19页/共59页 k4，s5=s4+u4-g4=0，所以，所以u4=g4-s4=4-s4，s4可取可取0，1，2，3。 0)()(min)(443 , 2, 1 , 0444sEuCsfus40123u44321C+E+f576+0.55+14

16、+1.5f476.565.5u4*4321 k3，s4=s3+u3-g3，所以，所以u3=s4+ g3-s3，s3可取可取0，1，2，3。 s30123u3234512340123012C+E+f45+76+6.57+68+5.54.5+75.5+6.56.5+67.5+5.51+75+6.56+67+5.51.5+6.55.5+66.5+5.5f31211.588u3*2100第20页/共59页 k2，s3=s2+u2-g2，所以，所以u2=s3+ g2-s2， s2可取可取0，1，2，3。 s20123u23456234512340123C+E+f36+127+11.58+89+85.5+

17、126.5+11.57.5+88.5+85+126+11.57+88+81.5+125.5+11.56.5+87.5+8f21615.51513.5u2*5430 k1，s2=s1+u1-g1，所以，所以u1=s2+ g1-s1， s1可取可取0。 s10u12345C+E+f25+166+15.57+158+13.5f121u1*2反推回去，反推回去， u1*=2，u2*=5，u3*=0，u4*=4。第21页/共59页例3 3 采购与销售问题 某商店在未来的某商店在未来的4 4个月里，准备利用它的一个仓库来专门经销某种商个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能贮存这种商

18、品品，仓库最大容量能贮存这种商品l000l000单位。假定该商店每月只能出卖仓单位。假定该商店每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如表个月的买卖价格如表7 7_12_12所示，假定商店在所示，假定商店在1 1月开始经销时，仓库贮有该月开始经销时，仓库贮有该商品商品500500单位。试问若不计库存费用，该商店应如何制定单位。试问若不计库存费用，该商店应如何制定1 1月至月至4 4月的订购月的订购与销售计划，使预期获利最大。与销售计划，使预期获利最大。 月份（k）购买单价（ck）

19、销售单价（pk）110122983111341517第22页/共59页解 按月份划分为4个阶段，k=l，2，3，4状态变量 ：第k月初时仓库中的存货量(含上月订货)。决策变量 ：第k月卖出的货物数量。 ：第k月订购的货物数量。 状态转移方程： kskxky最优指标函数 ：第k k月初存货量为 时，从第k k月到4 4月末所获最大利润。则有逆序递推关系式为： kkkkxyss1)(kksfks0)(1 , 2 , 3 , 4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk第23页/共59页当k=4时 显然，决策应取 时才有最大值1517max)(4

20、4)(1000004444444yxsfxsysx0,*44*4ysx44417)(ssf0)(1 , 2 , 3 , 4)(max)(5511)(100000sfksfycxpsfkkkkkkxsysxkkkkkkk第24页/共59页当k=3时 这个阶段需解一个线性规划问题： 1764max)(171113max)(1113max)(333)(10000033333)(1000004433)(10000033333333333333333syxxysyxsfyxsfxsysxxsysxxsysx因为只有两个变量x3, y3 ，可以用图解法，也可以用单纯形法，求解得到： 时有最大值 0,100

21、01764max3333333333yxsxysxsyxz1000,*33*3ysx333136000)(ssf第25页/共59页当k=2时 求解线性规划问题： 得45136000max)(13600098max)(98max)(222)(10000022222)(100000222322)(10000022222222222222222yxsxysyxxysfyxsfxsysxxsysxxsysx0,100045136000max2222222222yxsxysxyxsz2222291000044000136000)(ssssf2*2*21000,0syx第26页/共59页当k=1时 求解一

22、个线性规划问题： 得)(1012max)(111211)(1000001111111xysfyxsfxsysx 5001s145003max)(9100001012max)500(115000500011111500050001111111yxxysyxfxyxxyx0,500500314500max1111111yxxyxyxz16000500314500)500(, 0,5001*1*1fyx第27页/共59页最优策略见下表。最大利润为1600016000。 月份期前存货售出量购进量15005000200100031000100010004100010000第28页/共59页例例4 4 限

23、期采购问题限期采购问题( (随机型随机型) ) 某部门欲采购一批原料，原料价格在五周内可能有某部门欲采购一批原料，原料价格在五周内可能有所变动，已预测得该种原料今后五周内取不同单价的概所变动，已预测得该种原料今后五周内取不同单价的概率如表率如表7-147-14所示。试确定该部门在五周内购进这批原料所示。试确定该部门在五周内购进这批原料的最优策略，使采购价格的的最优策略，使采购价格的期望值期望值最小。最小。 原材料单价（元）概率5006007000.30.30.4表7-14 第29页/共59页 阶段阶段k k：可按采购期限可按采购期限( (周周) )分为分为5 5段，段，k k1 1，2 2，3

24、 3，4 4，5 5。 状态变量状态变量 ：第：第k k周的原料实际价格。周的原料实际价格。 kx 决策变量 ：第k周如采购 则 1，若不采购 则 =0 =0。 另外用 表示：当第k周决定等待，而在以后采购时的采购价格期望值。 最优指标函数 ：第k周实际价格为 时，从第k周至第5周采取最优策略所花费的最低期望价格。则有逆序递推关系式为： )(kksfks解解 本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而本例与前面所讨论的确定型问题不同，状态的转移不能完全确定，而按某种已知的按某种已知的概率分布概率分布取值，即属于取值，即属于随机型随机型动态规划问题。动态规划问题。 kskxkx

25、kES)17. 7()()17. 7(1 , 2 , 3 , 4,min)(55555bDsssfakDsSssfkkkEkkkkD为状态集合500，600，700。 第30页/共59页当k=5时 因为若前四周尚未购买，则无论本周价格如何，该部门都必须购买，所以 )( 1700700)( 1600600)( 1500500)5(5*55*55*55采购当采购当采购当xsxsxssf第31页/共59页当k=4时 由于 所以 6107004 . 06003 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 05554fffSE610,min,min)(4444444s

26、SssfEDs)(0700610)( 1600600)( 1500500*44*44*44等待当采购当采购当xsxsxs第32页/共59页当k=3时 由于 所以 5746104 .06003 .05003 .0)700(4 .0)600(3 .0)500(3 .04443fffSE574,min,min)(3333333sSssfEDs07006005741500500*33*33xsxs或当当第33页/共59页当k=2时 同理 8 .551,min,min)(22222sSssfE07006008 .5511500500*22*22xsxs或当当第34页/共59页当k=1时 26.536,m

27、in,min)(11111sSssfE070060026.5361500500*11*11xsxs或当当第35页/共59页 所以，最优采购策略为：若第一、二、三周原料价格所以，最优采购策略为：若第一、二、三周原料价格为为500500，则立即采购，否则在以后的几周内再采购。若第四，则立即采购，否则在以后的几周内再采购。若第四周价格为周价格为500500或或600600，则立即采购，否则等第五周再采购。，则立即采购，否则等第五周再采购。而第五周时无论当时价格为多少都必须采购。而第五周时无论当时价格为多少都必须采购。 按照以上策略进行采购，期望价格为：按照以上策略进行采购，期望价格为： 525382

28、.52526.5364 . 026.5363 . 05003 . 0)700(4 . 0)600(3 . 0)500(3 . 0)(11111fffsf第36页/共59页三、设备更新问题 从经济上分析，一台设备应该从经济上分析，一台设备应该 使用多少年更新最使用多少年更新最合算，这就是设备更新问题。一般来说，一台设备在比合算，这就是设备更新问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多少，故障变多, ,维修费用

29、增加。如果更新可提高年净收维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费，为了比较入，但是当年要支出一笔数额较大的购买费，为了比较不同决策的优劣，常常要在一个较长的时间内考虑更新不同决策的优劣，常常要在一个较长的时间内考虑更新决策问题。决策问题。 第37页/共59页 设备更新问题一般提法：在已知一台设备的效益函数r(t)，维修费用函数u(t)及更新费用函数c(t)条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年总效益最大。 rk(t)：在第k年设备已使用过t年(或称役龄为t年)，再使用1年时的效益。 uk(t) ：在第k年设备役龄为t年

30、，再使用一年的维修费用。 ck(t) ：在第k年卖掉台役龄为t年的设备，买进一台新设备的更新净费用。 为折扣因子(01) ，表示一年以后的单位收入价值相当于现年的 单位。 第38页/共59页动态规划模型阶段变量k：k=1,2,n，表示计划使用该设备的年限数。 状态变量sk: 第k年初，设备已使用过的年数，即役龄。决策变量xk: 是第k年初更新（Replacement），还是保留使用（keep）旧设备，分别用R与K表示。 状态转移方程为： 阶段指标为： 111kkssRxKxkk当当指标函数为： )()0()0()()(),(kkkkkkkkkkjscursusrxsvRxKxkk当当), 2

31、, 1(),(,nkxsvVnkjkkjnk第39页/共59页 最优指标函数fk(sk)表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，则可得如下的逆序动态规划方程： 实际上， 0)()(),(max)(1111nnkkkkRKkkksfsfxsvxsfk或)18. 7()18. 7(ba)()()0()0()()()(max)(1111kkkkkkkkkkkkkksfscursfsusrsfRxKxkk当当第40页/共59页例例5 5 设某台新设备的年效益及年均维修费、更新净费用如表设某台新设备的年效益及年均维修费、更新净费用如表7-7-1515所示。试确定今后所示。试确定今

32、后5 5年内的更新策略，使总收益最大。年内的更新策略，使总收益最大。（设（设 ） 1)(trk)(tuk)(tck役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5第41页/共59页解 如前述建立动态规划模型，n=5 当k=5时， )()0()0()()(max)(5555555555scursusrsfRxKx55当当状态变量s5可取1，2，3，4。 )1 ()0()0() 1 () 1 (max) 1 (555555cururfRxKx55当当5 . 35 . 15 . 0515 . 4maxK) 1 (x5当=2.5

33、2 . 25 . 055 . 14max)2(5fK)2(x5当=2 5 . 25 . 05275. 3max)3(5fR)3(x5当=1.5 35 .055 .23max)4(5fR)2(x5当 役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5第42页/共59页当k=4时， 状态变量s4可取1，2，3。 = 6.5 役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(5444445444444fscur

34、sfsusrsfRxKx44当当) 1 (4f5 . 35 . 15 . 055 . 215 . 4maxR) 1 (x4当)2(4f=5 . 32 . 25 . 05215 . 4max= 5.8 R)2(x4当) 3(4f=5 . 35 . 25 . 055 . 1275. 3max= 5.5 R) 3(x4当第43页/共59页当k=3时， 状态变量s3可取1，2。 = 9.5 役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5) 1 ()()0()0() 1()()(max)(4333334333333fscursfs

35、usrsfRxKx33当当) 1 (3f5 . 65 . 15 . 058 . 515 . 4maxR) 1 (x3当)2(3f=5 . 62 . 25 . 055 . 515 . 4max= 8.8 R)2(x3当第44页/共59页当k=2时， 状态变量s2只能取1 役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5= 12.5 ) 1 ()()0()0() 1()()(max)(3222223222222fscursfsusrsfRxKx22当当) 1 (2f5 . 95 . 15 . 058 . 815 . 4maxR

36、) 1 (x2当第45页/共59页当k=1时， 状态变量s1只能取0 役龄项目012345效益54.543.7532.5维修费0.5 11.522.53更新费0.51.52.22.533.5= 17 ) 1 ()()0()0() 1()()(max)(2111112111111fscursfsusrsfRxKx11当当5 .125 . 05 . 055 .125 . 05max)0(1fKx)0(1第46页/共59页 上述计算递推回去，当 时，由状态转移方程， 则 则查 得：状态 ，查： Kx)0(1RxRxfsKxss1*2221121)1 (11得，查知RxsKxss23223111推出)

37、 1 (3fRx *3推出 ，查 14s) 1 (4fRx *415s) 1 (5fKx *5最优策略为： ，即第一年初购买的设备到第二、三、四年初各更新一次，用到第5年末，其总效益为17万元。 KRRRK,第47页/共59页 k5，s5可取可取1,2,3,4。 s51234u5KRKRKRKRv5+f64.5-15-0.5-1.54-1.55-0.5-2.23.75-25-0.5-2.53-2.55-0.5-3f53.52.521.5u5*KKRR k4, s4可取可取1,2,3。 s4123u4KRKRKRv4+f54.5-1+2.55-0.5-1.5+3.5 4-1.5+25-0.5-2

38、.2+3.53.75-2+1.55-0.5-2.5+3.5f46.55.85.5u4*RRR第48页/共59页 k3，s3可取可取1,2。 s312u3KRKRv3+f44.5-1+5.85-0.5-1.5+6.54-1.5+5.55-0.5-2.2+6.5f49.58.8u4*RR k2, s2可取可取1。 s21u2KRv3+f24.5-1+8.85-0.5-1.5+9.5f212.5u2*R k1, s2可取可取0。 s10u1KRv1+f25-0.5+12.55-0.5-0.5+12.5f117u1*K第49页/共59页 货郎担问题一般提法为：一个货郎从某货郎担问题一般提法为：一个货郎

39、从某城镇出发，经过若干个城镇一次，且仅一次，城镇出发，经过若干个城镇一次，且仅一次，最后仍回到原出发的城镇，问应如何选择行最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个走路线可使总行程最短，这是运筹学的一个著名问题，实际中有很多问题可以归结为这著名问题，实际中有很多问题可以归结为这类问题。类问题。四、货郎担问题第50页/共59页 设设 是已知的是已知的n n个城镇，城镇个城镇，城镇 到城到城镇镇 的距离为的距离为 ，现求从，现求从 出发，经各城镇一出发，经各城镇一次且仅一次返回次且仅一次返回 的最短路程。若对的最短路程。若对n n个城镇进行排个城镇进行排列，有列，

40、有 (n(n一一1)!1)!2 2种方案，所以穷举法是不现种方案，所以穷举法是不现实的，这里介绍一种动态规划方法。实的，这里介绍一种动态规划方法。 货郎担问题也是求最短路径问题，但与例货郎担问题也是求最短路径问题，但与例4 4的最短的最短路问题有很大不同，建动态规划模型时，虽然也可按城路问题有很大不同，建动态规划模型时，虽然也可按城镇数目镇数目n n将问题分为将问题分为n n个阶段。但是状态变量不好选择，个阶段。但是状态变量不好选择，不容易满足无后效性。为保持状态间相互独立，可按以不容易满足无后效性。为保持状态间相互独立，可按以下方法建模：下方法建模：nvvv,21jvijd1viv1v第51页/共59页 设设S S表示从表示从 到到 中间所有可能经过的城中间所有可能经过的城市集合，市集合，S S实际上是包含除实际上是包含除 与与 两个点之外其两个点之外其余点的集合，但余点的集合，但S S中的点的个数要随阶段数改变。中的点的个数要随阶段数改变。 状态变量状态变量 表示：从表