灌溉问题模型

《灌溉问题模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、灌溉问题模型的建立与分析AbjectToreducethecostofagriculturalactivitiesandbuildtheConservation-mindedSociety.Inthisarticle,wesetupamathematicalmodelaboutirrigationintheagriculturalactivitiesanddiscusshowtochannelsothatallthefieldcanbeirrigated.Moreover,wecanconfirmtheschemesthatcost

2、smallestinvariousofschemes.Intheaspectofalgorithms,wemakeuseofMinimalspanningtreeheretoobtainthewaytoconnectallthefieldsinminimumwages.Theessay,whichbasedontwoalgorithms:PrimandKruskal.Weformthearticleinthreeparts:Firstly,abstractthefarmerfieldintoconnectedgraph;Then,c

3、reatetheweightmatrix;Lastly,wetrytofindthewaytoconnectallthefieldsinminimumcostbyPrimandKruskal.IndexTerms——Minimalspanningtree,Prim,Kruskal摘要为了减少农民生产活动成本，创造节约型社会，我们对农业生产中的灌溉问题建立了数学模型，来讨论怎样开渠能使所有农田都能被灌溉，进一步将确定各种连接方式中最小成本的连接方案。从算法上来说，这是一个最小生成树问题，将一个连通图形取最小连接方式连接成一体。对于这种

4、问题，有两种算法：kruskal算法和prim算法。本文所描述的模型正是分别基于这两种算法所建立的，大致分为如下三个部分：首先，将灌溉问题的农田抽象成连通图的形式，并将连通方式输入。其次，将输入的矩阵转化为边权矩阵。最后，用kruskal算法和prim算法找出最短路径并输出连接方案。关键字：最小生成树kruskal算法prim算法一．问题的概述中国是世界上最大的农业国之一，耕地面积18.37亿亩，占世界现有耕地面积的7%左右。为了加快中国经济的发展，创造节约型社会，不仅仅要在工商业19方向中寻找机会，同时也要着眼于农业生产中的问题。

5、在农业生产中，灌溉是很重要，也很复杂的一步。现在的灌溉技术大概有十几种之多，其中应用灌溉渠将水库的水引到农田中灌溉的方式还是应用的比较广泛的。对于这种方式，计算开凿灌溉渠的成本就是最重要的问题，如何开凿能使所有农田都能连成一体并且开凿费用最少。基于这一农业生产问题，本文提出以下的两种数学模型。题中已给出了一块农田的缩略图，如图2.1，要求将图中的边（田埂）挖开，使所有农田可以连成一体。图1.1本文根据以上问题进行了如下两点拓展：1.该模型变为带权的无向连通图模型，即挖开每条边所需的费用不同，要求在原题的基础上使开凿整个灌溉渠的费用最

6、小。2.该模型变为带权的有向连通图模型，即从A到B的路与从B到A是不同的，建造的成本也不相同，在此条件下，将原来的农田连接起来，并使建造成本最低。二.模型部分1．基本假设进行如下假设：Ø用灌溉渠将两农田连接上就能使农田被灌溉，灌溉渠不会损坏，堵塞。Ø连接一块农田的每条灌溉渠灌溉效果相同。19Ø相邻的农田之间边权矩阵对应元素为1，不相邻表示为0。2．模型建立及求解2.1模型一：基于kruskal算法的灌溉问题模型。2.1.1模型思路首先将n个顶点看成n个孤立的连通分支（n个孤立点）并将所有的边按权从小大排序。按照边权值递增顺序，如果加

7、入边后存在圈则这条边不加，直到形成连通图。以下是具体实现说明：首先将上图1.1的实物图抽象为连通图并标号。接下来将用kruskal算法求解上面连通图的最小生成树，即能将上面12个节点连接在一起的连接方案。本模型中应用的kruskal算法其实是贪心算法的一种，其主要的想法是：首先将连通图的连接方式与权重表示为一个边权矩阵，这里的边权矩阵为一个0-1权值矩阵，元素是从到开凿灌溉渠的权值（其中为0）；接下来在边权矩阵中从左上开始找元素为1的坐标，并将该边的权值改为无穷大，即又生成了一个新的边权矩阵，在这个新的边权矩阵中再从左上开始寻找元素

8、为1的边，并重复上面的步骤。其中要说明的是不能循环连接，这样一定不是最优的连接方案。例如：若已经确定1和2连接,2和3连接，那么在接下来的边权矩阵中即使的权为1，也不应该选这条边。因为若是将这条边选中，那么1,2,3将循环连接，造成资