自来水管的连接问题【教学参考】

《自来水管的连接问题【教学参考】》由会员分享，可在线阅读，更多相关《自来水管的连接问题【教学参考】（33页珍藏版）》请在装配图网上搜索。

1、自来水管连接问题的数学模型数学1101 崔瀚 20111370数学1101 崔蕃琳 20111387信计1102 陈曦 20111444自来水管连接问题的数学模型摘要本文研究的是自来水管连接问题，即如何铺设自来水管使得自来水管的总长度最小。我们利用Matlab软件，用最小生成树的方法求出了最短距离。关键词： 自来水管 最短 最小生成树1、问题重述在一个有限制区域的地区，有可数个用户，如何铺设自来水管，使得总的自来水管最短。当然，水管要涉及到每一个用户且不能穿过限制区域。2、模型假设假设用户直接所连接成的树形网络是属于同一个平面；假设不考虑钢管系统的首末站高度差；假设不考虑自来水管道的弯头；假设

2、所给出的坐标准确无误；3、符号说明4、问题分析我们将这个问题细化为了两个问题。问题一是，如何判断有效用户。有效用户指的是不在限制区域内的用户。问题二是，如何铺设管道使管道的总长度最短。问题二我们分两个步骤解决。首先，我们将所有用户点用最小生成树算法进行连接，这样我们就得到了最短的铺设方案。但是，这样铺设的管道有一些会穿过障碍区域，所以需要做进一步处理。其次，我们筛选无效线段。无效线段指的穿过障碍区域的管道线段。最后，我们将无效线段连接的两个点进行重新连接，即，将这两个用户点分别连接原来穿过那个障碍区域的一个顶点。5、模型建立与求解5.1模型一模型一要解决的是判断有效用户5.1.1构建障碍区域5

3、.1.1.1若障碍区域是三角形，则设三个顶点的坐标分别是A(x1, y1) B(x2,y2) C(x3,y3) 5.1.1.2若障碍区域是多边形，则依次设每个点的坐标是每个顶点与上一个顶点和第一个顶点组成的三角形进行判断。5.1.2判断有效用户设其中一个限制区域为三角形ABC，设用户点为，则一定存在p,q使得 ，如果，则在障碍区域内，为无效用户；反之，为有效用户。5.2模型二5.2.1不计障碍区域的最短距离 在不考虑障碍区时，问题二只是一个简单的求最小生成树问题。最小生成树问题，即分别求出每个点与其他点之间的距离，按照从小到大的顺序排列。排列之后从小到大选择连接的线段点，之后判断是否还有未连接

4、到的用户，并且不能重复连接用户，如果两个条件都成立，继续选择下一个点。直到连接到所有的用户。最后，简单的累加就可以算出铺设的自来水管的总长度。我们将模型一得到的有效用户，利用Matlab软件，和最小生成树算法，进行计算。最后我们画出了不计障碍区域的最短距离铺设自来水管的铺设图，并算出了最短的距离。最短距离为：639.4814。图 15.2.2障碍区域的处理5.2.2.1无效线段的判定我们定义表示穿过障碍区域的管道的线段为无效线段。从得到的图像我们可以明显看出来只有一条管道是穿过障碍区域的。但是实际的模型推广中，凭人工判断是低效的，所以我们设计了判断无效线段的算法。如果任意两个有效用户点的坐标分

5、别为A(x1,y1)、B(x2,y2)，同一障碍区任意两个顶点坐标为M(x3,y3)、N(x4,y4)。则两直线方程分别为：则由解线性方程组的方法有，线性方程组的的系数矩阵为： ；在运用Matlab求解该线性方程组时，不妨把 分别设为： 可以求得。若求得的交点坐标为P(x,y)，则通过向量关系PM=PN,可以求的。若0,则该线段为有效线段；若0,则要考虑向量关系PA=PB,若0，则该线段为有效线段，否则，该线段为无效线段。我们将上面求得的所有用户点之间的无效线段构造为一个集合，与之前最小生成树所用的线段构造为一个集合，两个集合的交集即为做最小生成树处理之后的无效线段5.2.2.2无效线段的处理

