自来水管道连接规划模型.docx

资源描述

自来水管道连接规划模型.docx

《自来水管道连接规划模型.docx》由会员分享，可在线阅读，更多相关《自来水管道连接规划模型.docx（33页珍藏版）》请在冰点文库上搜索。

自来水管道连接规划模型.docx

自来水管道连接规划模型

自来水管道连接规划问题

自来水管道连接规划模型

（一）摘要：

自来水是人们日常生活中不可缺少的生活要素，我们分析自来水管道连接最优问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最短路径问题，使自来水管道将各个供水点用最短路径链接。

根据对目标点的数据进行筛选与分析，先用面积法排除障碍区域，再对剩余点采用Kruskal算法生成最优路的方案。

初始给定的供水点中存在位于障碍区域中的点，需要采用合理的方法排除障碍区域中的点。

本文将采用面积分析的方法，提供一种解决障碍区域判定的切实可行的方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过Matlab编程实现。

在确定并剔除障碍区中的点位后，采用Kruskal算法生成最优路径，对于通过阴影区域的线段，将其权值设定为无穷大，最终通过编程、绘图，给出管道最优连接方案，解决本问题。

最后我们对模型进行了整体评价，并提出改进之处。

（二）关键词：

管道连接面积法障碍点筛选最短路

Kruskal算法权值最小生成树

一.问题重述

自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。

一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。

表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：

如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。

表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。

（1）请您判定表1中那些用户为有效用户。

（2）请设计算法筛选有效用户之间的有效线段。

（3）请设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。

表1（见附录一）

表2障碍区域1必须要覆盖的点的坐标

顶点序号

顶点的横坐标

顶点的纵坐标

3.2060

12.9166

17.4571

19.3377

4.7576

表3障碍区域2必须要覆盖的点的坐标

顶点序号

顶点的横坐标

顶点的纵坐标

53.7465

48.4490

46.9222

57.1195

33.3207

39.8050

43.1123

56.3187

表4障碍区域3必须要覆盖的点的坐标

顶点序号

顶点的横坐标

顶点的纵坐标

54.6982

53.7465

46.9222

表5障碍区域4必须要覆盖的点的坐标

顶点序号

顶点的横坐标

顶点的纵坐标

二．模型假设

1，用户之间以直线连接;

2，障碍区中的用户可以忽略，认为是无效用户；

3，以管道总距离最小为目的；

4，障碍区域是障碍顶点围成的凸多边形区域；

5，在非障碍区用户之间可确保用直线连接，且直线不通过障碍区域；

三．符号说明

表6论文符号说明

符号

表示对象

用户点的坐标

障碍区1的各顶点坐标

障碍区2的各顶点坐标

障碍区3的各顶点坐标

障碍区4的各顶点坐标

SIGN

记录各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0

OUTSIGN

无效用户点的序号

有效用户点的个数

NUM

记录任意两用户点之间可用线段连接起来且不过障碍区的线段

DIS

连接的长度

最小生成树的点以及连接的信息

sum

最小生成树管道的总长

四．问题分析

先排除障碍区域。

如果用户点位于凸边型障碍物之外，则为有效用户，否则为无效用户。

再将任意两个有效用户连接，如果连接通过障碍区域之内，则为无效线段。

最后通过有效点和有效连接生成最小生成树，并且连接有效用户点，画出连接路线图形，并计算生成树所成长度。

根据对模型的合理假设，障碍区域即为已知若干障碍区顶点围成的凸多边形，故解决此问题的关键在于在已建立的二维坐标系中，寻找到一种合理的算法能够判定出点是否位于障碍区域中。

通过直观判断，阴影区域的构成由表7给出：

表7障碍区域构成

障碍区域编号

构成

由3个无效用户坐标点围成的三角形

由5个无效用户坐标点围成的凸五边形

由3个无效用户坐标点围成的三角形

运用面积法进行筛选点，对所有点进行筛选，找到并排除障碍区域中的无效用户，

再把任意两个有效用户点之间用线段连接，运用向量法设计筛选线段的程序，筛选出所有不过障碍区的线段。

最后设计程序，将所有有效用户点连接起来，并使管道总距离最小。

这是一个典型的最小生成树问题，但相较以往最小生成树问题又有着其特别之处，以往的无障碍的情况下只需要使用弗洛伊德算法即可。

但因为障碍区域的干扰，这使得坐标系并非是一个连通区域，该无法直接使用。

