优化网络路线的新方法

第26卷第12期 Vd26Nol2 企业技术开发 TECHNOLOCICALDEVELOPMENTOFENTERPRISE 2007年12月 Dec2007 优化网络路线的新方法 饶卫振。李修海 (山东英才职业技术学院商学院，山东济南250104) 摘要；目前优化网络路线的方法只有避圈击和破圈法。但这两种方法在妾际操作过程中都存在明显的缺陷，文章 提出了一种仝新的优化网络路线的方法——最小边法．谊方击在一定程度上克服了速两种方法的不足。 关键词：网络路线优化；遵圈法；破圈法；最小边法 中图分类号：TU990．3 文献标识码：^ 文章编号：l∞6—8937(2007)12—00”一03 Thenewalgorithmofoptimizingnetworkroute RAOWei—zhen，LIXiu—hai (BusinessSch001．ShandongYingcaiVocationalTechn0109yCollege．Jinan．Shandong250104，China) Abstract：AtpresenLtheoptimizednetwork10ute8pproachonJyhasknlstal柚dthebT0kencircIeapproach． Butthe8etwoappr08chesauhavetheobviousnawintheactualoperationpmcess，thisp8pe。pmposesthe 哪alIestlineappmachofo眦newoptimizi“gnetworkmute，this8pproachh鹊overcomeinsu踊ciencyof thesetwo印pmachesintllecertaindeg陀e． Keywords：oPtjmi盟honofnetworkroute；kmstal-brokencircIeapproach；thesmallest1ineapproach 为了提高人们生活水平，我国各方面的基础建 设进行得如火如荼。在基础建设工作中，经常涉及 到一些诸如管道铺设、电线架接、公路修建、光缆埋 设等工作环节，在进行上述工作时不可避免要面临 一个路线选择问题。即如何选择施工路线，使各个 使用之间能够连通，又能达到节约资源的目的，这类 问题就是典型的网络路线优化问题。 1优化铺设管道路线的方法 目前，优化网络路线的方法仅有两种，即运筹 学中求最小支撑树中的避圈法和破罔法。 这两种方法各具特点，其方法原理用数学术语 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示比较抽象．在这里通过事例来介绍这两种方法。 例：某市6个新建单位之间的交通线路的长度 (km)如表l所示。其中单位A距市煤气供应网最 近．为1．5km。 表1某市6新建单位之间距离表 km __一 F 37 3．9 1 0 2．7 24 0 新建单位 收稿日期：2007—09一” 。 作者简介：饶卫振(1981一l，男，江西丰城人，硕士研完生．研究方 向：系统菅理与决策． 为使这6个单位都能使用煤气，现拟定沿交通 线铺设地下管道，并且经A与煤气供应网连通。应 如何铺设煤气管道使其总长最短。 设该6新建单位的位置关系如下图l所示。 围1 6新建单位距离关系网络图 1．1避圈法 避圈法计算步骤如下： ①从网络中任选一点v．．令s=lv。}．s=V“v．}；，、 ②从连接s与s的边中选取最小边，不妨设最 小边为(％v。)，该边必为优化路线中的一条； ③重新修正集合s与s的组成元素，在集合S中 增加顶点v．，显然在集合s中减少该顶点v。；． ④如果s-空集，则停止．已找到所有的优化路 线；否则返回第2步。 该铺设煤气管道问题用避圈法求解过程如下； E甄¨拍u o¨D一”枷拈o¨”c一：："o批拍加B一¨o”如¨”A—o¨妃”弘" 万方数据 企业技术开发 2f)07年12月 ①假设从A开始。即s：【A}，j：IB，c，D，E，Fl； 法很不适用。 ②连接s与s的边共有5条：(A，B)=1．3km、(A， C)=3．2km、(A，D)=4．3km、(A，E)=3．8km、(A，n=3．7 km，显见最小边为fA，B)=1．3km； ③重新修正集合S与s后，可得S=fA，B}，s=fc， D，E，F1； 。 ④因为当前s={c，D，E，Fl≠空集，所以要回到 第2步，这时可以发现连接S与S的有8条边⋯⋯． 以此思路继续下去，直到s=fA，B，c，D，E，Fl，s=空 集，而在此过程中每重复一次第2步，比较出来的 最川、边：(A，B)=1．3km、(B，E)=31 km、(E，D)：2．1 km、(E，F)=2．4km、(F，C)=1．0km，即为所有的优 化路线，线路总长为：1．3+3．1+2．1+2．4+1．0=9．9 (km)，为连接所有6新建单位的最短路线，要实现 煤气的供应则最短需要铺设的管道长度为9．9+ 1．5=儿4(km)。 因为方法思路一样，这里不再赘述所有的详细 比较步骤。 1．2破圈法。 破圈法相比避圈法的思路简单。 ①在网络图中找到一个圈，去掉圈中的最长的 一条边： ②检查网络图中是否还有圈，如果有，重复第1 步，否则停止，表明已找到最优路线。 用破圈法解决上述煤气管道铺设问题可以如 下操作： ①找到网络图中存在的任意一个圈，假设找到 的圈为A_B_+c_A，此圈由(A，B)=1．3km、(B， c)=3．5km、(C，A)=3．2km三条边组成，显然最长 的为(B，c)=3．5km，因此在此圈中删去边(B，C)； ②通过网l可以看出，此网络图有非常多的 圈，可以依照步骤l重复进行，直到网络图中不再 存在圈为止，这里不再赘述。 1．3避圈法与破圈法在解决此类问题中的优缺点 ①避圈法的优点：步骤固定，进行n—l步比较 (n为网络图中的顶点个数)必定找到所有的最优 路线；缺点：每一步的比较都比较繁琐，有的边需要 在几步比较中重复使用，比较的工作量大。 ②破圈法的优点：思路简单，只要找到一个圈 破掉最长边；缺点：网络中罔比较多时步骤也随之 增加(破圈的步骤数等于网络图中的圈的个数)，当 使用不可涂抹笔(如签字笔、圆珠笔、钢笔)时．破圈 2网络路线优化的新方法 当前用来解决网络路线优化的方法就是避圈 法和破圈法，作者认为还有一种方法能够解决此类 问题，而且能够在一定程度上克服这两种方法的不 足。 为了方便叙述，作者给此方法命名为最小边法。 最小边法步骤： ①先只画出网络图的所有顶点； ②在所有的边中找到最短的和次短的两条边， 添加到网络图中； ③在剩下的边中再找最短的一条．看添加上这 条边在网络图中是否会形成圈(很容易看出，因为 目前图中的边很少)，不会就在图中添加上这条边， 否则放弃这条边，继续找出次短的边进行判断； ④检查添加上的边数，如果等于n一1条(n表示 网络图中顶点的个数)，表明已找到所有的最优路 线，否则重复第3步。 使用最小边法解决该煤气管道在6新建单位 之间铺设问题。步骤如下： ①画出网络图中所有的顶点，见图2。 ④ ④ ④ ⑨ ，④ ④ 图2初始状态顶点圉 ②所有的边中最短的和次短的两条边，显见分 别为：(F，C)=1．Okm、(A，B)=1．3km，在图2的基 础上添加泼两条边，见图3。 ④燮艳 @ 图3第一步结束状态图 ③在剩下的边中再找最短的一条，得(E，D) 万方数据 第26卷第12期 饶卫振．等：优化网绍路线的新方法 ：2．1km，显然不会形成圈可以舔加上该条边；到目 前为止已经找到3条边，按照最小边方法思路还只 要找到2条可添加的边此问题就得到解决，在剩下 的所有边中最小的几条边分男4为：(E，F)=24km． (E，C)=26km，(D，F)-27km，(D，C)=2．8km，(E． B)=3．1km⋯⋯经过判断边(E。F)=24km可添加， 而边(E，C)=2．6km，(D．F)=27km，(D．C)=28 km， 均不可添加，因为这三条边添加任何一条都会使目 前网络图中形成圈。这时目前最小的边为(E．B) =31 km，通过判断添加该边不会形成圈，因此该边 为耍找的第5条可添加边(网络顶点数为6个)，这 说明网络的最优路线全部找到如图4所示。 图4最后步骤结束状态囤 最小边法说明： 在网络路线优化中遇见的一般均是简单网络 图，因为如果两点之『日』有多条路线。显然可以人为 地去掉较长的路线，保留最短的一条，并且这类问 题中不可能出现环．所以最终的网络图为简单网络 圉。罚此，在辫珧此类路径优化问题完全可以应用 上述最小边法求解。 但当网络图为多重图(有环或者两点之间有两 条或两条以上边的情况)，只要将第2步改为：从所 有边中找出最短的一条边，添加到网络图中．以后 步骤不变。 3结语 最小边法与避圈法和破圈法相比总体来说工 作量小．这体现在两方面：第一，最小边法的数据之 间的比较工作量小，只要把所有的边从小到大排好 顺序，然后由小到人逐个判断，直到找出nl条边 为止；第二，书写工作量小，在实际操作中避圈法和 破幽法均要画出整个网络囝，并且 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 重复书写多 次，而最小边诖所有的书写量就是网络的最优路线 图。 。希望本方法能够得以推广，为我国的基础建设 工作者提供一定的理论参考。 参考文献 【l】韩大卫管理运筹学【M】．大连：大连理工大学出版社，1998 【2l钱颂迪运筹学[M】北京-清华大学出版社，1990 【3】邦迪，默蒂著吴望名译囤论及其应用[Ml北京科学出 版社．】9lj4． 【4】左孝凌，李为鉴，刘永才，等离散数学【Ml卜海上海荆学 技术出版社。1982 +一一-一⋯⋯⋯～⋯～⋯ 高承压岩溶含水层带压开采技术获突破 科技日报2∞7年11月15日消息：长期以来，在 华北地区开采受奥灰水威胁的9号煤资碌．一直是{莩 炭行业面临的难题．虽开采慎重．却全部因遭受水害而 中止。由河北金牛能源集团葛泉矿与煤炭科学研究总 院西安研究院共同完成的葛泉矿东井双层复合高承压 岩溶告水层上带压开采下组煤综合防治水技术，使这 一问题得到解决，井于近日通过了由河北省科技厅组织 的专象鉴定。 专家组认为：双层复台高承玉岩溶含永层上带压 _开采下组惺综舍防治水技术研究，针对华北型蹲田下 组煤复杂的水史地质条件．制定了葛泉东井在开采9 号煤过程中“精细探查、先探后掘、洼浆改造先治后 果、垒程监控、全面设防”的防清水技术路线。项目制定 了“井下为主、地向为辅、物撵为主、钻探验证”的勘探 原则．采用了井上井下相结台，全方位，多层发的勘探 手压，并首次采用了直流电法长距离超前探冽技术和 三、四桠结合的假异常排除技术。项目在注浆的 工艺 钢结构制作工艺流程车尿素生产工艺流程自动玻璃钢生产工艺2工艺纪律检查制度q345焊接工艺规程 流 程上．采用钻探和注浆次序阶段进行等方法，克服丁高 承压岩溶含水层上带压开采下组煤的防治水技术难 题 开 程 ．彤礁了一整套以耀层底板注浆改造为主捧的带压 。 采综合防治水技术，提高了勘测精度．节省丁钻探工 ， ．井有多项技术属国内首创．达到了国际先进水平。 ； 技术前沿{—⋯一_—H⋯一～．一一』 万方数据