6、由于五边形可以由三个三角形组成，并且在本问题中只涉及穿过三角形障碍区域的无效线段，所以我们只讨论穿过三角形障碍的无效线段的处理方法。处理方法有两种，我们以下图为例三角形ABC为障碍区域，MN为两个有效用户点，线段MN为最小生成树生成的无效线段。该无效线段有两种较为有效的修改方案。第一，可以用线段MA,AN,代替。第二，可以用线段MB,BC,CN代替。即，两种替代方案本质上是加入辅助拐点的不同方法，并且有效拐点一定是限制区域的顶点，一种是加入A点，一种是加入B,C两点。这样，我们就可以做如下处理，对最小生成树程序加以修改。首先我们先去掉之前最小生成树结果中的无效线段。其次，我们判断加入的有效拐点

7、的坐标，重新做一次最小生成树。即可得到实际上最短的铺设结果。用Matlab求得最小结果为：642.1556。6、 参考文献1高等数学问题的matlab求解.高等教育出版社7、 MATLAB程序7.1筛选有效用户A=1.0000 95.0129 58.27922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0000 82.1407 52.

8、982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0000 92.1813 78.332914.0000 73.8207 68.084615.0000 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000 35.2868 30.4999

9、23.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20.2765 97.084527.0000 19.8722 99.008328.0000 60.3792 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5994 72.663236.0

10、000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2647 43.992440.0000 67.2137 93.338041.0000 83.8118 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.8892 62.988849.000

11、0 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000 68.2223 4.389553.0000 30.2764 2.718554.0000 54.1674 31.268555.0000 15.0873 1.286356.0000 69.7898 38.396757.0000 37.8373 68.311658.0000 86.0012 9.284259.0000 85.3655 3.533860.0000 59.3563 61.239561.0000 49.6552 60.854062.0000 89.9

12、769 1.576063.0000 82.1629 1.635564.0000 64.4910 19.007565.0000 81.7974 58.691866.0000 66.0228 5.758167.0000 34.1971 36.756868.0000 28.9726 63.145169.0000 34.1194 71.763470.0000 53.4079 69.266971.0000 72.7113 8.407972.0000 30.9290 45.435573.0000 83.8496 44.182874.0000 56.8072 35.325075.0000 37.0414 1

13、5.360676.0000 70.2740 67.564577.0000 54.6571 69.921378.0000 44.4880 72.750979.0000 69.4567 47.838480.0000 62.1310 55.484281.0000 79.4821 12.104782.0000 95.6843 45.075483.0000 52.2590 71.588384.0000 88.0142 89.284285.0000 17.2956 27.310286.0000 97.9747 25.476987.0000 27.1447 86.560388.0000 25.2329 23

14、.235089.0000 87.5742 80.487290.0000 73.7306 90.839891.0000 13.6519 23.189492.0000 1.1757 23.931393.0000 89.3898 4.975494.0000 19.9138 7.838495.0000 29.8723 64.081596.0000 66.1443 19.088797.0000 28.4409 84.386998.0000 46.9224 17.390099.0000 6.4781 17.0793100.0000 98.8335 99.4295;B=1 3.2060 12.91662 1

15、7.4571 19.33773 4.7576 20;C=1 50 302 53.7465 48.44903 46.9222 57.11955 43.1123 56.31874 33.3207 39.8050;D=1 54.6982 702 53.7465 903 46.9222 80;E=1 90 752 80 953 70 80;SIGN=zeros(1,100);%生成1行100列的记录矩阵，若点不在障碍区则对应位置记为1若否记0for n=1:100if(A(n,1)=4|A(n,1)=23|A(n,1)=36|A(n,1)=99)SIGN(n)=0else SIGN(n)=1enden

16、dSIGN;OUTSIGN=find(SIGN=0)p=0;for i=1:100 p=p+SIGN(i);endp7.2无障碍最小生成树clc,clearx=95.0129;23.1139;60.6843;89.1299;76.2097;45.6468;1.8504;82.1407;44.4703;61.5432;79.1937;92.1813;73.8207;17.6266;40.5706;93.547;91.6904;41.027;89.365;5.7891;35.2868;0.9861;13.8891;20.2765;19.8722;60.3792;27.2188;19.8814;1.