这就需要我们在对问题进行合理假设的前提下，对已有算法进行改良。

我们通过对穿过障碍区的线段赋权值为无穷大的方法，利用Kruskal算法，生成最优路径。

五．模型的建立与求解：

5.1.问题一的模型建立和求解

5.1.1运用向量的方法求解障碍区面积S

若障碍区是三角形，对应各顶点坐标分别为（x1,y1），（x2,y2）,（x3,y3）。

则a=（x2-x1,y2-y1）,b=（x3-x1,y3-y1）。

由于三角形面积S=|a|*|b|*sin/2,向量a,b外积的模长|a×b|=|a|*|b|*sin;则有S=|a×b|/2;

若障碍区为五边形，对应点为（x1,y1），（x2,y2）,（x3,y3）,（x4,y4），（x5,y5）。

则划分成三个三角形，各三角形的顶点分别为（x1,y1），（x2,y2）,（x3,y3）；（x3,y3）,（x4,y4），（x5,y5）；（x1,y1），（x3,y3）,（x5,y5）。

再用求三角形面积的方法求解即可。

5.1.2求用户点与任意两个同一障碍区的顶点构成三角形的面积之和S1

5.1.3判断有效用户

如果S=S1，则该用户在障碍区内，为无效用户。

反之为有效用户。

则筛选完毕的结果如下：

在障碍区的点的序号分别为：

4233699。

无效用户的信息为：

（4.0000,48.5982,33.3951）;（23.0000,81.3166,87.4367）;（36.0000,41.8649,41.1953）;（99.0000,6.4781,17.0793）;

有效用户的个数是：

96。

100个点是否在障碍区的情况如下图：

5.2连接有效用户

求出过任意两个有效用户点的直线m与过各障碍区中任意两个顶点的直线L的交点坐标，再运用向量法判断该交点是否在以上述两有效用户点为端点上的线段m1和以上述障碍区顶点为端点的线段L1上，然后判断过该两个有效用户点的连接是否有效。

5.2.1运用矩阵的方法求解两直线之间的交点坐标

如果任意两个有效用户点的坐标分别为A（x1,y1）、B（x2,y2），同一障碍区任意两个顶点坐标为M（x3,y3）、N（x4,y4）。

则两直线方程分别为：

（1）

（2）；

则由解线性方程组的方法有

，线性方程组的的系数矩阵为：

；

在运用Matlab求解该线性方程组时，不妨把

分别设为：

可以求得

=A\

。

5.2.2判断线段是否为有效线段

若求得的交点坐标为P（x,y），则通过向量关系PM=

PN,可以求的

。

若

0,则该线段为有效线段；若

<0,则要考虑向量关系PA=

PB,若

0，则该线段为有效线段，否则，该线段为无效线段。

5.3问题三的模型建立与求解

若要在N个用户之间连接自来水管道，由于每一个用户与其余N-1个用户之间都可能连接自来水管道。

因此，在N个用户之间，最多可能连接N（N-1）/2条自来水管道然而，在连接N个用户之间的管道时，最少只需连接N-1条管道。

也就是说只需要N-1条管道线路就可以把N个用户之间的自来水管道连通。

现在要考虑在连接N个用户的自来水管道的同时要保证所有的管道长度之和最短，这就涉及了最优化的问题。

利用Kruskal算法思想设计Matlab程序进行最小生成树所需边的筛选,并且设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。

5.3.1利用Kruskal算法思想求解最小生成树

设计96个用户之间的带权图，并作出邻接矩阵DIS,再根据求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf，可以得到一个新的邻接矩阵DIS。

接下来，用冒泡排序法对所有有效线段长度按从小到大的顺序进行排序。

这时，需要借助Kruskal算法进行最小生成树的计算。

然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE中。

生成最小生成树时，从长度最短的边开始选取。

首先不妨设一个1×96的标记向量l用于记录被选取的点的序号，初始状态向量l的各元素依次为各用户序号，在选取线段为边后，将对应两点的序号m与n取最小值，并将向量l中所有与m位置元素相等的元素位置及所有与n位置的元素相等的元素位置都赋值为该最小值，如此循环知道向量l中所有元素均相等时停止；同时可以设一向量R来依次记录被选点的序号，直到所有用户点被无重复地被记录。

在按线段长度从小到大的顺序选择边时，设线段端点用户的序号为m与n。

这时需要考虑如下4种情况：

