大学本科毕业论文：数学建模.doc

专业代码： 070101 学 号： 2009405018 本科毕业论文(设计)题目：贵州省晴隆县花贡镇数字电视线路优化设计学 院： 数学科学学院 专 业： 数学与应用数学 班 级： 2009级师(1)班 学生姓名： 李 娜 指导教师： 余 英 2013年 3 月 14 日目 录目录I中文摘要、关键词II英文摘要、关键词III正文11 引言1 1.1 提出问题 1 1.2 文献综述 1 1.2.1 数字电视线路优化的目的及基本内容 1 1.2.1.1 数字电视线路优化目标1 1.2.1.2 影响数字电视线路规划的因素2 1.2.2 最小生成树问题简介 2 1.3 研究意义 22 资料收集 33 研究过程 4 3.1 资料处理 4 3.2 数据处理 4 3.3电视线路设计5 3.3.1影响线路走向选择的因素5 3.3.2电视线路的确定5 3.3.3具体电视线路的确定5 3.3.3.1 Kruskal算法5 3.3.3.2 管梅谷算法6 3.3.3.3 结论84 结果讨论 85 结束语 86参考文献 9贵州省晴隆县花贡镇数字电视线路优化设计李娜(数学科学学院 数学与应用数学专业 2009级师(1)班)摘要：随着科技的发展，电视机走进了千家万户，看电视成为人们获取信息中的一个重要渠道。每个人的爱好不同，喜欢收看的节目也不一样，接收卫星发射节目的方式只能接收到部分频道，这已经不能满足人们收看电视节目的需求了。广电总局推出的数字电视解决了频道少的问题，它能够接收各种类型的频道，能充分满足人们看各种电视节目喜好。在数字电视逐步取代卫星信号的过程中，数字电视线路的规划成为一个亟待解决的问题，需要找到一种方法来解决这一问题，使线路的规划既合理又节省。我的家乡贵州省晴隆县花贡镇即将进行电视频道接收方式的改革，我就以我的家乡为例，对数字电视线路的安排作一个优化设计。由于广电总局还达不到数字电视进入每户农家的实力，目前只考虑村镇的数字电视线路的安排（即花贡镇的一个社区，六个行政村）。本文将用图论中树的知识对收集的资料进行处理，然后结合实际情况对研究所得的成果修改完善，最后给出数字电视线路优化设计方案。关键词: 数字电视线路；树；Kruskal算法；管梅谷算法 HuaGong town QingLong County Guizhou province digital TV line optimization design 李娜(Grade 2009 Class (1)(normal)，Mathematics and applied mathematics，School of Mathematical Science)Abstract:With the development of science and technology, television widely used by thousands of households and become an important channel for people to obtain information. However, each persons hobbies are different, they like watch different program, so receiving satellite launch programs the way only to receive part of the channel, could not meet peoples demand already. Consequently, Administration Of Radio Digital Television launched Digital Television, this solved many problems, it can receive various types of channels, which can fully satisfy the people to watch various TV programs according to their interests .In the process of digital TV is gradually replacing satellite signal, digital television line planning has become an urgent problem to be solved, so we need to find a way to solve this problem, which makes the line planning reasonable and save energy on the other hand. My hometown in Huagong town Qinglong County Guizhou province reform the ways of television channel receives, I want to take my hometown as an example, to make an Optimization design to the digital television line. Only consider to make rural digital TV line arrangement (i.e. Huagong town in a community, six administrative village) at present, for the SARFT has no strength to Installation digital television into every farmhouse. This article will use the knowledge of the Tree Of The Graph Theory to deal with the collected data, and then improve the research results combined with the actual situation, and finally, scheme the digital TV circuit.Keywords: Digital TV line; Tree;Kruskal algorithm; GuanMeiGu algorithm正文1引言1.1提出问题随着广电总局对数字电视的普及，晴隆县花贡镇的电视频道改革势在必行。晴隆县花贡镇的电视接收方式正处于由卫星电视向数字电视的转变中，在这个过程中不仅广电总局要使数字电视线路安排合理，达到方便大家、省钱省力，其基础设施也要达到标准的规模。数字电视是每家每户必备的娱乐设施，所以在晴隆县花贡镇的数字电视规划过程中，数字电视线路的设计是一个必不可少的任务。本文主要就数字电视线路安排这个问题进行研究。研究结果能为相关部门的工作带来一些科学性参考，为晴隆县花贡镇的数字电视线路的优化方案提供理论依据。1.2文献综述近年来，我国经济快速发展，村镇居民的生活条件普遍得到了提高。随着经济条件改善，村镇居民的消费水平也有所提高，很多家庭都希望收看到自己喜欢的节目。广电总局为了方便人们，于是对电视进行改革，推出了数字电视，数字电视能够满足大部分电视观众的需求。有线数字电视不仅提供传统广播电视服务，还提供视频点播、电子政务、生活资讯、电视商务等多种新型服务，成为家庭多媒体信息终端1。数字电视线路优化是数字电视发展中规划的一个重要内容。数字电视线路的优化设计直接影响投入成本的高低，同时数字电视线路的优化受到很多条件的限制如山势高低、村镇占地面积、用户分布等等。这些问题都是在数字电视线路优化设计中要考虑的因素。1.2.1 数字电视线路优化的目的及基本内容数字电视线路优化设计的目的：（1）丰富村镇居民的业余生活。 （2）开阔村镇居民视野，陶冶村镇居民情操。 （3）促成广电公司与用户两方的双赢局面，使双方投入最少，获得的利益最大。数字电视线路优化设计的基本内容： （1）数字电视线路的优化。 （2）各地需设光机个数及光缆型号的选择。本文主要就数字电视线路的优化设计进行研究。1.2.1.1数字电视线路优化目标 （1）主干线路的长度 指连接一社区六行政村的光缆线路，主干线路是评价线路的节省程度主要指标之一。 （2）光缆的使用型号选择 光缆的选择主要从主干路线确定后，综合各个村所需安装光机数来确定，光缆型号的合理选择是评价节省的指标。 （3）最省光机的安排 当主干线确定后，光机的安排也是评价节省的指标，光机只在一社区六行政村才安装，在主干线上是不安装的。(4） 保证线路的服务面积率，最大的覆盖村镇住户。1.2.1.2 影响数字电视线路规划的因素 （1）山势高低 贵州省是高原地区，花贡镇毫无例外地多山，这些因素影响着主干线路的安排，选择一条较近的表面距离是主干线路必要性参考条件之一。 （2）村镇占地面积 村镇占地面积大小和形状的情况，直接影响到光机使用的多少，是考虑是否有 安装光机必要性的参考条件之一。1.2.2 最小生成树问题简介树是图论中结构最简单但又十分重要的图，在自然科学和社会科学的许多领域都有广泛的作用。许多网络问题都可以归结为最小数问题，例如，设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来等2。解决最小树问题的算法主要有：Kruskal算法、管梅谷算法。Kruskal算法是Kruskal于1956年提出的一个产生最小树的算法，算法的基本思想是：每次将一条权最小的弧加入子图T中，并保证不形成圈，即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧，当弧有n+1条时，即为最小树3。管梅谷算法的步骤是：在赋权图G中任取一个回路，删去其中一条权最大的边，在余下的图中重复上述做法，直到无回路为止，使可得到最小生成树4。1.3 研究意义国内外学者通过研究影响线路设计的因素，主要包括用户数量、用户分布及山区地势条件等因素展开自己的研究，达到线路的优化设计。本文主要以晴隆县花贡镇的主干道路为基础，进一步给出其村和社区数字电视线路的优化设计方案，假设研究中的每条线路都满足电视收视运行的相关要求，规划图中所有的线路均看成直线。研究晴隆县花贡镇电视线路网的优化设计有很多意义。从理论方面来看，在论文的研究过程中主要运用了图论中的最小树模型，由此该论文可以作为图论中的最小树模型知识运用的实际例证，同时也是在电视线路网的优化设计方面的一种思想理念，最后本论文的研究能为相关课题研究提供参考价值。从实践方面来看，本文是以晴隆县花贡镇电视线路的实际情况为依据进行的研究，所以研究结果对该地广电公司规划设计数字电视线路具有一定的科学参考价值。该数字电视线路的优化设计主要根据住户的分布为依据进行研究，设计出来的结果在一定程度上能为当地村镇居民的业余生活带来方便。2.资料收集 贵州省晴隆县花贡镇的数字电视线路规划建设工作正在火热的开展中，通过走访晴隆县花贡镇广电公司相关人士、网上查阅晴隆县花贡镇的相关情况、实地考察后，我根据百度地图整理出了花贡镇的简图图1：花贡镇图5，根据晴隆县官网提供的资料整理出各地距离表1：花贡镇图表6。（图1） 花贡镇图表地名距离地名名百胜村都田村坪山村河塘新村母洒村竹塘村花贡社区518192220百胜村2714都田村9坪山村15河塘新村3母洒村10（单位：公里）（表1） 3.研究过程3.1资料处理对图1：花贡镇图分析，结合表1：花贡镇图表，整理得树图见图2。 （图2）3.2数据处理对图1：花贡镇图，结合表1：花贡镇图表作以下处理：(1)用线段表示数字电视线路。(2)用点表示数字电视线路的起点或终点，并标上记号为V0、V1(3)以线段为树图的权边，并标注权值。通过上面处理，综合图1：花贡镇图和表1：花贡镇图表中的信息用图2表示（主要研究其一行政社区和六个村）。3.3 电视线路设计3.3.1 影响线路走向选择的因素对于线路走向的选择，通常会考虑两个因素：(1)一般用户的需求：数字电视的使用量最多的居民区需要线路的覆盖；(2)特殊用户的需求：特殊的地点如政府、企事业单位、学校等公共场合都应覆盖。3.3.2 电视线路的确定 由于电视网络是为大众所服务的，所以选择电视线路时要选择用户密集地。考虑到上面的两个因素和实际情况，本文确定附件3中能够被选作为线路经过的地方有： (1)花贡社区V0(2)竹塘村V1(3)白胜村V2(4)都田村V3(5)坪山村V4 (6)河塘新村V5(7)母洒村V63.3.3具体电视线路的确定 数字电视线路参照公交线路网络优化的目标，根据晴隆县花贡镇的实际情况，本文重点以线路的最小树原则来确定电视线路。对于求最小树本文主要采用Kruskal算法和管梅谷算法求解。 3.3.3.1Kruskal算法 Kruskal算法基本步骤是：每步从未选的边中选取边e，使它与已选边不构成圈，且e是未选边中的最小权边，直到选够n-1条边为止。步骤 （1）先将附件3中边按大小顺序由小至大排列： （v0，v5）=2 （v0，v6）=2 （v5，v6）=3 （v0，v2）=5 （v3，v4）=9 （v1，v6）=10 （v1，v2）=14 （v4，v5）=15 （v0，v3）=18 （v0，v4）=19 （v0，v1）=20 （v2，v3）=27 （2）然后按边的排列顺序，取定：e1=（v0，v5） , e2=（v0，v6）。 由于下一个未选中的最小权边（v5，v6）与已选边e1，e2构成圈，所以排除。 选e3=（v0，v2）, e4=（v3，v4）, e5=（v1，v6） 由于下一个未选中的最小权边（v1，v2）与已选边e2，e5构成圈，所以排除。选e6=（v4，v5）。 （3）由（2）得到的图3就是图1的一棵最小树，它的权是：T*=（e1，e2，e3，e4，e5，e6）=2+2+5+9+10+15=43。用Kruskal算法整理后，线路长度一共只要43千米。 （图3）3.3.3.2管梅谷算法 管梅谷算法的基本步骤是：在赋权图G中任取一个回路，删去其中一条权最大的边，在余下的图中重复上述做法，直到无回路为止，便可得到最小生成树。步骤在附件3的赋权图中： 取闭合回路：v0v1v2v0 ，去掉其中最大的权边：（v0，v1）；取闭合回路：v0v2v3v0 ，去掉其中最大的权边：（v2，v3）；取闭合回路：v0v3v4v0 ，去掉其中最大的权边：（v0，v4）；取闭合回路：v0v5v6v0 ，去掉其中最大的权边：（v5，v6）。经过以上四个步骤后，得到图4，其中还有闭合回路，需要继续取闭合回路并去掉最大权边。 （图4）取闭合回路：v0v2v1v6v0，去掉其中最大的权边：（v1，v2）；取闭合回路：v0v3v4v5v0，去掉其中最大的权边：（v0，v3）。 最后得到图5，即一颗最小树，它的权是：T*=（e1，e2，e3，e4，e5，e6）=2+2+5+9+10+15=43。用管梅谷算法整理得出的结论与Kruskal算法整理得出的结论一致，线路总长只要43千米。 （图5）3.3.3.3结论结合各地区的实际情况和占地面积，中心机房位置在花贡镇上。花贡社区适合安装5个光机，竹塘村适合安装3个，百胜村适合安装7个，都田村适合安装4个，坪山村适合安装4个，河塘新村适合安装3个，母洒村适合安装6个。光缆分为光纤芯数4芯，光纤芯数8芯，光纤芯数12芯，光纤芯数16芯，光纤芯数20芯，光纤芯数24芯这六种型号，每个光机需要分光纤芯数2芯7。由于以后可能有增设光机的打算，所以每条线路要留有剩余的光纤芯数2芯。结合上述所需条