17、5274;74.6786;44.5096;93.1815;46.5994;84.6221;52.5152;20.2647;67.2137;83.8118;1.964;68.1277;37.9481;83.1796;50.2813;70.9471;42.8892;30.4617;18.9654;19.3431;68.2223;30.2764;54.1674;15.0873;69.7898;37.8373;86.0012;85.3655;59.3563;49.6552;89.9769;82.1629;64.491;81.7974;66.0228;34.1971;28.9726;34.1194;53

18、.4079;72.7113;30.929;83.8496;56.8072;37.0414;70.274;54.6571;44.488;69.4567;62.131;79.4821;95.6843;52.259;88.0142;17.2956;97.9747;27.1447;25.2329;87.5742;73.7306;13.6519;1.1757;89.3898;19.9138;29.8723;66.1443;28.4409;46.9224;98.8335;y=58.2792;42.3496;51.5512;43.2907;22.595;57.9807;76.0365;52.9823;64.

19、0526;20.9069;37.9818;78.3329;68.0846;46.1095;56.7829;79.4211;5.9183;60.2869;5.0269;41.5375;30.4999;1.5009;76.795;97.0845;99.0083;78.8862;43.8659;49.8311;21.3963;64.3492;32.0036;96.0099;72.6632;74.4566;26.7947;43.9924;93.338;68.3332;21.256;83.9238;62.8785;13.3773;20.7133;60.7199;62.9888;37.0477;57.51

20、48;45.1425;4.3895;2.7185;31.2685;1.2863;38.3967;68.3116;9.2842;3.5338;61.2395;60.854;1.576;1.6355;19.0075;58.6918;5.7581;36.7568;63.1451;71.7634;69.2669;8.4079;45.4355;44.1828;35.325;15.3606;67.5645;69.9213;72.7509;47.8384;55.4842;12.1047;45.0754;71.5883;89.2842;27.3102;25.4769;86.5603;23.235;80.487

21、2;90.8398;23.1894;23.9313;4.9754;7.8384;64.0815;19.0887;84.3869;17.39;99.4295;x1=3.206;17.4571;4.7576;3.0206;y1=12.9166;19.3377;20;12.9166;x2=33.3207;43.1123;46.9222;53.7465;50;33.3207;y2=39.805;56.3187;57.1195;48.449;30;39.805;x3=54.6982;53.7465;46.9222;54.6982;y3=70;90;80;70;x4=90;80;70;90;y4=75;9