<1>如果在向量R中m和n均没有被记录,则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m和n的值，并按照上述步骤更新向量l。

<2>如果在向量R中m被记录而n没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵M中，同时在R中添加记录n的值，并按照上述步骤更新向量l。

<3>如果在向量R中n被记录而m没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m的值，并按照上述步骤更新向量l。

<4>如果在向量R中m和n均被记录,则需要借助向量l来判断是否该线段可以被选为最小生成树的边：

a.如果向量l中对应的m位置与n位置的元素值相等，则该线段不是最小生成树的边，直接跳过到下一步判断。

b.如果向量l中对应的m位置与n位置的元素值不相等，则该线段是最小生成树的边，将对应线段的信息记录在矩阵M中，同时只需要更新向量l。

通过上述方法，即可产生最小生成树，其各边信息记录在矩阵M中。

5.3.2设计Matlab程序求出最小生成树长度并将各边连接起来

要计算最小生成树的长度，只需要借助for循环将M矩阵中记录长度相加即可。

具体算发如下：

sum=0;

fori=1:

p-1

sum=sum+M（1,i）;

end

sum

可以求得最小生成树的长度为：

sum=653.0196；

最后，借助plot函数画出最小生成树的图形。

算法如下：

holdon;

fori=1:

100

x=A（i,2）;

y=A（i,3）;

plot（x,y,'o'）

end

fori=1:

n-1

x1=AL（M（2,i）,2）;

y1=AL（M（2,i）,3）;

x2=AL（M（3,i）,2）;

y2=AL（M（3,i）,3）;

X=[x1,x2];

Y=[y1,y2];

plot（X,Y）

end

fori=1:

x1=B（i,2）;

y1=B（i,3）;

x2=B（mod（i,3）+1,2）;

y2=B（mod（i,3）+1,3）;

X=[x1,x2];

Y=[y1,y2];

plot（X,Y,'m'）

end

fori=1:

x1=C（i,2）;

y1=C（i,3）;

x2=C（mod（i,5）+1,2）;

y2=C（mod（i,5）+1,3）;

X=[x1,x2];

Y=[y1,y2];

plot（X,Y,'m'）

end

fori=1:

x1=D（i,2）;

y1=D（i,3）;

x2=D（mod（i,3）+1,2）;

y2=D（mod（i,3）+1,3）;

X=[x1,x2];

Y=[y1,y2];

plot（X,Y,'m'）

end

fori=1:

x1=E（i,2）;

y1=E（i,3）;

x2=E（mod（i,3）+1,2）;

y2=E（mod（i,3）+1,3）;

X=[x1,x2];

Y=[y1,y2];

plot（X,Y,'m'）

end

连接形成的最小生成树的图形如下图所示：

由图可知，该最小生成数是合理的。

六．模型检验

首先可以通过对所画最小生成树图形的观察，看是否有回路，由图易知图形中无回路，则通过修改最小生成树中任意边的连接，计算修改后的最小生成树的长度sum’与sum进行比较。

可得sum’>sum,则该模型所生成的最小生成树的长度最短，即运用该模型进行自来水管道的连接所需要的自来水管长度最短。

十．附录

附录：

若干个可能的用户的地址的横纵坐标

可能的用户的序号

可能的用户横坐标

可能的用户纵坐标

1.0000

95.0129

58.2792

2.0000

23.1139

42.3496

3.0000

60.6843

51.5512

4.0000

48.5982

33.3951

5.0000

89.1299

43.2907

6.0000

76.2097

22.5950

7.0000

45.6468

57.9807

8.0000

1.8504

76.0365

9.0000

82.1407

52.9823

10.0000

44.4703

64.0526

11.0000

61.5432

20.9069

12.0000

79.1937

37.9818

13.0000

92.1813

78.3329

14.0000

73.8207

68.0846

15.0000

17.6266

46.1095

16.0000

40.5706

56.7829

17.0000

93.5470

79.4211

18.0000

91.6904

5.9183

19.0000

41.0270

60.2869

20.0000

89.3650

5.0269

21.0000

5.7891

41.5375

22.0000

35.2868

30.4999

23.0000

81.3166

87.4367

24.0000

0.9861

1.5009

25.0000

13.8891

76.7950

26.0000

20.2765

97.0845

27.0000

19.8722

99.0083

28.0000

60.3792

78.8862

29.0000

27.2188

43.8659

30.0000

19.8814

49.8311

31.0000

1.5274

21.3963

32.0000

74.6786

