天然气管道的铺设方案的优化

天然气管道的铺设方案的优化内容摘要：

4 3 2 9 2 1 6 . 2 1 6 4 5 , 0 . 5 8 7 8 5 5 9 . 3 9 2 5 ,3 . 8 2 1 1 2 2 5 3 . 8 2 0 8 2 6 , 0 . 2 1 0 1 8 9 4 7 . 2 5 9 6 9 , 1 . 6 8 6 5 1 7 1 6 . 3 9 0 9 2 7Y X Y XSY X Y X Y X           3 21 .0 15 10 79 .4 82 6 , 1. 28 60 1 0. 34 24 32 , 1. 46 53 5 1 Y X Y X Y X         4 2 25 5 , 0. 25 97 .5 , 1. 5 25S Y X Y X Y X         连接节点中的任意两节点 ( , ), ( , )i i i j j jV X Y V X Y得到他们两点之间线段的方程为： ijX X tX ijY Y tY  1,1t 当  1 2 3 4( , )X Y S S S S 时令 ijE 边上的权 ijW 为 M。 （ M 为一个无穷大的数） 当  1 2 3 4( , )X Y S S S S 时令 ijE 边上的权 ijW 为：    22ij i j i jW X X Y Y    上式确定了任意两节点之间权的算法，把他们用矩阵表示出来，就得到了一个96 阶的矩阵。 矩阵中的元素表示对应的两节点间的权数。 理论模型 利用最小生 成树来求解最短路径的问题，在得到任意两节点权的条件下，我运用以下方法来求解。 [1] 避圈法和破圈法来求图的最小生成树。 用避圈法在给定的图中寻找最小生成树的基本步骤是： （ 1） 从图中 96 个节点中任选一点 iV ，让 iVV ，图中其余点均包含在 V 中。 （ 2） 从 V 与 V 的连线中找出一条最小边，若有两条边相等，任选一条即可，则这条边一定包含在最小部分树内。 5 （ 3） 令 jV V V ， \ jV V V。 （ 4） 重复（ 2），（ 3）两步，一直到土中 96 个点均包含在 V 中为止。 用破圈法在给定的图中寻找最小生成树的基本步骤是： （ 1） 从网络图 N 中任取一回路 C。 （ 2） 在回路中去掉其中权数最大的 一条边。 得子网络图 1N。 （ 3） 再在 1N 中任取一回路，再去掉回路中权数最大的一条边，得 2N。 （ 4） 重复（ 3），一直到剩下的子图中不再含回路为止，该图就是 N 的最小部分树。 [2] 构造网络中的最小生成树，下面我们给出这样一种解法：（称其为权值排序法） （ 1） 已知一个网，将网中的边按其权值由小到大的次序顺序选取。 （ 2） 若选某边后不形成回路，则将其保留作为树的一条边；若选某边后形成回路，则将其舍弃，以后也不再考虑。 （ 3）如此依次进行，直到选够 (n1)条边即得到最小生成树。 通过 MATLAB 对避圈法的编程，我们得到 以下结果： 表一：最小生成树的节点连接情况及权值 起始节点 终止节点 距离 (权值 )。