管理运筹学案例3.docxVIP

第一问： 1.枚举法 路线 路程 总路程 路线 路程 总路程 ABCDEA 11+4+7+3+3 28 ACBDEA 7+4+5+3+3 22 ABCEDA 11+4+8+3+5 31 ACBEDA 7+4+8+3+5 27 ABDCEA 11+5+7+8+3 34 ACDBEA 7+7+6+8+3 31 ABDECA 11+5+3+8+7 34 ACDEBA 7+7+3+8+10 35 ABECDA 11+8+8+7+5 39 ACEBDA 7+8+8+5+5 33 ABEDCA 11+8+3+7+7 36 ACEDBA 7+8+3+6+10 34 ADBCEA 4+6+4+8+3 25 AEBCDA 5+8+4+7+5 29 ADBECA 4+6+8+8+7 33 AEBDCA 5+8+5+7+7 32 ADCEBA 4+7+8+8+10 37 AECDBA 5+8+7+6+10 36 ADCBEA 4+7+4+8+3 26 AECBDA 5+8+4+5+5 27 ADECBA 4+3+8+4+10 29 AEDBCA 5+3+6+4+7 25 ADEBCA 4+3+8+4+7 26 AEDCBA 5+3+7+4+10 29 由上表可以得出最短路线为：A—C—B—D—E—A，此时的总路程为 7+4+5+3+3=22（公里）， 所以我们通过枚举法得出最短配送路线为：A—C—B—D—E—A，其最短总路程为 22 公里。 2.动态规划法 采用动态规划的方法，从 A 地出发，经过 B、C、D、E 之后回到 A 地， A、B、C、D、E五地分别用数字 1、2、3、4、5 表示，将问题分为 5 个阶段，用 k 表示， dij 表示从 i 地到 j 地的距离，Si 表示到达 i 城市之前，中途所经过的城市的集合， Fk{i，Si}表示从 A 地开始，经过 k-1 个中间城市的 Si 集合到达 i 地的最短路线： 1、 当 k=1 时，从 A 地出发，到 B、C、D、E 地： F1{2}=11；F1{3}=7；F1{4}=4；F1{5}=5 2、 当 k=2 时，从 A 地车发，中间经过一个城市到达 i 程的最短路程为： F2{2，{3}}= F1{3}+d32=7+4=11 F2{2，{4}}= F1{4}+d42=4+6=10 F2{2，{5}}= F1{5}+d52=5+8=13 F2{3，{2}}= F1{2}+d23=11+4=15 F2{3，{4}}= F1{4}+d43=4+7=11 F2{3，{5}}= F1{5}+d53=5+8=13 F2{4，{2}}= F1{2}+d24=11+5=16 F2{4，{3}}= F1{3}+d34=7+7=14 F2{4，{5}}= F1{5}+d54=5+3=8 F2{5，{2}}= F1{2}+d25=11+8=19 F2{5，{3}}= F1{3}+d35=7+8=15 F2{5，{4}}= F1{4}+d45=4+3=7 3、 当 k=3 时，即从 A 地出发，经过两个地方到达 i 地的最短路程为： F3{2，{3，4}}= min[F2{3，{4}}+d32，F2{4，{3}}+d42]=min[4+7+4，7+7+6] =min[15，20]=15 F3{2，{3，5}}= min[F2{3，{5}}+d32，F2{5，{3}}+d52]=min[5+8+4，7+8+8] =min[17，23]=17 F3{2，{4，5}}= min[F2{4，{5}}+d42，F2{5，{4}}+d52]=min[5+3+6，4+3+8] =min[14，15]=14 F3{3，{2，4}}= min[F2{2，{4}}+d23，F2{4，{2}}+d43]=min[4+6+4，11+5+7] =min[14，23]=14 F3{3，{2，5}}= min[F2{2，{5}}+d23，F2{5，{2}}+d53]=min[5+8+4，11+8+8] =min[17，27]=17 F3{3，{4，5}}= min[F2{4，{5}}+d43，F2{5，{4}}+d53]=min[5+3+7，4+3+8] =min[15，15]=15 F3{4，{2，3}}= min[F2{2，{3}}+d24，F2{3，{2}}+d34]=min[7+4+5，11+4+7] =min[16，22]=16 F3{4，{2，5}}= min[F2{2，{5}}+d24，F2{5，{2}}+d54]=min[5+8+5，11+8+3] =min[18，22]=18 F3{4，{3，5}}= min[F2{3，{5}}+d34，F2{5，{3}}+d54]=min[5+8+7，7+8+3] =min[20，18