64.3492

33.0000

44.5096

32.0036

34.0000

93.1815

96.0099

35.0000

46.5994

72.6632

36.0000

41.8649

41.1953

37.0000

84.6221

74.4566

38.0000

52.5152

26.7947

39.0000

20.2647

43.9924

40.0000

67.2137

93.3380

41.0000

83.8118

68.3332

42.0000

1.9640

21.2560

43.0000

68.1277

83.9238

44.0000

37.9481

62.8785

45.0000

83.1796

13.3773

46.0000

50.2813

20.7133

47.0000

70.9471

60.7199

48.0000

42.8892

62.9888

49.0000

30.4617

37.0477

50.0000

18.9654

57.5148

51.0000

19.3431

45.1425

52.0000

68.2223

4.3895

53.0000

30.2764

2.7185

54.0000

54.1674

31.2685

55.0000

15.0873

1.2863

56.0000

69.7898

38.3967

57.0000

37.8373

68.3116

58.0000

86.0012

9.2842

59.0000

85.3655

3.5338

60.0000

59.3563

61.2395

61.0000

49.6552

60.8540

62.0000

89.9769

1.5760

63.0000

82.1629

1.6355

64.0000

64.4910

19.0075

65.0000

81.7974

58.6918

66.0000

66.0228

5.7581

67.0000

34.1971

36.7568

68.0000

28.9726

63.1451

69.0000

34.1194

71.7634

70.0000

53.4079

69.2669

71.0000

72.7113

8.4079

72.0000

30.9290

45.4355

73.0000

83.8496

44.1828

74.0000

56.8072

35.3250

75.0000

37.0414

15.3606

76.0000

70.2740

67.5645

77.0000

54.6571

69.9213

78.0000

44.4880

72.7509

79.0000

69.4567

47.8384

80.0000

62.1310

55.4842

81.0000

79.4821

12.1047

82.0000

95.6843

45.0754

83.0000

52.2590

71.5883

84.0000

88.0142

89.2842

85.0000

17.2956

27.3102

86.0000

97.9747

25.4769

87.0000

27.1447

86.5603

88.0000

25.2329

23.2350

89.0000

87.5742

80.4872

90.0000

73.7306

90.8398

91.0000

13.6519

23.1894

92.0000

1.1757

23.9313

93.0000

89.3898

4.9754

94.0000

19.9138

7.8384

95.0000

29.8723

64.0815

96.0000

66.1443

19.0887

97.0000

28.4409

84.3869

98.0000

46.9224

17.3900

99.0000

6.4781

17.0793

100.0000

98.8335

99.4295

附录三：

解决该自来水管道连接问题的Matlab程序：

%问题一，进行有效点的筛选

A=[1.000095.012958.2792;

2.000023.113942.3496;

3.000060.684351.5512;

4.000048.598233.3951;

5.000089.129943.2907;

6.000076.209722.5950;

7.000045.646857.9807;

8.00001.850476.0365;

9.000082.140752.9823;

10.000044.470364.0526;

11.000061.543220.9069;

12.000079.193737.9818;

13.000092.181378.3329;

14.000073.820768.0846;

15.000017.626646.1095;

16.000040.570656.7829;

17.000093.547079.4211;

18.000091.69045.9183;

19.000041.027060.2869;

20.000089.36505.0269;

21.00005.789141.5375;

22.000035.286830.4999;

23.000081.316687.4367;

24.00000.98611.5009;

25.000013.889176.7950;

26.000020.276597.0845;

27.000019.872299.0083;

28.000060.379278.8862;

29.000027.218843.8659;

30.000019.881449.8311;

31.00001.527421.3963;

32.000074.678664.3492;

33.000044.509632.0036;

34.000093.181596.0099;

35.000046.599472.6632;

36.000041.864941.1953;

37.000084.622174.4566;

38.000052.515226.7947;

39.000020.264743.9924;

40.000067.213793.3380;

41.000083.811868.3332;

42.00001.964021.2560;

43.000068.127783.9238;

44.000037.948162.8785;

45.000083.179613.3773;

46.000050.281320.7133;

47.000070.947160.7199;

48.000042.889262.9888;

49.000030.461737.0477;

50.000018.965457.5148;

51.000019.343145.1425;

52.000068.22234.3895;

53.000030.27642.7185;

54.000054.167431.2685;

55.000015.08731.2863;

56.000069.789838.3967;

57.000037.83

展开阅读全文