22、5;80;75;a=zeros(96); for i=1:96 for j=1:96 a(i,j)=(x(i)-x(j)2+(y(i)-y(j)2)(1/2); end; end; a=a+a;a(find(a=0)=inf;result=;p=1;tb=2:length(a); while length(result)=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;end

23、result plot(x,y,.)hold;for i=1:95 b=result(1:2,i); plot(x(b),y(b)endplot(x1,y1,x2,y2,x3,y3,x4,y4)hold;7.3筛选有效线段&辅助点选择NUM=zeros(95,95);for i=1:95 for j=i+1:95 NUM(i,j)=1; endendB=1 3.2060 12.9166;2 17.4571 19.3377;3 4.7576 20;C=1 50 30;2 53.7465 48.4490;3 46.9222 57.1195;5 43.1123 56.3187;4 33.3207 3

24、9.8050;D=1 54.6982 70;2 53.7465 90;3 46.9222 80;E=1 90 75; 2 80 95; 3 70 80;b1=(B(1,3)-B(2,3)/(B(1,2)-B(2,2);bb1=(B(1,3)*B(2,2)-B(1,2)*B(2,3)/(B(1,2)-B(2,2);b2=(B(2,3)-B(3,3)/(B(2,2)-B(3,2);bb2=(B(2,3)*B(3,2)-B(2,2)*B(3,3)/(B(2,2)-B(3,2);b3=(B(3,3)-B(1,3)/(B(3,2)-B(1,2);bb3=(B(3,3)*B(1,2)-B(3,2)*B(1

25、,3)/(B(3,2)-B(1,2);BB=b1 bb1;b2 bb2;b3 bb3;c1=(C(1,3)-C(2,3)/(C(1,2)-C(2,2);cc1=(C(1,3)*C(2,2)-C(1,2)*C(2,3)/(C(1,2)-C(2,2);c2=(C(2,3)-C(3,3)/(C(2,2)-C(3,2);cc2=(C(2,3)*C(3,2)-C(2,2)*C(3,3)/(C(2,2)-C(3,2);c3=(C(3,3)-C(4,3)/(C(3,2)-C(4,2);cc3=(C(3,3)*C(4,2)-C(3,2)*C(4,3)/(C(3,2)-C(4,2);c4=(C(4,3)-C(5

26、,3)/(C(4,2)-C(5,2);cc4=(C(4,3)*C(5,2)-C(4,2)*C(5,3)/(C(4,2)-C(5,2);c5=(C(5,3)-C(1,3)/(C(5,2)-C(1,2);cc5=(C(5,3)*C(1,2)-C(5,2)*C(1,3)/(C(5,2)-C(1,2);CC=c1 cc1;c2 cc2;c3 cc3;c4 cc4;c5 cc5;d1=(D(1,3)-D(2,3)/(D(1,2)-D(2,2);dd1=(D(1,3)*D(2,2)-D(1,2)*D(2,3)/(D(1,2)-D(2,2);d2=(D(2,3)-D(3,3)/(D(2,2)-D(3,2);

27、dd2=(D(2,3)*D(3,2)-D(2,2)*D(3,3)/(D(2,2)-D(3,2);d3=(D(3,3)-D(1,3)/(D(3,2)-D(1,2);dd3=(D(3,3)*D(1,2)-D(3,2)*D(1,3)/(D(3,2)-D(1,2);DD=d1 dd1;d2 dd2;d3 dd3;e1=(E(1,3)-E(2,3)/(E(1,2)-E(2,2);ee1=(E(1,3)*E(2,2)-E(1,2)*E(2,3)/(E(1,2)-E(2,2);e2=(E(2,3)-E(3,3)/(E(2,2)-E(3,2);ee2=(E(2,3)*E(3,2)-E(2,2)*E(3,3)/

28、(E(2,2)-E(3,2);e3=(E(3,3)-E(1,3)/(E(3,2)-E(1,2);ee3=(E(3,3)*E(1,2)-E(3,2)*E(1,3)/(E(3,2)-E(1,2);EE=e1 ee1;e2 ee2;e3 ee3;A=1.0000 95.0129 58.27922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0

29、000 82.1407 52.982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0000 92.1813 78.332914.0000 73.8207 68.084615.0000 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000

30、35.2868 30.499923.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20.2765 97.084527.0000 19.8722 99.008328.0000 60.3792 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5

31、994 72.663236.0000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2647 43.992440.0000 67.2137 93.338041.0000 83.8118 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.889

32、2 62.988849.0000 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000 68.2223 4.389553.0000 30.2764 2.718554.0000 54.1674 31.268555.0000 15.0873 1.286356.0000 69.7898 38.396757.0000 37.8373 68.311658.0000 86.0012 9.284259.0000 85.3655 3.533860.0000 59.3563 61.239561.0000 49.6552 60.8

33、54062.0000 89.9769 1.576063.0000 82.1629 1.635564.0000 64.4910 19.007565.0000 81.7974 58.691866.0000 66.0228 5.758167.0000 34.1971 36.756868.0000 28.9726 63.145169.0000 34.1194 71.763470.0000 53.4079 69.266971.0000 72.7113 8.407972.0000 30.9290 45.435573.0000 83.8496 44.182874.0000 56.8072 35.325075

34、.0000 37.0414 15.360676.0000 70.2740 67.564577.0000 54.6571 69.921378.0000 44.4880 72.750979.0000 69.4567 47.838480.0000 62.1310 55.484281.0000 79.4821 12.104782.0000 95.6843 45.075483.0000 52.2590 71.588384.0000 88.0142 89.284285.0000 17.2956 27.310286.0000 97.9747 25.476987.0000 27.1447 86.560388.

35、0000 25.2329 23.235089.0000 87.5742 80.487290.0000 73.7306 90.839891.0000 13.6519 23.189492.0000 1.1757 23.931393.0000 89.3898 4.975494.0000 19.9138 7.838495.0000 29.8723 64.081596.0000 66.1443 19.088797.0000 28.4409 84.386998.0000 46.9224 17.390099.0000 6.4781 17.0793100.0000 98.8335 99.4295;for i=

36、1:95 xx1=result(1,i); xx2=result(2,i); x1=A(xx1,2); y1=A(xx1,3); x2=A(xx2,2); y2=A(xx2,3); a=(y1-y2)/(x1-x2); b=(y1*x2-x1*y2)/(x1-x2); for k=1:3 M=a -1;BB(k,1) -1; N=b 0;BB(k,2) 0; if(det(M)=0) P=MN; x=P(1,1); y=P(2,1); M1=x-B(k,2) y-B(k,3); N1=x-B(mod(k,3)+1,2) y-B(mod(k,3)+1,3); m=M1/N1; aa=x-x1,y

37、-y1; bb=x-x2,y-y2; if(xor(aa(1),bb(1)|xor(aa(1),bb(1)mm=0; else mm=aa/bb; end if(m0) if(mm0) NUM(i,j)=NUM(i,j)*0; else NUM(i,j)=NUM(i,j)*1; end else NUM(i,j)=NUM(i,j)*1; end end for k=1:5 M=a -1;CC(k,1) -1; N=b 0;CC(k,2) 0; if(det(M)=0) P=MN; x=P(1,1); y=P(2,1); M1=x-C(k,2) y-A(k,3); N1=x-C(mod(k,5)

38、+1,2) y-C(mod(k,5)+1,3); m=M1/N1; aa=x-x1,y-y1; bb=x-x2,y-y2; if(xor(aa(1),bb(1)|xor(aa(1),bb(1)mm=0; else mm=aa/bb; end if(m0) if(mm0)NUM(i,j)=NUM(i,j)*0; else NUM(i,j)=NUM(i,j)*1; end else NUM(i,j)=NUM(i,j)*1; end end end for k=1:3 M=a -1;DD(k,1) -1; N=b 0;DD(k,2) 0; if(det(M)=0) P=MN; x=P(1,1); y

39、=P(2,1); M1=x-D(k,2) y-D(k,3); N1=x-D(mod(k,3)+1,2) y-D(mod(k,3)+1,3); m=M1/N1; aa=x-x1,y-y1; bb=x-x2,y-y2; if(xor(aa(1),bb(1)|xor(aa(1),bb(1)mm=0; else mm=aa/bb; end if(m0) if(mm0)NUM(i,j)=NUM(i,j)*0; else NUM(i,j)=NUM(i,j)*1; end else NUM(i,j)=NUM(i,j)*1; end end end for k=1:3 M=a -1;EE(k,1) -1; N

40、=b 0;EE(k,2) 0; if(det(M)=0) P=MN; x=P(1,1); y=P(2,1); M1=x-E(k,2) y-E(k,3); N1=x-E(mod(k,3)+1,2) y-E(mod(k,3)+1,3); m=M1/N1; aa=x-x1,y-y1; bb=x-x2,y-y2; if(xor(aa(1),bb(1)|xor(aa(1),bb(1)mm=0; else mm=aa/bb; end if(m0) if(mm0)NUM(i,j)=NUM(i,j)*0; else NUM(i,j)=NUM(i,j)*1; end else NUM(i,j)=NUM(i,j)

41、*1; end end end endendNUM=NUM+NUM;for i=1:95; if(sign(i)=0); for j=1:95; NUM(i,j)=0; NUM(j,i)=0; end endendNUMA=1.0000 95.0129 58.27922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0000 82.140

42、7 52.982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0000 92.1813 78.332914.0000 73.8207 68.084615.0000 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000 35.2868 30

43、.499923.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20.2765 97.084527.0000 19.8722 99.008328.0000 60.3792 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5994 72.663

44、236.0000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2647 43.992440.0000 67.2137 93.338041.0000 83.8118 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.8892 62.988849.0000 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000