8.问题四的解答
8.1模型的建立
在第二问的基础上，我们讨论四个组的情况，运用控制变量法对所要讨论的变量进行讨论。并令时间复杂度为a=10%，若变量变化时而时间复杂度小于等于10%，则认为对巡视路线没有影响，以此来确定变量的变化范围。所以建立的目标函数为：
maxKi?minKj?a?,i,j?1,2,3,4?maxKi? ??K?aT?bt?w(ci）,i?1,2,3,4iii?V?令maxKi?aiT?bti?w(cj）w(ci）,minKj?ajT?bjt?，所以 VVw(ci）maxKiaiT?bt?iV假设时间均衡度a<10%时，最佳巡视路线不会改变，假设第i组巡视时间最长，第j组巡视时间最短，分三种情况进行讨论： 1：T，t不变，由a<10%,可以得出
a?maxKi?minKj?(ai?aj)T?(bi?bj)t?w(ci)?w(cj)V
V?[T(0.9ai?aj)?t(0.9bi?bj)]?w(cj)?0.9w(ci)
2：T,V不变，由a<10%,可以得出
t?V(0.9bi?bj)?w(cj)?0.9w(ci)?VT(aj?0.9ai)
3：V,t不变，由a<10%,可以得出
T?V(0.9ai?aj)?w(cj)?0.9w(ci)?Vt(bj?0.9bi)
8.1.1综上所述得到问题三的最优化模型为
maxKi?minKj?,i,j?1,2,3,4?a?maxKi? ??K?aT?bt?w(ci）,i?1,2,3,4iii?V?8.2模型的求解
在问题四中分四组情况时求得时间均衡度为，我们假定时间??10%，运用控制变量法，分三组进行讨论，每次控制两个变量不变，一个变量变动，最后求得求得结果如图15
16
T和t不变时 8.82?V?35 T和V不变时 0.69 t和V不变时 2 当T和t不变时，V只能变小，可以减小到8.82公里/小时，此时的最佳巡视路径不变。 当T和V不变时，t只能减小，可以减小到0.69小时，此时的最佳巡视路线不变。 当t和V不变时,T只能增大，可以增大到2.67小时，此时的最佳巡视路线不变。 9.模型的评价、改进及推广 9.1模型的评价 9.1.1模型的优点： (1)把灾情巡视问题看作旅行员推销问题，便于快速解决问题。 (2)运用Kruskal算法画出最小生成树，再根据近似算法使得问题简化。 9.1.2模型的缺点： (1)模型中的计算都只是近似计算，不能够保证所求的解为最优解。 (2)缺乏严格的理论基础。 (3)模型求解过程中存在经过一个点多次的情况。 (4)在分组时凭借经验划分可能存在不合理现象。 9.2模型的改进 (1)先利用计算机仿真巡视过程后再进行求解可使结果更准确。 (2)所建立的模型没有考虑到意外情况，我们可以先调查统计对意外情况发生的概率及所产生的影响进行综合考虑后再优化模型。 9.3模型的推广 该图论模型可以广泛应用于物理学控制论、信息论、工程技术。交通运输、经济管理、电子计算机等各领域。对于科学研究、市场和社会中的许多问题，可以用该模型来解决。例如各种通信线路的架设、输油管道的铺设、铁路或者公路 17 交通图的合理布局等问题都可应用该图论模型的方法，简便，快速地加以解决。 10.参考文献 [1]王朝瑞.图论[M]，北京：北京工业学院出版社.1987年。 [2]李当志.数学建模竞赛教程[M].南京：江苏教育出版社.1996年。 [3]姜启源.数学模型[M].北京：高等教育出版社.1987年。 [4]卢开澄.图论及其应用.北京：清华大学出版社.1981年。 11.附录 附录1：最小生成树源程序： b=[1,1,1,1,2,2,2,3,3,3,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,9,9,10,11,11,11,12,12,12,13,13,13,13,14,14,14,15,15,16,16,17,17,17,18,18,18,19,19,19,20,20,20,20,21,21,21,21,22,22,22,23,23,23,23,24,24,24,25,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29,30,30,31,31,31,32,32,32,32,33,33,33,33,34,34,34,35,35,35,36,36,36,36,36,36,37,37,37,37,37,38,38,38,38,39,39,39,39,40,40,40,40,41,41,41,41,42,42,42,43,43,43,44,44,45,45,45,45,45,46,46,46,46,46,47,47,47,47,48,48,48,48,49,49,49,49,49,50,50,50,50,50,51,51,51,51,52,52,52,53,53,53,53;36,37,38,39,3,5,36,2,39,40,8,40,2,6,40,49,5,7,48,49,6,40,41,48,4,41,41,42,42,41,43,46,42,43,44,14,43,45,46,13,15,44,14,45,17,45,16,22,47,45,46,47,20,46,48,19,21,25,48,20,23,25,47,17,23,47,21,22,24,50,23,27,50,20,21,49,50,27,50,51,24,26,28,27,51,52,51,52,53,32,52,32,33,53,30,31,33,35,31,32,35,37,35,37,38,32 18 ,33,34,1,2,39,49,51,53,1,33,34,38,53,1,34,37,39,1,3,36,38,3,4,5,7,7,8,9,11,9,10,12,11,12,13,12,14,13,15,16,18,46,11,13,18,19,45,17,18,21,22,6,7,19,20,5,6,25,36,50,23,24,25,26,49,26,28,29,36,28,29,30,29,31,36,37;6,10.3,5.9,11.2,4.8,8.3,9.2,4.8,7.9,8.2,20.4,12.7,8.3,9.7,11.3,11.4,9.7,7.3,11.8,9.5,7.3,15.1,7.2,14.5,20.4,8,7.8,5.6,10.8,14.2,6.8,13.2,12.2,7.8,10.2,8.6,8.6,16.4,9.8,8.6,15,9.9,15,8.8,6.8,11.8,6.8,6.7,9.8,8.2,8.2,9.2,9.3,8.1,7.2,9.3,7.9,6.5,5.5,7.9,9.1,7.8,4.1,6.7,10,10.1,9.1,10,8.9,7.9,8.9,18.8,13.2,6.5,7.8,12,8.8,7.8,10.5,10.5,18.8,7.8,7.9,7.9,12.1,8.3,15.2,7.2,7.9,10.3,7.7,8.1,7.3,9.2,10.3,8.1,19,14.9,7.3,19,20.3,7.4,8.2,11.5,17.6,14.9,20.3,8.2,6,9.2,11.5,19.8,10.1,12.9,10.3,7.4,11.5,12.2,8.8,5.9,17.6,12.2,11,11.2,7.9,11.5,11,8.2,12.7,11.3,15.1,7.2,8,7.8,14.2,5.6,10.8,12.2,6.8,7.8,8.6,10.2,9.9,16.4,8.8,11.8,8.2,15.8,13.2,9.8,8.2,8.1,15.8,9.8,9.2,4.1,10.1,11.8,14.5,7.2,5.5,11.4,9.5,12,19.8,14.2,7.9,13.2,8.8,10.5,14.2,10.5,12.1,15.2,10.1,8.3,7.2,7.7,7.9,9.2,12.9,8.8;]; [B,i]=sortrows(b',3);B=B'; m=size(b,2);n=53; t=1:n; k=0; T=[ ]; c=0; for i=1:m if t(B(1,i))~=t(B(2,i)) k=k+1; T(k,1:2)=B(1:2,i), c=c+B(3,i) tmin=min(t(B(1,i)),t(B(2,i))); tmax=max(t(B(1,i)),t(B(2,i))); for j=1:n if t(j)==tmax t(j)=tmin; end end end if k==n-1 break ; end end T,c 附录2：问题一及问题二的Lingo程序 model: sets: city / 1.. 19/: u; link( city, city): dist, ! 距离矩阵; x; endsets n = @size( city); data: !距离矩阵，它并不需要是对称的; 19 dist = 0 6 6 0 14 34.9 34.5 49.7 49.5 65.9 55.9 67.3 64.1 72.7 11.9 11.5 22.2 41.7 55.1 62.7 77.5 19.1 40 40.5 55.7 55.5 71.9 61.9 73.3 70.1 78.7 5.9 11.2 27.3 47.7 61.1 68.7 83.5 20.9 23.3 38.5 38.3 54.7 44.7 56.1 59.7 68.3 18.9 7.9 8.2 30.5 43.9 51.5 66.3 27.8 20.4 36.2 52.6 42.6 54 58 66.6 39.8 28.8 12.7 28.4 41.8 49.4 64.2 15.2 15 31.4 21.4 32.8 36.8 45.4 42.2 31.2 15.1 7.2 20.6 28.2 43 15.8 32.2 22.2 33.6 37.6 46.2 57.4 46.4 30.3 8 21.4 29 43.8 16.4 22 17.8 34.2 37.9 57.2 46.2 30.1 7.8 5.6 25.6 28 37.6 23 39.4 43.1 73.6 62.6 46.5 24.2 10.8 30.8 33.2 14.6 15.4 24 63.6 52.6 36.5 14.2 26.8 6.8 24.8 16.4 20.1 75 64 47.9 25.6 12.2 7.8 10.2 8.6 76 67.6 51.9 29.6 28.6 8.6 18.5 84.6 76.2 60.5 38.2 32.3 17.2 9.9 11 27.1 49.4 62.8 70.4 85.2 16.1 38.4 51.8 59.4 74.2 22.3 35.7 43.3 58.1 13.4 21 35.8 20 22.4 18 14 19.1 0 34.9 40 20.9 0 34.5 40.5 23.3 27.8 0 49.7 55.7 38.5 20.4 15.2 0 49.5 55.5 38.3 36.2 15 15.8 0 65.9 71.9 54.7 52.6 31.4 32.2 16.4 0 55.9 61.9 44.7 42.6 21.4 22.2 22 37.6 0 67.3 73.3 56.1 54 32.8 33.6 17.8 23 14.6 0 64.1 70.1 59.7 58 36.8 37.6 34.2 39.4 15.4 16.4 0 72.7 78.7 68.3 66.6 45.4 46.2 37.9 43.1 24 20.1 8.6 0 11.9 5.9 18.9 39.8 42.2 57.4 57.2 73.6 63.6 75 76 84.6 0 11.5 11.2 7.9 28.8 31.2 46.4 46.2 62.6 52.6 64 67.6 76.2 11 0 41.7 47.7 30.5 28.4 7.2 8 22.2 27.3 8.2 12.7 15.1 30.3 30.1 46.5 36.5 47.9 51.9 60.5 27.1 16.1 0 7.8 24.2 14.2 25.6 29.6 38.2 49.4 38.4 22.3 0 55.1 61.1 43.9 41.8 20.6 21.4 5.6 10.8 26.8 12.2 28.6 32.3 62.8 51.8 35.7 13.4 0 62.7 68.7 51.5 49.4 28.2 29 25.6 30.8 6.8 7.8 8.6 17.2 70.4 59.4 43.3 21 20 0 ; !随机产生，这里可改为你要解决的问题的数据; enddata !目标函数; min = @sum( link: dist * x); @FOR( city( K): !进入城市K; @sum( city( I)| I #ne# K: x( I, K)) = 1; !离开城市K; @sum( city( J)| J #ne# K: x( K, J)) = 1; ); !保证不出现子圈; @for(city(I)|I #gt# 1: @for( city( J)| J#gt#1 #and# I #ne# J: u(I)-u(J)+n*x(I,J)<=n-1); ); !限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解; @for(city(I) | I #gt# 1: u(I)<=n-2 ); !定义X为0\\1变量; @for( link: @bin( x)); 77.5 83.5 66.3 64.2 43 43.8 28 33.2 24.8 10.2 18.5 9.9 85.2 74.2 58.1 35.8 22.4 18 0 附录三：问题三的Matlab程序 clc clear xhot=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, 20